首页 > 代码库 > HDOJ--4869--Turn the pokers【组合数学+快速幂】
HDOJ--4869--Turn the pokers【组合数学+快速幂】
链接:http://acm.hdu.edu.cn/showproblem.php?pid=4869
题意:有m张扑克,开始时全部正面朝下,你可以翻n次牌,每次可以翻xi张,翻拍规则就是正面朝下变背面朝下,反之亦然,问经过n次翻牌后牌的朝向有多少种情况。
这道题在比赛时我们只开了个头,却无从下手。我看了网上的解题报告,说的都比较简单,对于我这名菜鸟来说也想了比较长的时间才想明白,所以我想写的清楚一些日后再看还能看的很清晰。
思路是这样,每张牌翻奇数次必然是正面朝上,翻偶数次则还是正面朝下。现在用0表示初始状态(正面朝下),1表示正面朝上,可以根据n次翻牌的个数找出1的下限和上限,然后再在这个范围里用组合数学就ok了,比赛时就是想到了这里,找范围没有想出来。
这道题可以分为两部分:先是找到1的上限和下限,然后是计算出 c ( m , i ) 的值依次相加。
第一部分:
minm = maxm = 0; p = q = 0; for(i=0;i<n;i++){ scanf("%d",&x); if(minm>=x) p = minm - x; //一 else if(maxm>=x) p = ((x&1)==(minm&1))?0:1; //二 else p = x - maxm; //三 if(maxm+x<=m) q = maxm + x; //四 else if(minm+x<=m) q = (((minm+x)&1)==(m&1))?m:m-1; //五 else q = 2 * m - (x + minm); //六 minm = p; maxm = q; }minm表示下限,maxm表示上限,p、q分别记录当前上下限,然后更新到minm、maxm中。x是输入的第i次翻牌的数量
第一组if语句是判断下限的。
①:当前下限大于等于现在翻牌的数量,这个比较好理解,全翻1,1变成0,则剩下的1就是minm-x
②:当前下限小于翻牌数量,上限大于等于翻牌数量,因为翻牌数量刚好在上下限之间,所以最少可以把正面朝上的数量减为零,但不是绝对能减到0,因为有可能当前正面朝上的牌时奇数,而翻牌数量是偶数,所以要判断奇偶性是否一样,为什么要和minm比较奇偶性,后面会说。
③:翻牌数量比上限还大的时候,直接减去上限就是下限,也不难理解
④:上限+翻牌数量没有达到总牌数时,上限+翻牌数量就是新的上限,全翻0,这样使1最多
⑤:上限+翻牌数量大于总牌数,而下限+翻牌数量小于等于总牌数,前者可以说是翻牌溢出了,已经全是1再翻的话只会让一些1变成0,后者没有达到全变成1的情况。它们是一个上限一个下限,这说明可以处理到在这之间的情况,那么最好的结果是所有牌都正面朝上,全是1,和②的情况一样,需要判断奇偶性是否一致,这回和m比较,应该比②的好理解
⑥:上限+翻牌数、下限+翻牌数全都大于总牌数时,说明都会溢出,那就用2 * m - (x + minm)来表示上限,因为(x+minm)小,所以溢出的1变成0的牌数少。我之前用max(maxm + x - m, 2 * m - (x + minm))来表示⑥的上限,结果WA了,其实是我想错了,maxm + x - m是1变成0的牌的数量,而要找的是1的上限。
第二部分:
c[0] = 1; for(i=1;i<=maxm;i++){ if(m-i<i) c[i] = c[m-i]; else{ c[i] = c[i-1] * (m-i+1) % MOD * mode((ll)i,MOD-2) % MOD; } }其中mode是快速幂取模函数,数组c表示组合数学 c ( m , i ) , 按理说 c[ i ] = c[ i - 1 ] * ( m - i + 1 ) / i ,然后这个数对MOD取模,但是存在除法取模就不是这么简单的分解了,以前做数论题应该遇到过,只不过太久没做给忘了。。。
费马小定理是这样: a^(p-1) ≡1(mod p),p为质数,a、p互质,a^(p-1) mod p 恒等于1。
变换一下,两边同时除以a ,变成 a^(p-2)=a^(-1)(mod p),所以要除以a 就可以表示成 乘 a^(p-2),所以有了如上的写法。
最后将组合数学值相加的时候,要隔一个相加,不难发现上限和下限的奇偶性一样,并且每种结果1的数量的奇偶性一定和上限下限的奇偶性一样,这个可以自己推
我以列的方式表示牌的情况,O表示翻哪个牌,假设现在有7张牌,翻两次,第一次翻4张,第二次翻三张
不论你怎么变化,每次翻完牌正面朝上的总是奇数个或偶数个,其他情况可以自己推,得到这个结论。
现在说说第一部分的②,其实应该和你现在更接近的那种情况去比较奇偶性,但是相比于某种中间情况,上下限的奇偶性更容易判断,而且中间每种情况的奇偶性都和上下限一样,所以可以x可以和minm比较奇偶性,当然,和maxm比较也可以,因为他们奇偶性一样。
完整代码:
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 100100 #define eps 1e-7 #define MOD 1000000009 #define INF 0x7FFFFFFF #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; ll c[MAXN]; ll mode(ll a,int n){ ll t = a; ll ans = 1; while(n){ if(n & 1){ ans = ans * t % MOD; } n >>= 1; t = t * t % MOD; } return ans; } int main(){ int n,m,minm,maxm,i,j,x,p,q; while(scanf("%d%d",&n,&m)!=EOF){ minm = maxm = 0; p = q = 0; for(i=0;i<n;i++){ scanf("%d",&x); if(minm>=x) p = minm - x; else if(maxm>=x) p = ((x&1)==(minm&1))?0:1; else p = x - maxm; if(maxm+x<=m) q = maxm + x; else if(minm+x<=m) q = (((minm+x)&1)==(m&1))?m:m-1; else q = 2 * m - (x + minm); minm = p; maxm = q; } ll ans = 0LL; c[0] = 1; for(i=1;i<=maxm;i++){ if(m-i<i) c[i] = c[m-i]; else{ c[i] = c[i-1] * (m-i+1) % MOD * mode((ll)i,MOD-2) % MOD; } } for(i=minm;i<=maxm;i+=2){ ans += c[i]; ans %= MOD; } cout<<ans<<endl; } return 0; }