一个人的高三楼

题目链接：Click here

Solution:

题目名字有点伤感啊。。。

直接看题吧，\(k\)次前缀和，瞬间想到\(O(nk)\)的做法，20pts到手了，走吧！

回到正题。。。不难想到，我们构造一个生成函数\(G(x)=\sum_{i=0}^n x^i\)，同时有\(A(x)=\sum_{i=1}^n a_ix^i\)

那么\(A\times G\)就相当于对\(A\)做了一次前缀和了，那么\(S_n^k=A\times G^k\)，难道要多项式快速幂？

多项式快速幂是不可能的，这辈子都不可能的，考虑\(G\)的特殊性，它的每一项系数都是1

我们一下子就能发现，\(G^k\)与组合数的关系，\(G^k\)的第\(i\)项的系数就是\({i+k-1\choose k-1}\)，不就是插板法吗

那么我们把\(G^k\)求出来之后，直接上\(NTT\)即可

Code:

#include
#define int long long 
#define Pi acos(-1.0)
using namespace std;
const int N=4e5+11;
const int mod=998244353;
int n,m,k,len=1,tim,p[N];
int a[N],trans[N],inv[N];
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int qpow(int u,int t){
    int re=1;
    while(t){
        if(t&1) re=re*u%mod;
        t>>=1;u=u*u%mod;
    }return re;
}
void NTT(int *v,int flag){
    for(int i=0;i>1);u++,w=w*wn%mod){
                int x=v[u],y=w*v[u+(l>>1)]%mod;
                v[u]=(x+y)%mod;v[u+(l>>1)]=(x-y+mod)%mod;
            }    
        }
    }
}
signed main(){
    n=m=read();k=read()%mod;++n;++m;
    for(int i=1;i>1]>>1)|((i&1)<<(tim-1));
    trans[0]=1;inv[1]=1;
    for(int i=2;i<=len;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(int i=1;i