[HAOI2011] problem C

タイトルの説明
n人に席を手配して、まず一人に1~nの番号を付けて、i人目の番号をai(異なる人の番号は同じでもいい)にして、それから1人目から順番に席に着いて、i人目が来たらaiに座ってみて、aiが占拠されたらai+1を試して、ai+1も占拠されたらai+2を試して、・、n人目まで試してもだめなら、この手配案は合法ではない.しかし、m個人の番号はすでに確定しています(彼らはあなたの上司に賄賂を渡したかもしれません...).残りの人の番号を手配するしかありません.合法的な手配案を求めます.答えは大きいかもしれないので、Mで割った残りの数を出力するだけでいいです.
にゅうしゅつりょくけいしき
入力形式:
 
1行目の整数Tは、データ群数を表す
各データのセットについて、最初の行にはn、m、Mの3つの整数があります.
mが0でなければ、次の行にm対の整数があり、p 1、q 1、p 2、q 2、...、pm、qmであり、i対目の整数pi、qiが第pi個人を表す番号はqiでなければならない
 
出力フォーマット:
 
データのセットごとに1行ずつ出力し、解があればYESを出力し、整数でシナリオ数mod Mを表す.ただし、YESと数の間にはスペースが1つしかない.そうでなければNOを出力する
 
入出力サンプル
サンプル#1を入力:

2
4 3 10
1 2 2 1 3 1
10 3 8882
7 9 2 9 5 10

出力サンプル#1:

YES 4
NO

説明
100%のデータは、1≦T≦10、1≦n≦300、0≦m≦n、2≦M≦10^9、1≦pi、qi≦nを満たし、piが互いに異なることを保証する.
 
 
s[i]を前のi個の位置としていくつかの人選された場合、1つのスキームが合法的であり、すべてのiに対してs[i]>=iである場合にのみ発見される.
したがって,人選の順序を考慮するのではなく,位置dp,f[i][j]に従って前のi個の位置がj個の人選されたシナリオ数を表し,さらにO(N)を移すことができる.
では、もし誰かが席を予約したら?p[i]を前のiの位置に欽定された人数とすると、f[i][j]は合法的であり、j+p[i]>=iのみである.
 

#include
#define ll long long
using namespace std;
const int maxn=305;
int n,m,P,s[maxn],pos,lef,T;
int C[maxn][maxn],f[maxn][maxn];

inline int add(int x,int y){
	x+=y;
	return x>=P?x-P:x;
}

inline void init(){
	memset(f,0,sizeof(f));
	memset(s,0,sizeof(s));
	C[0][0]=1;
	for(int i=1;i<=300;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=add(C[i-1][j-1],C[i-1][j]);
	}
}

inline void dp(){
	for(int i=1;i<=n;i++) s[i]+=s[i-1];
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	    for(int j=max(0,i-s[i]);j<=lef;j++)
	        for(int l=0;l<=j;l++) f[i][j]=add(f[i][j],f[i-1][l]*(ll)C[lef-l][j-l]%P);
	        
}

int main(){
	scanf("%d",&T);
	while(T--){
    	scanf("%d%d%d",&n,&m,&P),lef=n-m;
	    init();
	    for(;m;m--) scanf("%d",&pos),scanf("%d",&pos),s[pos]++;
	    
		bool flag=1;
	    for(int i=1,tot=0;i<=n;i++){
	    	tot+=s[n-i+1];
	    	if(tot>i){
	    		flag=0,puts("NO");
	    		break;
			}
		}
		if(!flag) continue;
		
	    dp();
	    printf("YES %d
",f[n][lef]);
	}
	return 0;
}

　　
転載先:https://www.cnblogs.com/JYYHH/p/8793868.html