LibreOJ 6261 一个人的高三楼

发表于 | 分类于

Description

给你一个长为\(n\)的序列\(A\)，将它做\(k\)次前缀和，输出结果序列，每一项对\(998244353\)取模。

\(1\leq n\leq 10^5,1\leq k\leq 2^{60}\)。

Solution

终于有我会做的题力，，，

考虑构造\(A\)的生成函数\(A(x)\)，然后我们想一下怎么对生成函数做前缀和。

昨晚前缀和之后，每一项都会往后面所有项（包括这一项）加一下，换言之乘上的东西的生成函数就是\(1 + x^2 + x^3 +\ldots = \frac{1}{1 - x}\)，做\(k\)次前缀和就乘了\(k\)次，所以总的来说乘了一个\((1 - x)^{-k}\)。

然后负指数是不是很毒啊……其实也不是，注意到底数是一个二项式，所以直接用广义二项式定理展开即可。更好的事情是广义组合数是可以和普通组合数一样从左到右推一整行的，这样就舒服多了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
using ll = long long;
const ll ha = 998244353LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

int flip(int bi, int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans |= (1 << (bi - i - 1));
    }
  }
  return ans;
}
void NTT(ll *A, int bi, bool flag = false) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int f = flip(bi, i);
    if(f < i) std::swap(A[f], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi_n = inv(xi_n);
    for(int i = 0; i < n; i += (L << 1)) {
      ll xi = 1LL;
      for(int j = i; j < i + L; j ++) {
        ll x = A[j], y = A[j + L];
        A[j] = (x + (y * xi) % ha) % ha;
        A[j + L] = (x - (y * xi) % ha + ha) % ha;
        xi = xi * xi_n % ha;
      }
    }
  }
  if(flag) {
    ll v = inv(n);
    for(int i = 0; i < n; i ++) A[i] = A[i] * v % ha;
  }
}

ll A[400005], B[400005];
int main() {
  int n; ll k; scanf("%d%lld", &n, &k);
  for(int i = 0; i < n; i ++) scanf("%lld", &A[i]);
  ll C = 1; B[0] = C;
  ll up = (ha - k % ha) % ha;
  for(int i = 1; i < n; i ++) {
    if(true) {
      C = C * ((up - (ll)i + 1LL + ha) % ha) % ha;
      C = C * inv(i) % ha;
    }
    C = (ha - C) % ha;
#ifdef LOCAL
    printf("C(%d) : %lld\n", i, C);
#endif
    B[i] = C;
  }
  int bi = 0, len = 1;
  while(len <= 2 * n) bi ++, len <<= 1;
  NTT(A, bi); NTT(B, bi);
  for(int i = 0; i < len; i ++) {
    A[i] = A[i] * B[i] % ha;
  }
  NTT(A, bi, true);
  for(int i = 0; i < n; i ++) {
    printf("%lld\n", A[i]);
  }
  return 0;
}