原题: 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=;
14 LL C[maxn];
15 LL quickmod(LL a,int b)
16 {
17 LL ans=,base=a;
18
19 while(b!=)
20 {
21 if(b&)
22 {
23 ans=ans*base%MM;
24 }
25 b>>=;
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,,sizeof(C));
42
43 while(fin>>n>>m)
44 {
45
46 int left,right,a1,a2;
47 left=; right=;
48
49 for(i=;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&)==(x&))?:;
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)&) == (x&)?m:m-);
66 }
67 else{
68 a2=*m-(x+left);
69 }
70
71 left=a1;right=a2;
72
73 }
74
75
76 C[]=; C[m]=;
77
78 for(i=;i<=m/+;i++)
79 {C[i]=C[i-]*(m-i+)%MM*quickmod(i,MM-)%MM;
80
81 C[m-i]=C[i];
82 }
83
84
85 LL sum = ;
86 for(i = left; i<=right; i+=)
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
return ;}