CF891E Lust

迈不过友情╰ 2023-08-17 17:29 117阅读 0赞

# CF891E Lust #

--------------------

鸽子更博了

Orz Itst

神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去最后的\\(\\prod a\_i\\)。证明感性理解。Orz Itst

然后可以套生成函数，如果第\\(i\\)个数选了\\(c\_i\\)次那么有\\(\\frac\{k!\}\{\\prod c\_i!\}\\)种选法。所以\\(f\_i(x)=\\sum\_\{j\\ge 0\}x^j\\frac\{a\_i-j\}\{j!\}\\)，可以套\\(e\\)进去。Orz Itst

多项式忘光了，Orz Itst

\\(f\_i(x)=\\sum\_\{j\\ge 0\}x^j\\frac\{a\_i-j\}\{j!\}=e^x(a\_i-x)\\)

要求\\(k!\\frac\{1\}\{n^k\}\[x^k\]\\prod f\_i(x)=k!\[x^k\]e^\{nx\}\\prod(a\_i-x)\\)。

\\(\\prod(a\_i-x)\\)是个\\(n\\)次多项式，那么只要求\\(e^\{nx\}\\)的第\\(k-n\\)到\\(k\\)项即可。

有一个\\(k!\\)不好算，注意\\(\[x^i\]e^\{nx\}=\\frac\{n^ix^i\}\{i!\}\\)，下面的阶乘和\\(k!\\)约分一下就可以算了。

#include<bits/stdc++.h> #define il inline #define vd void #define mod 1000000007 il int gi(){ int x=0,f=0;char ch=getchar(); while(!isdigit(ch))f^=ch=='-',ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return f?-x:x; } il int pow(int x,int y){ int ret=1; while(y){ if(y&1)ret=1ll*ret*x%mod; x=1ll*x*x%mod;y>>=1; } return ret; } int c[5010]; int main(){ #ifdef XZZSB freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n=gi(),k=gi(),mul=1; c[0]=1; for(int i=1;i<=n;++i){ int a=gi();mul=1ll*a*mul%mod; for(int j=n;~j;--j)c[j+1]=(c[j+1]-c[j]+mod)%mod,c[j]=1ll*c[j]*a%mod; } int ans=0,invn=pow(n,mod-2); for(int i=0,pn=1,fc=1;i<=n;fc=1ll*fc*(k-i)%mod,pn=1ll*pn*invn%mod,++i)ans=(ans+1ll*c[i]*fc%mod*pn%mod)%mod; printf("%d\n",(mul-ans+mod)%mod); return 0; }

转载于:https://www.cnblogs.com/xzz\_233/p/11348343.html

发表评论取消回复

表情：

评论列表（有 0 条评论，117人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 71 阅读

相关【构造】CF1761 E

[Problem - 1761E - Codeforces][] 题意： ![0622cda9a5a44fcfbb3df51c5babd8bc.png][] 思路：

缺乏、安全感/ 2024年03月23日 22:53/ 0 赞/ 81 阅读

相关【构造】CF1734 E

[Problem - 1734E - Codeforces][] 题意： ![434e61d374814555abe1a965962475f0.png][] 思路： !

超、凢脫俗/ 2024年03月23日 22:45/ 0 赞/ 57 阅读

相关构造——cf1214E

首先定义三元组（2\i-1,2\i,d），将n个三元组按d降序排列，然后取每个三元组的2\i-1连在一起，构成一条长为n-1的链然后降序枚举每个三元组，把对应的2\i在链上

深藏阁楼爱情的钟/ 2023年10月11日 09:04/ 0 赞/ 11 阅读

相关 CF891E Lust

CF891E Lust -------------------- 鸽子更博了 Orz Itst 神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去

迈不过友情╰/ 2023年08月17日 17:29/ 0 赞/ 118 阅读

相关 [CF1111E]Tree

题目大意：给一棵$n(n\\leqslant10^5)$个点的树，有$q(q\\leqslant10^5)$次询问，每次询问给出$k,m,r$表示把以下$k$个点分成不超过$m

素颜马尾好姑娘i/ 2021年12月22日 04:15/ 0 赞/ 210 阅读

相关 CF 166E Tetrahedron

E. Tetrahedron time limit per test 2 seconds memory limit per test 256 megabytes in

蔚落/ 2021年12月19日 14:35/ 0 赞/ 209 阅读

相关 CF1187E Tree Painting

思路：树形dp，首先使用dp计算以1为根的时候的最大分数，同时得到各个子树i的最大分数dp\[i\]。然后利用前面得到的dp数组分别计算以其他每个点作为根的时候的最大分数。

Bertha 。/ 2021年12月10日 17:49/ 0 赞/ 243 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 265 阅读

相关 CF813E Army Creation

昨天想了好久……现在想想是水题啊。首先对于一个区间，如果一个数出现的次数超过了$k$次，那么直接选$k$个这个数就好了。然后我们算一算每一个数对答案的贡献，对于第$i$个

ゝ一纸荒年。/ 2021年09月30日 01:12/ 0 赞/ 269 阅读