HDU4869：Turn the pokers（快速幂求逆元+组合数）

题意：

给出n次翻转和m张牌，牌相同且一开始背面向上，输入n个数xi，表示xi张牌翻转，问最后得到的牌的情况的总数。

思路：

首先我们可以假设一开始牌背面状态为0，正面则为1，最后即是求ΣC(m,k),k为所有能取到1的情况。首先我们要确认最后1的奇偶性。因为一次翻转0->1,或者1->0,则最后所有1的情况的奇偶性相同。然后我们要找到最小的1的个数i和最大的1的个数j，i为能翻1则翻1，j为能翻0则翻0，介于中间的情况是取偶数步数，一半翻1，一半翻0，保持1的个数不变。那么k为(i<=k<=j&&(k-i)&1==0)。

然后求组合数会涉及到一个求逆元的问题，可以采用快速幂或者打表，求逆元的方法我会最近补上。

-END-

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 #define LL __int64

 const int maxn=1e5+;

 const int MOD =1e9+;

 LL c[maxn];//记录C(n,i)

 LL pow_mod(LL n,LL p)//快速幂求逆元

 {

     LL s=;

     for(int i=p-;i;i>>=,n=n*n%MOD)

     {

         if(i&) s=s*n%MOD;

     }

     return s;

 } 

 int main()

 {

     int n,m;

     while(scanf("%d%d",&n,&m)==)

     {

         int i,j,k,x,p,q;

         i=j=;

         for(k=;k<n;k++)

         {

             scanf("%d",&x);

             //求最小1的个数

             if(i>=x) p=i-x;

             else if(j>=x) p=((i&)==(x&)?:);

             else p=x-j;

             //求最大1的个数

             if(j+x<=m) q=j+x;

             else if(i+x<=m) q=(((i+x)&)==(m&)?m:m-);

             else q=*m-(i+x);

             i=p;j=q;

         }

         LL ans=;

         c[]=;

         if(i==) ans+=c[];

         for(k=;k<=j;k++)

         {

             if(m-k<k) c[k]=c[m-k];

             else c[k]=c[k-]*(m-k+)%MOD*pow_mod(k,MOD)%MOD;

             if(k>=i&&(k&)==(i&)) ans+=c[k];

         }

         printf("%I64d\n",ans%MOD);

     }

 }

秒客网

HDU4869：Turn the pokers（快速幂求逆元+组合数）

相关文章