luogu4707 重返现世

Source and Judge

luogu4707

Record

2h

Analysis

请先思考后再展开

首先你需要熟悉kth-minmax容斥,我写了教程,自行搜索

主要难点应该是考虑S的增大,用组合数 $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$ ,所以状态多个n-k就好了

剩下的难点主要是初始化……但这个我好像没啥好说的

时间复杂度为 $O(nm(n-k))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void add(int &x,int y){x=(1ll*x+y)%MOD;}
int f[11][10010],a[N];
void main()
{
int n=qread(),k=qread(),m=qread();for(int i=1;i<=n;i++) a[i]=qread();
for(int i=0;i<=n-k;i++) f[i][0]=-1;
for(int i=1,t=1;i<=n;i++,t^=1)
for(int ss=10000-a[i];ss>=0;ss--)
{
add(f[0][ss+a[i]],-f[0][ss]);
for(int nk=1;nk<=10;nk++) add(f[nk][ss+a[i]],f[nk-1][ss]-f[nk][ss]);
}
ll ans=0;for(int ss=1;ss<=10000;ss++) ans+=(ll)f[n-k][ss]*m%MOD*invm(ss),ans%=MOD;
write((ans+MOD)%MOD);
}//x+MOD

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ee60.html
转载请注明出处,谢谢!