Blog #6



Editorial of "Tima and sum of powers"


I got 100 points on this problem during a competition. Now, reminiscing about my time at that Olympiad, I decided to write an editorial for this problem.
You can download full tests and author solutions here. You can submit your solution here

Statement

Editorial

Code

              const int MAX_N = (int)1e5 + 123;
              const int mod = (int)1e9 + 7;

              int n, m, k;
              int a[MAX_N];

              int pw[30][MAX_N], sum[30][MAX_N];
              int c[30][30];

              void add(int &a, const int &b) {
                  a += b;
                  if (a >= mod)
                      a -= mod;
              }

              int get(int it, int l, int r) {
                  int res = sum[it][r];
                  add(res, mod - sum[it][l - 1]);
                  return res;
              }

              int main() {
                  scanf("%d%d%d", &n, &m, &k);
                  for (int i = 1; i <= n; i++) {
                      scanf("%d", &a[i]);
                  }
                  for (int i = 0; i <= k; i++) {
                      c[i][0] = c[i][i] = 1;
                      for (int j = 1; j < i; j++) {
                          c[i][j] = c[i - 1][j];
                          add(c[i][j], c[i - 1][j - 1]);
                      }
                  }
                  pw[0][0] = 1;
                  for (int it = 0; it <= k; it++) {
                      for (int i = 1; i <= n; i++) {
                          if (it == 0)
                              pw[it][i] = 1;
                          else
                              pw[it][i] = pw[it - 1][i] * 1ll * i % mod;
                          sum[it][i] = sum[it][i - 1];
                          add(sum[it][i], pw[it][i] * 1ll * a[i] % mod);
                      }
                  }
                  for (int i = 1; i + m - 1 <= n; i++) {
                      int cons = i - 1;
                      int res = 0;
                      for (int j = 0; j <= k; j++) {
                          int now = c[k][j] * 1ll * pw[j][cons] % mod;
                          now = 1ll * now * get(k - j, i, i + m - 1) % mod;
                          if (j % 2 == 1)
                              now = mod - now;
                          add(res, now);
                      }
                      printf("%d\n", res);
                  }
                  return 0;
              }