zcmimi's blog

查看原题

点击跳转

s_i为已经确定的m人中编号不小于i的个数

若存在s_i>n-i+1,显然无解

考虑动态规划,设f(i,j)表示剩下n-m个人中有j个人编号不小于i

\displaystyle f(i,j)=\sum_{k=0}^j f(i+1,j-k)\cdot {j\choose k}, 其中j\le n-s_i-i+1

最终答案为f(1,n-m)

#include<bits/stdc++.h>
const int N=311;
int n,m,M,c[N][N],s[N],f[N][N];
void solve(){
    memset(f,0,sizeof f);
    memset(s,0,sizeof s);
    // memset(c,0,sizeof c);
    scanf("%d%d%d",&n,&m,&M);
    c[0][0]=1;
    for(int i=1;i<=n;++i){
        c[i][0]=1;
        for(int j=1;j<=i;++j)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%M;
    }
    for(int i=1,x,y;i<=m;++i)
        scanf("%d%d",&x,&y),++s[y];
    for(int i=n;i;--i)
        if((s[i]+=s[i+1])>n-i+1)
            return puts("NO"),void();
    f[n+1][0]=1;
    for(int i=n;i;--i)
        for(int j=0;j<=n-s[i]-i+1;++j)
            for(int k=0;k<=j;++k)
                f[i][j]=(f[i][j]+1ll*f[i+1][j-k]*c[j][k])%M;
    printf("YES %d\n",f[1][n-m]);
}
int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
}
LG 2523 [HAOI2011]Problem c
comment评论
Search
search