LOJ#6261. 一个人的高三楼 构造函数 NTT
相关题目:LOJ#6261. 一个人的高三楼

题目描述

一天的学习快要结束了,高三楼在晚自习的时候恢复了宁静。 不过,HSD 桑还有一些作业没有完成,他需要在这个晚自习写完。比如这道数学题:

1、给出一个数列,求它的前 ii 项和 SiS_{i}i{x1xn,xN}i\in \{x|1\le x\le n,x\in \mathbb{N}\}

HSD 桑擅长数学,很快就把这题秒了…… 然而还有第二题:

2、如果把上一问的前 ii 项和看成一个新数列,请求出它的前 ii 项和

看完第二题,还有第三题……HSD 桑已经预感到情况不妙了。 HSD 桑大致看了看题,发现有些规律。其实就是在求 kk 次前缀和。如果我们借用函数迭代的标记,就是在求 Sn(k)S_n^{(k)}...... 3{3}

HSD 桑还有很多作业要写,请你帮助他完成这项作业。

输入格式

第一行,两个正整数 n,kn,knn 表示数列的长度,kk 的意义如题目描述; 第二行,nn 个正整数,表示这个数列,两个数之间用一个空格隔开。

输出格式

nn 行,每行一个数,第 ii 行表示 Si(k)S_i^{(k)},结果可能会非常大,请对 998244353998244353 取模后输出。

样例

样例输入 1

4 1
1 2 3 4

样例输出 1

1
3
6
10

样例解释 1

对于这个序列,求它的 11 次前缀和,就是输出这个数列的前缀和咯……

样例输入 2

4 3
1 2 3 4

样例输出 2

1
5
15
35

样例解释 2

要求这个数列的 33 次前缀和,这个数列的 11 次前缀和为 {1,3,6,10}\{1,3,6,10\}22 次前缀和为 {1,4,10,20}\{1,4,10,20\}33 次前缀和即为 {1,5,15,35}\{1,5,15,35\}

数据范围与提示

本题为捆绑测评,只有一组子任务内所有测试点均通过才能获得该子任务的分数。

Subtask 分数 nn kk
11 2020 103\le 10^3 102\le 10^2
22 3030 105\le 10^5 218\le 2^{18}
33 5050 105\le 10^5 260\le 2^{60}

对于全部数据,保证数列中的任意一个数的范围在 [1,998244353)[1,998244353) 内。

Solution

考虑 NTT 。

我们设

显然有

T=i=1nxiT=\sum_{i=1}^{n}x^{i}

成立。 所以

使用 NTT 复杂度 O(n log n log k)O(n~log~n~log~k)kk 太大卡不过 200ms......

考虑 的数学意义,由二项式定理知其每项用组合数均可表示为 。预处理即可。 总复杂度 O(n log n)O(n~log~n)

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <memory>
#define p 998244353 //原根=3
typedef long long ll;
const int N = 1<<19;
int n, R[N];
long long k, a[N], b[N], pow3[N], inv3[N], inv[N];
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}

inline ll qpow(ll a,int b) {
ll res=1;
for(;b;b>>=1,a=a*a%p)if(b&1)res=res*a%p;
return res;
}
inline void init(int n) {
for(int i=0; i<n; ++i)
R[i] = ((R[i>>1]>>1)|(n>>(i&1)))&(n-1);
ll inv = qpow(3, p-2);
for(int i=1; i<=n; i<<=1) pow3[i]=qpow(3,(p-1)/i);
for(int i=1; i<=n; i<<=1) inv3[i]=qpow(inv,(p-1)/i);
}

inline void NTT(ll *a, int n, int f) {
for(int i=0; i<n; ++i)
if(R[i] > i) std::swap(a[R[i]], a[i]);
ll wn, omega, t;
for(int l=1; l<n; l<<=1) {
wn = f==1?pow3[l*2]:inv3[l*2];
for(int j=0; j<n; j+=(l<<1)) {
omega = 1;
for(int k=0; k<l; ++k,omega=omega*wn%p)
{
t = a[j+k+l]*omega%p;
a[j+k+l] = (a[j+k]-t+p)%p;
a[j+k] = (a[j+k]+t)%p;
}
}
}
if(f==-1) {
ll inv = qpow(n, p-2);
for(int i=0; i<n; ++i) a[i] = a[i]*inv%p;
}
}

int main() {
read(n), read(k), k%=p;
for(int i=0; i<n; ++i) read(a[i]);
inv[1]=b[0] = 1;
for(int i=2; i<n; ++i) inv[i] = (p-p/i)*inv[p%i]%p;
for(int i=1; i<n; ++i) b[i] = b[i-1]*(i+k-1)%p*inv[i]%p;
int m = 1;
while(m < 2*n) m<<=1;
init(m);
NTT(a, m, 1), NTT(b, m, 1);
for(int i=0; i<m; ++i) a[i]=a[i]*b[i]%p;
NTT(a, m, -1);
for(int i=0; i<n; ++i) printf("%lld\n", a[i]);
return 0;
}