Binary Lifting

How can we weigh all weights in $[0,31]$ using as few weights as possible? (Weights may only be placed on one side of the balance.)

The answer is to use the five weights 1, 2, 4, 8, and 16, which can weigh every weight in $[0,31]$. Similarly, to weigh every weight in $[0,127]$, we can use 1, 2, 4, 8, 16, 32, and 64. By choosing powers of 2 as the weights each time, we can use very few weights to weigh any desired weight.

Why are so few needed? To weigh every weight in $[0,1023]$, we need only 10 weights; to weigh every weight in $[0,1048575]$, we need only 20. If the target weight doubles, the number of weights only needs to increase by 1. This is called logarithmic growth, because the number of weights required is proportional to the logarithm of the target weight range.

Given a cycle of length $n$ and a constant $k$, each move goes from point $i$ to point $(i+k)\bmod n+1$. A total of $m$ moves are made. Each point has a weight $a_i$. Find the sum of the weights of the starting points of the $m$ moves, modulo $10^9+7$.

Data range: $1\leq n\leq 10^6$, $1\leq m\leq 10^{18}$, $1\leq k\leq n$, $0\le a_i\le 10^9$.

It is clearly impossible to simulate $m$ moves by brute force, since $m$ can be as large as $10^{18}$; brute-force simulation would take too much time.

Therefore, we need some preprocessing to combine some information in advance so that the result can be obtained more quickly at query time. Recording the result for every possible number of moves would be infeasible in both time and space.

So how should we preprocess? Look at the first example. Do you have an idea now?

Returning to this problem, we need to preprocess some information and use it to combine the answer as quickly as possible. At the same time, the amount of preprocessed information must not be too large. Thus, we can preprocess information in units of powers of 2; this requires processing only a small amount of information during preprocessing and does not require much work during combination.

For this problem, we preprocess the result after jumping 1, 2, 4, 8, and so on steps from each point (the point reached and the sum of point weights). Then, to jump 13 steps, we only need to jump 1+4+8 steps: first jump 1 step from the starting point, then jump 4 steps from the endpoint reached, then jump 8 steps, while accumulating the precomputed sums of point weights. This gives the sum of point weights for 13 jumps.

For each $2^i$-step jump starting from each point, record go[i][x] as the endpoint after point $x$ jumps $2^i$ steps, and sum[i][x] as the sum of point weights obtained after point $x$ jumps $2^i$ steps. During preprocessing, use two nested loops. The information for a $2^i$-step jump can clearly be viewed as first jumping $2^{i-1}$ steps and then another $2^{i-1}$ steps, since $2^{i-1}+2^{i-1}=2^i$. Thus, sum[i][x] = sum[i-1][x]+sum[i-1][go[i-1][x]], and go[i][x] = go[i-1][go[i-1][x]].

There are also some implementation details to note. To ensure that no point is counted twice or omitted, we generally preprocess point-weight sums on a ‘left-closed, right-open’ interval. That is, for one step, we record only the weight of the current point; for two steps, we record the weights of the current point and the next point. Equivalently, the weight of the endpoint is never included in sum. Then, during preprocessing, the sums of the two parts can simply be added directly, without worrying that the endpoint of the first segment and the starting point of the second segment will be counted twice.

Here $m\leq 10^{18}$. Although this may look frightening, preprocessing values no greater than $65$ for $i$ is enough to solve the problem easily, much faster than brute-force enumeration. In technical terms, the time complexity of this approach is $\Theta(n\log m)$ for preprocessing and $\Theta(\log m)$ per query.

#include <cstdio>
using namespace std;

constexpr int mod = 1000000007;

int modadd(int a, int b) {
  if (a + b >= mod) return a + b - mod;  // replace modulo with subtraction to speed up computation
  return a + b;
}

int vi[1000005];

int go[75][1000005];  // make the array slightly larger to avoid out-of-bounds access; define the smaller dimension first when possible
int sum[75][1000005];

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", vi + i);
  }

  for (int i = 1; i <= n; ++i) {
    go[0][i] = (i + k) % n + 1;
    sum[0][i] = vi[i];
  }

  int logn = 31 - __builtin_clz(n);  // a quick way to take a logarithm
  for (int i = 1; i <= logn; ++i) {
    for (int j = 1; j <= n; ++j) {
      go[i][j] = go[i - 1][go[i - 1][j]];
      sum[i][j] = modadd(sum[i - 1][j], sum[i - 1][go[i - 1][j]]);
    }
  }

  long long m;
  scanf("%lld", &m);

  int ans = 0;
  int curx = 1;
  for (int i = 0; m; ++i) {
    if (m & (1ll << i)) {  // see the relevant bitwise-operation material; this asks whether bit i of m is 1
      ans = modadd(ans, sum[i][curx]);
      curx = go[i][curx];
      m ^= 1ll << i;  // set bit i to zero
    }
  }

  printf("%d\n", ans);
}