题解 P6667 【[清华集训2016] 如何优雅地求和】
Karry5307
·
·
题解
题面
给定 n,x 和多项式 F(x) 在 0,1,\cdots,m 的点值 a_i，求
\sum\limits_{k=0}^{n}F(k)\binom{n}{k}x^{k}(1-x)^{n-k}
答案对 998244353 取模。
\texttt{Data Range:}n\leq 10^9,m\leq 2\times 10^4,0\leq a_i,x\lt 998244353
题解
目前是本题最优解。（虽然很快不是了）
先吐槽一句：这个毒瘤 \texttt{F\color{red}ee\_cle6418} 咋样例输出都能打错啊，严重影响做题体验。
不知道大家有没有做过 A 卷的组合数问题，没看过的可以先去看我的题解。麻烦了麻烦了给我点个赞捧个场吧
同样，我们还是要对这个式子进行降维打击。有了上一题的经验，我们可以直接考虑先拆下降幂。假设 F(x)=\sum\limits_{k=0}^{m}f_kx^{\underline k}，那么原式可以写成
\sum\limits_{k=0}^{n}\binom{n}{k}x^{k}(1-x)^{n-k}\sum\limits_{i=0}^{\min(m,k)}f_i\frac{k!}{(k-i)!}
接下来来一波交换求和顺序，顺手拆掉二项式系数，约一下分：
\sum\limits_{i=0}^{m}\sum\limits_{k=i}^{n}x^{k}(1-x)^{n-k}f_i\frac{n!}{(n-k)!(k-i)!}
如果分子是 (n-i)! 那就更好了，于是可以考虑凑一个出来：
\sum\limits_{i=0}^{m}\sum\limits_{k=i}^{n}x^{k}(1-x)^{n-k}f_i\binom{n-i}{k-i}\frac{n!}{(n-i)!}
接下来有一个很绝妙的操作：二项式中有一个分母是 k-i，另一个是 n-k，而 1-x 的次数是 n-k，所以我们也想凑一个 x 的次数为 k-i（其实这个操作曾经出现在 P6073，但是那个题不仅拆了幂来凑形式也拆了二项式来凑卷积），于是提取一下与 k 无关的东西，并凑 x 的指数，得到
\sum\limits_{i=0}^{m}f_ix^i\frac{n!}{(n-i)!}\sum\limits_{k=i}^{n}x^{k-i}(1-x)^{n-k}\binom{n-i}{k-i}
接下来如果对推柿子有感觉的可以直接看出是二项式定理，如果没感觉的话可以做 k\gets k-i 的代换（就是新的 k 代表原来的 k-i），以及设 p=n-i：
\sum\limits_{i=0}^{m}f_ix^i\frac{n!}{(n-i)!}\sum\limits_{k=0}^{n-i}x^{k}(1-x)^{p-k}\binom{p}{k}
所以右边的求和项就是 (x+1-x)^{p+1}=1，于是就得到最终式子
\sum\limits_{i=0}^{m}f_ix^i\frac{n!}{(n-i)!}
接下来考虑怎么求下降幂多项式的系数。
先考虑下降幂单项式如何转换成普通多项式，考虑 x^{\underline n} 的 \texttt{EGF}，设为 F_0(x)。（因为 k\geq n 的时候下降幂才有非零值）
F_0(x)=\sum\limits_{k=n}^{\infty}\frac{k^{\underline n}}{k!}x^k
根据定义式拆掉下降幂并提出 x^n约分得到
F_0(x)=x^n\sum\limits_{k=n}^{\infty}\frac{x^{k-n}}{(k-n)!}
做 k\gets k-n 的代换
F_0(x)=x^n\sum\limits_{k=0}^{\infty}\frac{x^k}{k!}
于是得到
F_0(x)=x^ne^x
接下来设 F(x) 为某下降幂多项式点值的 \texttt{EGF}，G(x) 为其系数的 \texttt{OGF}（注意！这里不是 \texttt{EGF}！），f 为该多项式的系数序列，得到
F(x)=\sum\limits_{k=0}^{\infty}f_kx^{\underline k}=e^x\sum\limits_{k=0}^{\infty}f_kx^k=e^xG(x)
所以 G(x)=e^{-x}F(x)。
题面中给我们的是 F(x)，所以可以求出 G(x) 并得到答案。时间复杂度 O(m\log m)。
### 代码
```cpp
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef int ll;
typedef long long int li;
typedef unsigned long long int ull;
const ll MAXN=65537,MOD=998244353,G=3,INVG=332748118;
ll n,m,x,res,binom=1,pw=1;
ll rev[MAXN],omgs[MAXN],invo[MAXN],f[MAXN],expn[MAXN],fact[20005],finv[20005];
inline ll read()
{
register ll num=0;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num;
}
inline ll qpow(ll base,ll exponent)
{
ll res=1;
while(exponent)
{
if(exponent&1)
{
res=(li)res*base%MOD;
}
base=(li)base*base%MOD,exponent>>=1;
}
return res;
}
inline void setup(ll cnt)
{
fact[0]=fact[1]=finv[0]=1;
for(register int i=1;i<=cnt;i++)
{
fact[i]=(li)fact[i-1]*i%MOD;
}
finv[cnt]=qpow(fact[cnt],MOD-2);
for(register int i=cnt-1;i;i--)
{
finv[i]=(li)finv[i+1]*(i+1)%MOD;
}
}
inline void setupOmg(ll cnt)
{
ll limit=log2(cnt)-1,omg;
omg=qpow(G,(MOD-1)>>(limit+1)),omgs[cnt>>1]=1;
for(register int i=(cnt>>1|1);i!=cnt;i++)
{
omgs[i]=(li)omgs[i-1]*omg%MOD;
}
for(register int i=(cnt>>1)-1;i;i--)
{
omgs[i]=omgs[i<<1];
}
}
inline void NTT(ll *cp,ll cnt,ll inv)
{
static ull tcp[MAXN];
register ll cur=0,x,shift=log2(cnt)-__builtin_ctz(cnt);
if(inv==-1)
{
reverse(cp+1,cp+cnt);
}
for(register int i=0;i<cnt;i++)
{
tcp[rev[i]>>shift]=cp[i];
}
for(register int i=2;i<=cnt;i<<=1)
{
cur=i>>1;
for(register int j=0;j<cnt;j+=i)
{
for(register int k=0;k<cur;k++)
{
x=tcp[j|k|cur]*omgs[k|cur]%MOD;
tcp[j|k|cur]=tcp[j|k]+MOD-x,tcp[j|k]+=x;
}
}
}
for(register int i=0;i<cnt;i++)
{
cp[i]=tcp[i]%MOD;
}
if(inv==1)
{
return;
}
x=MOD-(MOD-1)/cnt;
for(register int i=0;i<cnt;i++)
{
cp[i]=(li)cp[i]*x%MOD;
}
}
inline void conv(ll fd,ll *f,ll *g,ll *res)
{
static ll tmpf[MAXN],tmpg[MAXN];
ll cnt=1,limit=-1;
while(cnt<(fd<<1))
{
cnt<<=1,limit++;
}
memcpy(tmpf,f,fd<<2),memcpy(tmpg,g,fd<<2);
for(register int i=0;i<cnt;i++)
{
rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
}
NTT(tmpf,cnt,1),NTT(tmpg,cnt,1);
for(register int i=0;i<cnt;i++)
{
tmpf[i]=(li)tmpf[i]*tmpg[i]%MOD;
}
NTT(tmpf,cnt,-1),memcpy(res,tmpf,fd<<2);
}
int main()
{
n=read(),m=read(),x=read(),setupOmg(65536),setup(m+1);
for(register int i=0;i<=m;i++)
{
f[i]=(li)read()*finv[i]%MOD,expn[i]=i&1?MOD-finv[i]:finv[i];
}
conv(m+1,f,expn,f);
for(register int i=0;i<=m;i++)
{
res=(res+(li)f[i]*binom%MOD*pw)%MOD;
binom=(li)binom*(n-i)%MOD,pw=(li)pw*x%MOD;
}
printf("%d\n",res);
}
```