 /**//*
看解题报告才懂的

题意:一排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
搜索
最新评论

|
|