【hdu3544】 Alice's Game

给一块n*m的巧克力，Alice只能垂直切，切成A*m和B*m,并且A+B=n,Bob只能横切，只能切成A*n和B*n，并且A+B=m。

对于n*n的这种巧克力，谁先切了第一刀，就直接让对方有切两刀的机会，所以Alice不可能去切这种巧克力，可以直接无视这种。

后一人会尽量选前一人切后小的一块切。

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 
 9 typedef long long LL;
10 
11 #define N 1000010
12 #define MOD 1000000007
13 
14 int t;
15 int n;
16 
17 LL f[N],d[N];
18 
19 inline LL qpow(LL a,LL b)
20 {
21     LL ans=1;
22     while (b)
23     {
24         if (b&1)
25             ans=(1LL*ans*a)%MOD;
26         b>>=1;
27         a=(1LL*a*a)%MOD;
28     }
29     return ans;
30 }
31 
32 inline LL C(LL x,LL y)
33 {
34     return f[x]*d[y]%MOD*d[x-y]%MOD;
35 }
36 
37 inline LL Catalan(LL x)
38 {
39     return (C(x<<1,x)-C(x<<1,x-1)+MOD)%MOD;
40 }
41 
42 int main()
43 {
44     freopen("move.in","r",stdin);freopen("move.out","w",stdout);
45     scanf("%d",&t);
46     f[0]=1;
47     for (int i=1;i<=1000000;i++)
48         f[i]=f[i-1]*i%MOD;
49     for (int i=0;i<=1000000;i++)
50         d[i]=qpow(f[i],MOD-2)%MOD;
51     while (t--)
52     {
53         scanf("%d",&n);
54         LL ans=0;
55         for (int i=0;i<=n;i+=2)
56             ans+=C(n,i)*Catalan(i>>1),ans%=MOD;
57         printf("%lld
",ans);
58     }
59     return 0;
60 }
61 
62