C++14(g++5.4) 解法, 执行用时: 930ms, 内存消耗: 1912K, 提交时间: 2020-02-15 20:56:20

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 310
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-0x30;
    return f*x;
}
ll n, m, mod, res[maxn], C[maxn][maxn], f[maxn][maxn], s[maxn][maxn];
int main()
{
    ll i, j, k, T=read(), ans;
    while(T--)
    {
        n=read(), m=read(), mod=read();
        rep(i,1,n)res[i]=n-i+1;
        rep(i,1,m)
        {
            ll p=read(), q=read();
            rep(j,1,q)res[j]--;
        }
        rep(i,0,n)C[i][0]=1;
        rep(i,1,n)rep(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        rep(i,1,n)if(res[i]<0){printf("NO\n");break;}if(i<=n)continue;
        printf("YES ");
        if(n==m){printf("1\n");continue;}
        ans=1;
        cl(f);
        f[1][res[1]]=1;
        rep(i,2,n)rep(j,1,res[i])
        {
            rep(k,j,n)f[i][j]+=f[i-1][k]*C[k][j]%mod;
            f[i][j]%=mod;
            (ans+=f[i][j])%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 518ms, 内存消耗: 2664K, 提交时间: 2020-04-02 12:48:20

#include<cstdio>
#include<cstring>
const int MAXN=399;
int n,m,M,cnt[MAXN],sum[MAXN],i;
long long c[MAXN][MAXN],f[MAXN][MAXN];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(cnt,0,sizeof(cnt));
		memset(sum,0,sizeof(sum));
		memset(f,0,sizeof f);
		scanf("%d%d%d",&n,&m,&M);
		for(i=0;i<=n;i++)
		c[i][0]=c[i][i]=(1%M);
		for(i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
		c[i][j]=(c[i-1][j]+c[i-1][j-1])%M;
		for(i=1;i<=m;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			cnt[y]++;
		 } 
		 sum[0]=n-m;
		 for(i=1;i<=n;i++)
		 {
		 	sum[i]=sum[i-1]+cnt[i];
		 	if(sum[i]<i)
		 	{
		 		puts("NO");
		 		break;
			 }
		 }
		 if(i!=(n+1))
		 continue;
		 f[0][0]=1;
		 for(i=1;i<=n;i++)
		 for(int j=sum[i];j>=i;j--)
		 for(int k=j-i+1;k>=cnt[i];k--)
		 f[i][j]=(f[i][j]+f[i-1][j-k]*c[sum[i]-(j-k)-cnt[i]][k-cnt[i]])%M;
		 printf("YES %lld\n",f[n][n]);
	}
	return 0;
}