首页 > 代码库 > HDU 4869 Turn the pokers
HDU 4869 Turn the pokers
看完题解还wa了老半天才ac = =！囧rz 给大牛门跪了
因为本题求的是最后状态的种数，设最终翻到正面为1，反面为0：
因为每次翻牌的选择自由，所以一定范围内，翻到正面的牌数相差2的状态都可以取到；
（假设当前状态为i 个1，可以用一次翻到1的机会把另一个翻到1的牌翻到0；这样状态就是i-2，相差2了；同理可得i+2（设i，i-2，i+2都在范围内）
接下来就是求这个范围（1的个数）了：
设l 为范围的下界，r 为范围的上界；nl 为当前下界，nl 为当前上界；
当前可翻牌数为x ；
求下界：
若 x<=l ：nl = l-x；l 为前一次翻完后1的个数的最小值，若x<l，当前最小值便是 l-x；（把1翻为0）
若 x>l && x<=r ： nl = ( l &1 == x&1)?0:1；前一次翻完后状态可以为l,r 中间相差为2的所有值，所以当x与l，r相差为2的倍数时，为0，否则为1；
若 x>r ：nl = x-r ； 若x比最大值还大，则把所有1翻为0后又要把 x-r个0翻为1；
求上界：
若 x+r<=m ：nr=x+r；x加上最大值小于总数时，当前最大值就是 x+r；
若 x+r>m && x+l<=m：nr = (x+l )&1==m&1?m:m-1；前一次翻完后状态可以为l,r中间相差为2的所有值，所以当x+l 与m相差为2的倍数时，存在k，使x+k==m，否则只有 x+k==m-1，或x+k==m+1；
若 x+l>m ：nr=m-(x+l-m)=m*2-(x+l)；若x+l>m，则把所有0翻为1后还需把x+l-m个1翻为0；
知道范围后便是求所有状态的种数了，即组合排列问题；
一般来说，c(m,i)=c(m,i-1)*(m-i+1)/i；
但是本题为取模题；除法的取模运算并不像乘法一样简单；所以我们利用费马小定理来把除法取模转化为乘法：
费马小定理：a^(p-1)≡1(mod p); p为质数；
所以 a^(p-2)=a^-1 (mod p)
所以 原式中 /i 的部分可以转化为 *i^-1(mod p)=*i^(p-2) (mod p)
因为本题为模 1e9+9，是质数。。。所以p=1e9+9；
这部分可以用快速幂取模来得到；
所以 c(m,i)=c(m,i-1)*(m-i+1) *i^(p-2) ;
即 c(m,i)=c(m,i-1)*(m-i+1) %p *pow_mode (i,p-2) %p ;
ps：开始wa到不行，所以从大牛们博客里扒了些代码混杂自己的代码交上去a过一发 orz；发现错误后，看懂题解后自己又写了一发交上去了；
这是自己写的，居然也还改了两三次 囧rz
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 typedef long long ll; 7 8 const ll mod = 1e9+9; 9 10 ll pow_mode (ll a,ll b){11 ll temp=a;12 ll s=1;13 while (b){14 if (b&1)15 s=(s*temp)%mod;16 b/=2;17 temp=(temp*temp)%mod;18 }19 return s;20 }21 22 int main (){23 ll n,m;24 ll c[100005];25 while (cin>>n>>m){26 ll x,ans;27 ll l,r,nl,nr;28 l=r=nl=nr=0;29 while (n--){30 cin>>x;31 if (x<=l) nl=l-x;32 else if (x<=r) nl=(x&1)==(l&1)?0:1;33 else nl=x-r;34 if (r+x<=m) nr=r+x;35 else if (l+x<=m) nr=((l+x)&1)==(m&1)?m:m-1;36 else nr=m*2-(l+x);37 l=nl;r=nr;38 }//cout<<l<<" "<<r<<endl;39 c[0]=1;40 ans=0;41 for (int i=0;i<=r;i++){42 if (i){43 if (i*2<=m)44 c[i]=((c[i-1]*(m-i+1))%mod*pow_mode (i,mod-2))%mod;45 else c[i]=c[m-i];46 }47 if ((i&1)==(l&1)&&i>=l)48 ans=(ans+c[i])%mod;49 }50 cout<<ans%mod<<endl;51 }52 return 0;53 }