/**//* 看解题报告才懂的
题意:一排n个的座位,n个人(m个本地人,其余的为外地人) 每个人拿着自己的票从左进去,先找到自己的位置,如果该位置被占了,就往右走 直到空位就坐下,没有空位的话就被迫离开 m个本地人事先已有票了,现要对剩下的外地人安排,问有多少种方案,使得没有一个人离开 给出这m个人出现的顺序及票号 合法的方案指没有一个人离开,所以对于最后坐在什么位置不用管 而不同的方案指给剩下的m个外地人安排的票(a1,a2,am)不同 由上面两句话,知: "现在要做的,就是如何给(a1,a2am)赋值,使得没有一个人离开,而本地人也有顺序进场,但没关系, 那只会影响最后坐的位置而已,不影响合不合法。" 合法的充要条件: 票安排在位置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
搜索
最新评论
|
|