zcmimi's blog

查看原题

点击跳转

题意就是在[-n,n]中取k个整数,使他们和为0,求方案数

为了方便,我们可以理解为在[1,2n+1]中取k个整数,使他们和为k(n+1)

可以发现k\le 10

f(i,j)表示取i个数,和为j

f(i,j)=f(i,j-i)+f(i-1,j-i)

由于最大取到2(n+1),若j超出2(n+1)记得减去超出部分

#include<bits/stdc++.h>
int n,k,p,f[11][200011];
int min(int x,int y){return x<y?x:y;}
void solve(){
    scanf("%d%d%d",&n,&k,&p);
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int j=1;j<=k*(n+1);++j)
        for(int i=1;i<=k&&i<=j;++i){
            f[i][j]=(f[i][j-i]+f[i-1][j-i])%p;
            if(j>=(n+1)*2)f[i][j]=(f[i][j]-f[i-1][j-(n+1)*2]+p)%p;
        }
    printf("%d\n",f[k][k*(n+1)]%p);
}
int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
}
LG 4104 [HEOI2014]平衡
comment评论
Search
search