bzoj2302 problem c 遞推

       （吐槽請無視：自從寫STL卡到吐之後寫題就一直狂WA,TLE,RE不止，woc我真是沒救了）。

       不難發現方案符合條件的充分必要條件是：對于任意的i，都有編号<=i的人的個數>i=。那麼用f[i][j]表示有j個人，他們的編号都在1..i之間時的方案數。顯然f[i][j]>0僅當j>=i，然後枚舉編号為i的人的個數，顯然可以得到下述轉移方程：

       f[i][j]=Σ(k=已經确定得編号為i的人的個數,j)f[i-1][j-k]*C(現在還可以選的人的總數，目前位置還沒有确定的人的個數)

AC代碼如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 305
#define ll long long
using namespace std;

int n,m,p,a[N],sum[N],f[N][N],c[N][N];
void pfs(){
	int i,j; memset(c,0,sizeof(c)); c[0][0]=1;
	memset(a,0,sizeof(a)); memset(f,0,sizeof(f));
	for (i=1; i<=n; i++){
		c[i][0]=1;
		for (j=1; j<=i; j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
	}
}
int main(){
	int cas; scanf("%d",&cas);
	while (cas--){
		scanf("%d%d%d",&n,&m,&p); int i,j,k; pfs();
		for (i=1; i<=m; i++){
			int x,y; scanf("%d%d",&x,&y);
			a[y]++;
		}
		f[0][0]=1; sum[0]=n-m;
		for (i=1; i<=n; i++){
			sum[i]=sum[i-1]+a[i];
			if (sum[i]<i){ puts("NO"); break; }
		}
		if (i<=n) continue;
		for (i=1; i<=n; i++)
			for (j=i; j<=sum[i]; j++)
				for (k=a[i]; k<=j-i+1; k++)
					f[i][j]=(f[i][j]+(ll)f[i-1][j-k]*c[sum[i-1]+k-j][k-a[i]]%p)%p;
		printf("YES %d\n",f[n][n]);
	}
	return 0;
}
           

by lych

2016.2.26