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

이 CF, 머리 가 복잡 해...C 문 제 는 오 랜 시간 동안 풀 었 다가 끝나 서 야 어떻게 풀 어야 할 지 생각 났 다.B 문제, 안 봤 어 요. D 문제, 오늘 봤 어 요. 괜 찮 은 조합 문제 예요.
하면, 만약, 만약...
아래 의 상황 은 모두 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 }