 /**//*
看解題報告才懂的

題意:一排n個的座位,n個人(m個本地人,其余的為外地人)
每個人拿著自己的票從左進去,先找到自己的位置,如果該位置被占了,就往右走
直到空位就坐下,沒有空位的話就被迫離開
m個本地人事先已有票了,現要對剩下的外地人安排,問有多少種方案,使得沒有一個人離開
給出這m個人出現的順序及票號
合法的方案指沒有一個人離開,所以對于最后坐在什么位置不用管
而不同的方案指給剩下的m個外地人安排的票(a1,a2 ,am)不同
由上面兩句話,知:
"現在要做的,就是如何給(a1,a2 am)賦值,使得沒有一個人離開,而本地人也有順序進場,但沒關系,
那只會影響最后坐的位置而已,不影響合不合法。"
合法的充要條件:
票安排在位置pos的數目 <= pos之后剩下的空座位 + 1

dp[n,m]表示合法的安排使得n之后還有m個空座位
“DP with ak,m = # of valid assignments to positions k; : : : ; n with m available slots”
轉移就是枚舉有多少張票是在位置n的
在位置n的票 = 本地 + 外地
num[n]表示在位置i的本地的票,sum[n]表示i即之前的本地的票的總數
現在可選的外地人 free = n - sum[n] + addtional
轉移:
m+1
dp[n,m] = ∑C[free,i-num[n]] * dp[n-1,m+1-i]
num[n]
*/
#include<cstdio>
#include<cstring>

int N,M,MOD;

int dp[310][310],C[310][310];
int num[310],sum[310];

int memo(int n,int add)
  {
if(num[n] > add+1)return 0;

if(n==1)return 1;
int &ans = dp[n][add];
if(ans!=-1)return ans;

ans = 0;
int free = n-sum[n]+add;//free foreign can select
for(int i = num[n]; i<=add+1;i++)//選取i-num[n]個外地人的票是位置n的
 {
ans = (ans + (long long)C[free][i-num[n]]*memo(n-1,add+1-i))%MOD;
}
return ans;
}

bool possible()//可行 <==> 票安排在pos處的人 <= pos之后多余的位置add + 1
  {
int add = 0;
for(int i=N;i;i--)
 {
if(num[i]>add+1)return false;
add = add+1-num[i];
}
return true;
}
int main()
  {
#ifdef ONLINE_JUDGE
#else
freopen("in","r",stdin);
#endif

int T;
for(scanf("%d",&T);T--;)
 {
scanf("%d%d%d",&N,&M,&MOD);

memset(num,0,sizeof(num));
for(int i=1;i<=M;i++)
 {
int t,pos;
scanf("%d%d",&t,&pos);
num[pos]++;
}
sum[0] = 0;
for(int i=1;i<=N;i++)
sum[i] = sum[i-1] + num[i];

if(!possible())
 {
puts("NO");
continue;
}

memset(dp,-1,sizeof(dp));
for(int i=0;i<=N;i++)
 {
C[i][0] = C[i][i] = 1;
for(int j=1;j<i;j++)
C[i][j] = (C[i-1][j]+C[i-1][j-1])%MOD;
}
printf("YES %d\n",memo(N,0));
}
return 0;
}

 /**//*
ipsc 2009 有一道類似的,不過是沒有限制的
座位K個,人數N個,問多少種情況的票的序列會沖突。
數據很大,不能dp,組合推導
解題報告:
N>K肯定不行。只考慮K>=N
總的數目為K^N
考慮多少種情況不會沖突,即沒有人離開的

多加一個座位K+1,然后這K+1個座位形成一個環。每個人的票有K+1種,所以有(K+1)^N種可能
由于形成了環了,沒人離開,每一次會剩下(K+1-N)個位置是空的
(K+1)^N種可能,則總共有C = (K+1-N)*(K+1)^N次位置空了,每個位置空的情況就有C/(K+1)種了(第K+1個位置也是)
所以合法的方案數就為: (K+1-N)*(K+1)^(N-1)
答案就為 K^N - (K+1-N)*(K+1)^(N-1)

zoj 3404要用到上面的公式
可以理解成,有多少種序列(每個點的值屬于[1,N]),最終能夠變為排列1,2, N
*/
|
|
常用鏈接
隨筆分類
Links
搜索
最新評論

|
|