快速搭建网站 开源,网站的外部推广,医疗器械做网站到哪里先备案,江门网站建设报价正题
题目链接:https://www.luogu.com.cn/problem/CF891E 题目大意 nnn个数字的一个序列aia_iai#xff0c;每次随机选择一个让它减去一。然后贡献加上所有其他aia_iai的乘积。
执行kkk次#xff0c;求贡献答案。 1≤n≤5000,0≤ai,k≤1091\leq n\leq 5000,0\leq a_i,k…正题
题目链接:https://www.luogu.com.cn/problem/CF891E 题目大意
nnn个数字的一个序列aia_iai每次随机选择一个让它减去一。然后贡献加上所有其他aia_iai的乘积。
执行kkk次求贡献答案。
1≤n≤5000,0≤ai,k≤1091\leq n\leq 5000,0\leq a_i,k\leq 10^91≤n≤5000,0≤ai,k≤109 解题思路
这个操作很麻烦但是其实答案就是开始时所有aia_iai的乘积减去结束时所有aia_iai的乘积。
设第iii个数减去了bib_ibi次就是求∏i1nai−∏i1n(ai−bi)\prod_{i1}^na_i-\prod_{i1}^n(a_i-b_i)∏i1nai−∏i1n(ai−bi)的期望考虑怎么求后面那个东西。
推一下式子不难发现对于一组bib_ibi对期望的贡献就是 1nkk!∏i1n(bi!)∏i1n(ai−bi)\frac{1}{n^k}\frac{k!}{\prod_{i1}^n(b_i!)}\prod_{i1}^n(a_i-b_i)nk1∏i1n(bi!)k!i1∏n(ai−bi) 总方案×可重排方案×贡献 把∏i1n(bi!)\prod_{i1}^n(b_i!)∏i1n(bi!)丢进去会有很神奇的结果 ⇒k!nk∏i1nai−bibi!\Rightarrow \frac{k!}{n^k}\prod_{i1}^n\frac{a_i-b_i}{b_i!}⇒nkk!i1∏nbi!ai−bi 因为每种方案都要求和后面那个东西显然可以生成函数搞设 fz^(x)∑i0n(az−i)xii!∑i0∞azxii!−∑i0∞ixii!\widehat{f_z}(x)\sum_{i0}^n(a_z-i)\frac{x^i}{i!}\sum_{i0}^\infty a_z\frac{x^i}{i!}-\sum_{i0}^\infty i\frac{x^i}{i!}fz(x)i0∑n(az−i)i!xii0∑∞azi!xi−i0∑∞ii!xi
好像就搞不动了前面那个是azexa_ze^{x}azex其实后面那个把iii抵消掉阶乘就是xexxe^{x}xex fz(x)^(az−x)ex\widehat{f_z(x)}(a_z-x)e^xfz(x)(az−x)ex 然后F^∏i1nfz^\widehat{F}\prod_{i1}^n\widehat{f_z}F∏i1nfz可以暴力O(n2)O(n^2)O(n2)乘出∏i1n(az−x)\prod_{i1}^n(a_z-x)∏i1n(az−x)这部分记为∑i0∞cixi\sum_{i0}^{\infty}c_ix^i∑i0∞cixi。
然后展开后面的exe^xex就有 F(x)^[xk]∑i0kcink−i(k−i)!\widehat{F(x)}[x^k]\sum_{i0}^kc_{i}\frac{n^{k-i}}{(k-i)!}F(x)[xk]i0∑kci(k−i)!nk−i 然后 ans∑i0kcik!(k−i)!nians\sum_{i0}^kc_{i}\frac{k!}{(k-i)!n^i}ansi0∑kci(k−i)!nik!
就好了时间复杂度O(n2)O(n^2)O(n2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5100,P1e97;
ll n,k,f[N],ans;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{scanf(%lld%lld,n,k);f[0]1;for(ll i1;in;i){ll x;scanf(%lld,x);for(ll ji;j1;j--)f[j](f[j]*x-f[j-1]P)%P;f[0]f[0]*x%P;}ll tt1,invpower(n,P-2);for(ll i0;in;i){ans(ansf[i]*tt%P)%P;tttt*inv%P*(k-i)%P;}printf(%lld\n,(f[0]-ansP)%P);return 0;
}
