UOJ #269. 【清华集训2016】如何优雅地求和
给定一个\(m\)次多项式\(f(x)\)的\(m+1\)个点值：\(f(0)\)到\(f(m)\)。
然后求：
\[Q(f,n,x) = \sum_{k = 0}^{n}f(k){n\choose k}x^k(1 - x) ^{n - k} \pmod{998244353}
\]
\]
考虑一个很巧妙的变化：组合数多项式！
设：
\[f(n)=\sum_{i=0}^m\binom{n}{i}h_i
\]
\]
可以这么玩的原因是\(\binom{n}{m}\)其实是一个关于\(n\)的\(m\)次的多项式。因为\(\binom{n}{m}=\frac{\prod_{i=1}^m(n-i+1)}{m!}\)。
这就能理解为什么输入的是\(m+1\)个点值了，因为这样我们就能用二项式反演来求出\(h\)：
对于\(m<i\leq n\)，我们直接认为\(h_i=0\)，因为只需要\(m\)项的\(h\)就可以确定\(f\)了。
\[f(n)=\sum_{i=0}^n\binom{n}{i}h_i\\
\Rightarrow h_n=\sum_{i=0}^n (-1)^{n-i}\binom{n}{i}f_i
\]
\Rightarrow h_n=\sum_{i=0}^n (-1)^{n-i}\binom{n}{i}f_i
\]
写成卷积形式：
\[\frac{h_n}{n!}=\sum_{i=0}^n\frac{(-1)^{n-i}}{(n-i)!}\frac{f_i}{i!}
\]
\]
再来算答案。
考虑对\(f\)的每一项计算：
\[\begin{align}
Q(f,n,x) &=\sum_{i=0}^mh_i\sum_{k=i}^n\binom{k}{i}\binom{n}{k}x^k(1-x)^{n-k} \\
\end{align}
\]
Q(f,n,x) &=\sum_{i=0}^mh_i\sum_{k=i}^n\binom{k}{i}\binom{n}{k}x^k(1-x)^{n-k} \\
\end{align}
\]
我们知道：
\[\binom{n}{i}\binom{i}{j}=\binom{n}{j}\binom{n-i}{i-j}
\]
\]
所以：
\[\begin{align}
Q(f,n,x) &=\sum_{i=0}^mh_i\sum_{k=i}^n\binom{k}{i}\binom{n}{k}x^k(1-x)^{n-k} \\
&=\sum_{i=0}h_i\sum_{k=i}^n\binom{n}{i}\binom{n-i}{k-i}x^k(1-x)^{n-k}\\
&=\sum_{i=0}h_i\binom{n}{i}x^i \sum_{k=i}^n\binom{n-i}{k-i}x^{k-i}(1-x)^{n-k}\\
&=\sum_{i=0}h_i\binom{n}{i}x^i(x+1-x)^{n-i}\\
&=\sum_{i=0}h_i\binom{n}{i}x^i\\
\end{align}
\]
Q(f,n,x) &=\sum_{i=0}^mh_i\sum_{k=i}^n\binom{k}{i}\binom{n}{k}x^k(1-x)^{n-k} \\
&=\sum_{i=0}h_i\sum_{k=i}^n\binom{n}{i}\binom{n-i}{k-i}x^k(1-x)^{n-k}\\
&=\sum_{i=0}h_i\binom{n}{i}x^i \sum_{k=i}^n\binom{n-i}{k-i}x^{k-i}(1-x)^{n-k}\\
&=\sum_{i=0}h_i\binom{n}{i}x^i(x+1-x)^{n-i}\\
&=\sum_{i=0}h_i\binom{n}{i}x^i\\
\end{align}
\]
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 20005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
const ll mod=998244353;
ll ksm(ll t,ll x) {
ll ans=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1) ans=ans*t%mod;
return ans;
}
int n,m,x;
ll f[N];
void NTT(ll *a,int d,int flag) {
static int rev[N<<2];
static ll G=3;
int n=1<<d;
for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<d-1);
for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int s=1;s<=d;s++) {
int len=1<<s,mid=len>>1;
ll w=flag==1?ksm(G,(mod-1)/len):ksm(G,mod-1-(mod-1)/len);
for(int i=0;i<n;i+=len) {
ll t=1;
for(int j=0;j<mid;j++,t=t*w%mod) {
ll u=a[i+j],v=a[i+j+mid]*t%mod;
a[i+j]=(u+v)%mod;
a[i+j+mid]=(u-v+mod)%mod;
}
}
}
if(flag==-1) {
ll inv=ksm(n,mod-2);
for(int i=0;i<n;i++) a[i]=a[i]*inv%mod;
}
}
ll A[N<<2],B[N<<2];
ll H[N];
ll fac[N<<2],ifac[N<<2];
ll C(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
ll down[N];
ll CC(int n,int m) {
if(!m) return 1;
return down[m]*ifac[m]%mod;
}
int main() {
n=Get(),m=Get(),x=Get();
for(int i=0;i<=m;i++) f[i]=Get();
fac[0]=1;
for(int i=1;i<=m;i++) fac[i]=fac[i-1]*i%mod;
ifac[m]=ksm(fac[m],mod-2);
for(int i=m-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
int d=ceil(log2(2*m+1));
ll flag=1;
for(int i=0;i<=m;i++,flag=flag*(mod-1)%mod) A[i]=flag*ifac[i]%mod;
for(int i=0;i<=m;i++) B[i]=f[i]*ifac[i]%mod;
NTT(A,d,1),NTT(B,d,1);
for(int i=0;i<1<<d;i++) A[i]=A[i]*B[i]%mod;
NTT(A,d,-1);
for(int i=0;i<=m;i++) H[i]=A[i]*fac[i]%mod;
ll ans=0;
down[1]=n;
for(int i=2;i<=m;i++) down[i]=down[i-1]*(n-i+1)%mod;
for(int i=0;i<=m;i++) (ans+=H[i]*ksm(x,i)%mod*CC(n,i))%=mod;
cout<<ans;
return 0;
}