abc 选做
2021/12/30 6:07:14
本文主要是介绍abc 选做,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
abc231g
\(\frac{1}{n^k} \sum\frac{k!}{\prod b_i!} \prod (a_i+b_i)\),其中 \(\sum b_i=k\)
构造生成函数 \(f_i=\sum \frac{a_i+j}{j!}x^j=e^x(a_i+x)\),欲求式为 \(k![x^k]\prod f_i=k![x^k] e^{nx}\prod (a_i+x)\)
预处理 \(g_i\) 为任选 \(i\) 个乘积的和,原式为 \(\frac{1}{n^k} k!\sum\limits_{i=0}^n g_{n-i} n^{k-i} \frac{1}{(k-i)!}=\sum\limits_{i=0}^n g_{n-i} \frac{k^{\underline i}}{n^i}\)
#include<bits/stdc++.h> using namespace std; #define inf 1e9 const int maxn=2e5+10; const int mod=998244353; inline int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*f; } const int N=2e3+5; int n,k,a[N],dp[N][N],ans; inline int ksm(int x,int y){ int res=1; while(y){ if(y&1)res=1ll*res*x%mod; x=1ll*x*x%mod;y>>=1; }return res; } int main(){ n=read(),k=read(); for(int i=1;i<=n;i++)a[i]=read(); dp[0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=i;j++) dp[i][j]=(dp[i-1][j]+1ll*a[i]*dp[i-1][j-1])%mod; int K=ksm(n,mod-2); for(int i=0,k1=1,k2=1;i<=n;i++){ ans=(ans+1ll*dp[n][n-i]*k1%mod*k2)%mod; k1=1ll*k1*K%mod;k2=1ll*k2*(k-i)%mod; }printf("%d\n",ans); return 0; }
这篇关于abc 选做的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升