Codeforces Round #195 (Div. 2) D题Vasily the Bear and Beautiful Strings

这场CF，脑子乱死啊。。。C题，搞了很长时间，结束了，才想到怎么做。B题，没看，D题，今天看了一下，很不错的组合题。

如果n和m都挺多的时候

以下情况都是变为1，根据偶数个0，最后将会为1，奇数个0，最后变为0，以1开头，全都是0.

0 1..

0 0 0 1....

0 0 0 0 0 1....

总的情况是C(n+m,m)，算1也可以算出来。注意m = 1的时候特判，0的时候，我也全写的特判。

10^5的组合数，用费马小定理求逆元。看了下题解，题解直接来了个逆元。。

inv(a) = a^(mod-2)，完全没看懂，查了查资料，明白了。。

a*inv(a) 模 mod = 1

因为mod是素数，根据费马小定理，a的p-1次方对 p取余等于1， a^(mod-2)肯定是逆元。

算组合数，好高端啊。。。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 #define MOD 1000000007
 8 #define LL __int64
 9 LL fact[200101];
10 LL fastmod(LL a,LL k)
11 {
12     LL b = 1;
13     while(k)
14     {
15         if(k&1)
16         b = a*b%MOD;
17         a = (a%MOD)*(a%MOD)%MOD;
18         k = k/2;
19     }
20     return b;
21 }
22 LL comb(int n,int m)//如果取余是素数，根据费马小定理求逆元，快速求组合数
23 {
24     LL ans,a;
25     ans = fact[n];
26     a = fastmod((fact[n-m]*fact[m])%MOD,MOD-2);
27     return (ans*a)%MOD;
28 }
29 int main()
30 {
31     int i,n,m,g;
32     LL ans,res;
33     scanf("%d%d%d",&n,&m,&g);
34     if(m == 0)
35     {
36         if(n%2 == 0)
37         {
38             printf("%d
",g);
39         }
40         else
41         {
42             printf("%d
",!g);
43         }
44         return 0;
45     }
46     if(n == 0)
47     {
48         if(m == 1&&g == 1)
49         printf("1
");
50         else if(m == 1&&g == 0)
51         printf("0
");
52         else if(m > 1&&g == 0)
53         printf("1
");
54         else
55         printf("0
");
56         return 0;
57     }
58     fact[0] = 1;
59     for(i = 1;i <= n+m;i ++)
60     {
61         fact[i] = (fact[i-1]*i)%MOD;
62     }
63     ans = comb(n+m,n);
64     res = 0;
65     for(i = 1;i <= n;i += 2)
66     {
67         if(m == 0) break;
68         if(i + 1 == n+m) break;
69         res = (res + comb(n+m-i-1,m-1))%MOD;
70     }
71     if(m == 1&&n%2 == 0)
72     res ++;
73     if(g == 1)
74     printf("%I64d
",res);
75     else
76     {
77         ans = (ans - res + MOD)%MOD;
78         printf("%I64d
",ans);
79     }
80     return 0;
81 }