洛谷 P6667 - [清华集训2016] 如何优雅地求和(下降幂多项式,多项式)
2024-08-30 07:09:30
wjz:《如何优雅地 AK NOI》
我:如何优雅地爆零
首先,按照这题总结出来的一个小套路,看到多项式与组合数结合的题,可以考虑将普通多项式转为下降幂多项式,因为下降幂和组合数都可以用阶乘相除的形式表示,而对于两个组合数相乘我们有恒等式 \(\dbinom{n}{m}\dbinom{m}{k}=\dbinom{n}{k}\dbinom{n-k}{m-k}\),这样我们可以将原式中待枚举变量 \(m\) 从两个组合数中转移到一个组合数(\(\dbinom{n-k}{m-k}\))中,也就进而可以用二项式定理等公式化简了。
因此此题我们也可以考虑设 \(f(x)=\sum\limits_{i=0}^mb_ix^{\underline{i}}\),下面开始推式子:
\[\begin{aligned}
ans&=\sum\limits_{k=0}^mf(k)\dbinom{n}{k}x^k(1-x)^{n-k}\\
&=\sum\limits_{k=0}^n\sum\limits_{j=0}^mb_jk^{\underline{j}}\dbinom{n}{k}x^k(1-x)^{n-k}\\
&=\sum\limits_{j=0}^mb_jj!\sum\limits_{k=j}^n\dbinom{k}{j}\dbinom{n}{k}x^k(1-x)^{n-k}\\
&=\sum\limits_{j=0}^mb_jj!\dbinom{n}{j}\sum\limits_{k=j}^n\dbinom{n-j}{k-j}x^k(1-x)^{n-k}\\
&=\sum\limits_{j=0}^mb_jj!\dbinom{n}{j}\sum\limits_{k=0}^{n-j}\dbinom{n-j}{k}x^{k+j}(1-x)^{n-k-j}\\
&=\sum\limits_{j=0}^mb_jj!\dbinom{n}{j}x^j(1-x+x)^{n-j}\\
&=\sum\limits_{j=0}^mb_jj!\dbinom{n}{j}x^j
\end{aligned}
\]
ans&=\sum\limits_{k=0}^mf(k)\dbinom{n}{k}x^k(1-x)^{n-k}\\
&=\sum\limits_{k=0}^n\sum\limits_{j=0}^mb_jk^{\underline{j}}\dbinom{n}{k}x^k(1-x)^{n-k}\\
&=\sum\limits_{j=0}^mb_jj!\sum\limits_{k=j}^n\dbinom{k}{j}\dbinom{n}{k}x^k(1-x)^{n-k}\\
&=\sum\limits_{j=0}^mb_jj!\dbinom{n}{j}\sum\limits_{k=j}^n\dbinom{n-j}{k-j}x^k(1-x)^{n-k}\\
&=\sum\limits_{j=0}^mb_jj!\dbinom{n}{j}\sum\limits_{k=0}^{n-j}\dbinom{n-j}{k}x^{k+j}(1-x)^{n-k-j}\\
&=\sum\limits_{j=0}^mb_jj!\dbinom{n}{j}x^j(1-x+x)^{n-j}\\
&=\sum\limits_{j=0}^mb_jj!\dbinom{n}{j}x^j
\end{aligned}
\]
因此我们只需求出 \(b_j\) 即可在线性的时间内计算出 \(ans\)。
接下来我们的任务是怎样由 \(f(x)\) 的点值计算出 \(b_i\),考虑 \(f(x)\) 的 \(\text{EGF}\),那么有
\[\begin{aligned}
\sum\limits_{n}\dfrac{f(n)x^n}{n!}&=\sum\limits_{n}\sum\limits_{j=0}^mb_jn^{\underline{j}}\dfrac{x^n}{n!}\\
&=\sum\limits_{j=0}^mb_j\sum\limits_{n}\dfrac{x^n}{(n-j)!}\\
&=\sum\limits_{j=0}^mb_jx^j\sum\limits_{n}\dfrac{x^{n-j}}{(n-j)!}
\end{aligned}
\]
\sum\limits_{n}\dfrac{f(n)x^n}{n!}&=\sum\limits_{n}\sum\limits_{j=0}^mb_jn^{\underline{j}}\dfrac{x^n}{n!}\\
&=\sum\limits_{j=0}^mb_j\sum\limits_{n}\dfrac{x^n}{(n-j)!}\\
&=\sum\limits_{j=0}^mb_jx^j\sum\limits_{n}\dfrac{x^{n-j}}{(n-j)!}
\end{aligned}
\]
记 \(A=\sum\limits_{j=0}^mb_jx^j,B=\sum\limits_{j}\dfrac{x^j}{j!}=e^x\),那么 \(\sum\limits_{n}\dfrac{f(n)x^n}{n!}=A\times B\)。
故 \(A=(\sum\limits_{n}\dfrac{f(n)x^n}{n!})\times e^{-x}\),NTT 一下即可。
时间复杂度 \(n\log n\)。
const int pr=3;
const int MOD=998244353;
const int ipr=(MOD+1)/3;
const int MAXP=1<<16;
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int rev[MAXP+5];
void NTT(vector<int> &a,int len,int type){
int lg=31-__builtin_clz(len);
for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);
for(int i=0;i<len;i++) if((i-rev[i])>>31) swap(a[i],a[rev[i]]);
for(int i=2;i<=len;i<<=1){
int W=qpow((type<0)?ipr:pr,(MOD-1)/i);
for(int j=0;j<len;j+=i){
for(int k=0,w=1;k<(i>>1);k++,w=1ll*w*W%MOD){
int X=a[j+k],Y=1ll*w*a[(i>>1)+j+k]%MOD;
a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
}
}
} if(!~type) for(int j=0,ivn=qpow(len,MOD-2);j<len;j++) a[j]=1ll*a[j]*ivn%MOD;
}
vector<int> conv(vector<int> a,vector<int> b){
int LEN=1;while(LEN<a.size()+b.size()) LEN<<=1;a.resize(LEN,0);b.resize(LEN,0);
NTT(a,LEN,1);NTT(b,LEN,1);for(int i=0;i<LEN;i++) a[i]=1ll*a[i]*b[i]%MOD;
NTT(a,LEN,-1);return a;
}
int n,m,x,fac[MAXP+5],ifac[MAXP+5];
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i]*ifac[i-1]%MOD;
}
int main(){
scanf("%d%d%d",&n,&m,&x);vector<int> a(m+1),b(m+1);init_fac(m);
for(int i=0;i<=m;i++) scanf("%d",&a[i]),a[i]=1ll*a[i]*ifac[i]%MOD;
for(int i=0;i<=m;i++) b[i]=((~i&1)?ifac[i]:(MOD-ifac[i]));a=conv(a,b);
int ans=0,cur=1;for(int i=0;i<=m;i++) ans=(ans+1ll*a[i]*cur%MOD*qpow(x,i))%MOD,cur=1ll*cur*(n-i)%MOD;
printf("%d\n",ans);
return 0;
}
最新文章
- bug描述技巧
- javascript基础06
- svn设置外网访问
- Jenkins邮件配置,实现邮件发送策略(可实现每个Job对应不同的发送邮箱)
- 【洛谷P1080】国王游戏
- JS面向对象组件(四) -- 面向对象的继承
- 部分视图调用方法总结(Action 、 RenderAction 、 Partial 、 RenderPartial)
- 变更到Android4.4的问题
- Bluetooth LE(低功耗蓝牙) - 第五部分
- (转)ios跳转到通用页面
- GitHub上整理
- 寻找与疾病相关的SNP位点——R语言从SNPedia批量提取搜索数据
- gsp页面标签
- 【LSGDOJ1834 Tree】树链剖分
- 像使用数据库一样使用xml
- 2.Spring 拦截器应用
- 扒光IT界江湖骗子巴蜀万明的底裤
- C#基础知识总结(七)
- ShardedJedisPool的使用
- 微信小程序点击图片放大预览
热门文章
- vue基础-组件&;插槽
- 【UE4 设计模式】状态模式 State Pattern
- 如何接入 K8s 持久化存储?K8s CSI 实现机制浅析
- Linux下Zabbix5.0 LTS监控基础原理及安装部署(图文教程)
- numpy中的nan和常用方法
- Machine learning(1-Introduction)
- 计算机网络之IPv4(IPv4分组、IPv4地址、NAT、子网划分与子网掩码、CIDR、ARP协议、DHCP、ICMP)
- 【Azure 存储服务】如何把开启NFS 3.0协议的Azure Blob挂载在Linux VM中呢?(NFS: Network File System 网络文件系统)
- Eclipse简单介绍
- 常用的package.json以及React相关