$[HAIO2011]ProblemC$

\([HAIO2011]ProblemC\)

考虑无解的情况，实际上可以证明，仅在这种情况下会无解（然而我只会口胡……

对于一开始给出的\(m\)个固定的人，记\(Sum[i]\)为编号\(\geq i\)的人的个数。

如果有\(Sum[i]>n-i+1\)，则一定无解。

此时我们容易考虑到\(DP\)，\(f[i][j]\)为在剩下的中\(\geq i\)个已确定有\(j\)个的方案数。
\[ f[i][j]=\sum_{k=0}^jf[i+1][j-k]*{j \choose k}(0\leq j\leq n-Sum[i]-i+1) \]
意思是我们现在有\(j-k\)个已确定为\(\geq i+1\)，再钦定\(k\)个\(=i\)即可。（注意每个人不同，所以用了组合数）

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int f=1,w=0;char x=0;
    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
    return w*f;
}
const int N=310;
int n,m,p,Sum[N],f[N][N],C[N][N];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("A.in","r",stdin);
#endif
    int T=read();
    while(T--)
    {
        memset(f,0,sizeof(f));memset(Sum,0,sizeof(Sum));
        int Jud=0;n=read(),m=read(),p=read();
        for(int i=1,x;i<=m;i++) x=read(),Sum[read()]++;
        for(int i=n;i;i--)
        {
            Sum[i]+=Sum[i+1];
            if(Sum[i]>n-i+1) {Jud=1;break;}
        }
        if(Jud) {puts("NO");continue;}
        for(int i=0;i<=n;i++) C[i][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                C[i][j]=(C[i-1][j]%p+C[i-1][j-1]%p)%p;
        f[n+1][0]=1;
        for(int i=n;i;i--)
            for(int j=0;j<=n-Sum[i]-i+1;j++)
                for(int k=0;k<=j;k++)
                    f[i][j]=(f[i][j]+(f[i+1][j-k]%p*C[j][k]%p)%p)%p;
        printf("YES %lld\n",f[1][n-m]);
    }
}

$[HAIO2011]ProblemC$

原文：https://www.cnblogs.com/wo-shi-zhen-de-cai/p/11657177.html