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 \]

写成卷积形式：

\[ \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} \]

我们知道：

\[ \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} \]

代码：

#include
    
     #define ll long long#define N 20005using 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<
     
      >1]>>1)|((i&1)<
      
       >1;        ll w=flag==1?ksm(G,(mod-1)/len):ksm(G,mod-1-(mod-1)/len);        for(int i=0;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<