首页 > 代码库 > HDU-4869 Turn the pokers

HDU-4869 Turn the pokers

2024-07-15 10:44:29   219人阅读

      原题:  Turn the pokers

      思路:假设正面为0，反面为1。牌就像这样 000000....... 。考虑到假如可以实现最终反面个数为m, 牌共n张, 则这n张排任取m个为反面其余都为正面的状况都能实现。于是转化为考虑最终可能出现1的个数的集合有哪些。
      因为可能的个数集合是连续的(在最大最小值之内相差2的都可能), 所以每一次翻转之后的上下限都可以根据上一次所得的上下限推出。
      最后算排列组合的适合需要用到组合数递推公式和费马小定理推论\( a^{p-2} \equiv a^{-1} \bmod p \) , 通过快速幂的方法算一下逆元。

      其实TLE了n次。。。。。。用位运算简化了一下。。。而且输入那个部分要用scanf才够快。

 

  1 #include <iostream>
  2 #include <fstream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <algorithm>
  6 #include <cmath>
  7 //#define LOCAL
  8 #define fin cin
  9 #define fout cout
 10 #define LL long long int
 11 #define maxn 100000+5
 12 using namespace std;
 13 LL MM=1000000009;
 14 LL C[maxn];
 15 LL quickmod(LL a,int b)
 16 {
 17    LL ans=1,base=a;
 18 
 19    while(b!=0)
 20    {
 21      if(b&1)
 22      {
 23         ans=ans*base%MM;
 24     }
 25     b>>=1;
 26     base=base*base%MM;
 27 }
 28 
 29 return ans;
 30 }
 31 int main ()
 32 {
 33 #ifdef LOCAL
 34     ofstream fout ("1.out");
 35     ifstream fin ("1.in");
 36 #endif
 37 
 38     int i,j,k;
 39     int n,m,x;
 40 
 41     memset(C,0,sizeof(C));
 42 
 43     while(fin>>n>>m)
 44     {
 45 
 46         int left,right,a1,a2;
 47         left=0; right=0;
 48 
 49         for(i=0;i<n;i++)
 50         {
 51             scanf("%d",&x);
 52 
 53 
 54             if(x<=left){ a1=left-x; }
 55             else if(x<=right)
 56                 {   a1= ((left&1)==(x&1))?0:1;
 57                 }
 58                 else{
 59                     a1=x-right;
 60                 }
 61 
 62                 if(x<=m-right){ a2=right+x; }
 63                 else if(x<=m-left)
 64                 {
 65                     a2 = (((m-left)&1) == (x&1)?m:m-1);
 66                 }
 67                 else{
 68                     a2=2*m-(x+left);
 69                 }
 70 
 71                 left=a1;right=a2;
 72 
 73             }
 74 
 75 
 76             C[0]=1; C[m]=1;
 77 
 78             for(i=1;i<=m/2+1;i++)
 79                 {C[i]=C[i-1]*(m-i+1)%MM*quickmod(i,MM-2)%MM;
 80 
 81                    C[m-i]=C[i];
 82                }
 83 
 84 
 85                LL sum = 0;
 86                for(i = left; i<=right; i+=2)
 87                 { sum+=C[i];
 88                   sum%=MM;
 89               }
 90 
 91               fout<<sum<<endl;
 92           }
 93 
 94 
 95 #ifdef LOCAL
 96           fin.close();
 97           fout.close();
 98 #endif
 99 
100           return 0;} 


联系
我们