「清华集训2016」如何优雅地求和

题目链接：http://uoj.ac/problem/269。

这就涉及到我的知识盲区了

学到了一个叫下降幂多项式的操作，就是说我们可以把一个多项式写成这样的形式：

$$f(x)=\sum_{i=0}^{m}a_i\binom{x}{i}$$

这样有时候可以帮助我们消掉一些组合数。

假设我们可以得到$a_i$，把式子带进去试试：

$$\begin{align} ans&=\sum_{k=0}^{n}\sum_{i=0}^{m}a_i\binom{k}{i}\binom{n}{k}x^k(1-x)^{n-k}\\ &=\sum_{k=0}^{n}\sum_{i=0}^{m}a_i\binom{n}{i}\binom{n-i}{k-i}x^k(1-x)^{n-k}\\ &=\sum_{i=0}^{m}a_i\binom{n}{i}\sum_{k=i}^{n}\binom{n-i}{k-i}x^k(1-x)^{n-k}\\ &=\sum_{i=0}^{m}a_i\binom{n}{i}x^i\sum_{k=0}^{n-i}\binom{n-i}{k}x^k(1-x)^{n-k}\\ &=\sum_{i=0}^{m}a_i\binom{n}{i}x^i\\ \end{align}$$

最后一步是$(x+1-x)^{n-i}$的二项式展开。

也就是说如果我们得到了$a_i$就可以暴力算出答案。

而显然二项式反演一下就可以得到$a_i​$：

$$\begin{align} f(x)&=\sum_{i=0}^{x}a_i\binom{x}{i}\\ a_x&=\sum_{i=0}^{x}(-1)^{x-i}\binom{x}{i}f(i)\\ \frac{a_x}{x!}&=\sum_{i=0}^{x}\frac{(-1)^{x-i}}{(x-i)!}\cdot \frac{f(i)}{i!}\\ \end{align}$$

显然$\rm NTT$优化，复杂度$O(m\log m)$。

为啥有人暴力卷积过了啊，数据范围为哈开这么小啊

#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;

int f[maxn],fac[maxn],ifac[maxn],n,m,x,a[maxn],w[maxn],pos[maxn],N,bit;

int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
    return res;
}

void gen() {
    fac[0]=ifac[0]=1;
    for(int i=1;i<=m;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[m]=qpow(fac[m],mod-2);
    for(int i=m-1;i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
    for(N=1,bit=-1;N<=m<<1;N<<=1,bit++);
    w[0]=1,w[1]=qpow(3,(mod-1)/N);
    for(int i=2;i<N;i++) w[i]=1ll*w[i-1]*w[1]%mod;
    for(int i=1;i<N;i++) pos[i]=pos[i>>1]>>1|((i&1)<<bit);
}

void ntt(int *r,int op) {
    for(int i=1;i<N;i++) if(pos[i]>i) swap(r[i],r[pos[i]]);
    for(int i=1,d=N>>1;i<N;i<<=1,d>>=1)
        for(int j=0;j<N;j+=i<<1)
            for(int k=0;k<i;k++) {
                int x=r[j+k],y=1ll*w[k*d]*r[i+j+k]%mod;
                r[j+k]=(x+y)%mod,r[i+j+k]=(x-y+mod)%mod;
            }
    if(op==-1) {
        int d=qpow(N,mod-2);reverse(r+1,r+N);
        for(int i=0;i<N;i++) r[i]=1ll*r[i]*d%mod;
    }
}

int main() {
    read(n),read(m),read(x);gen();
    for(int i=0;i<=m;i++) read(f[i]),f[i]=1ll*f[i]*ifac[i]%mod;
    for(int i=0;i<=m;i++) a[i]=((i&1?-1:1)*ifac[i]+mod)%mod;
    ntt(a,1),ntt(f,1);
    for(int i=0;i<N;i++) a[i]=1ll*a[i]*f[i]%mod;
    ntt(a,-1);
    for(int i=0;i<=m;i++) a[i]=1ll*a[i]*fac[i]%mod;
    int ans=0,c=1;
    for(int i=0;i<=m;i++) {
        if(i) c=1ll*(n-i+1)*qpow(i,mod-2)%mod*c%mod;
        ans=(ans+1ll*a[i]*c%mod*qpow(x,i)%mod)%mod;
    }write(ans);
    return 0;
}