CF1739C Card Game

题目地址

题意：有n(n为偶数)张大小不同的卡牌，现在A和B玩一个游戏，规则是如果一个人出示了一张卡牌，另一个人无法出示更大的卡牌，他就赢了，如果反之该回合结束，并将这两张牌移除（移入墓地bushi），由另一个人先出示卡牌，如果牌全部出示完了，那么就算平局，现在问如果最开始由A出示，分别有多少种发牌方式使得A赢，B赢以及平局。

Solution

组合数学，如果A赢，那么他必须拿到第一大的牌，或者每去掉四张牌的第一大和之前去掉的牌中最接近这张牌的（例如[1,2,3,4,5,6,7,8]中必须拿到8或者567或者467）

对于平局的情况，只有一种，B拿到第一大的牌，A拿到第二三大的牌，B拿到第四五大的牌，以此类推

剩下的情况就是B赢的

 1 void init()
 2 {
 3     fac[0]=1;
 4     for(int i=1;i<=60;i++)
 5     {
 6         fac[i]=(fac[i-1]*i)%mod;
 7     }
 8     inv[60]=ksm(fac[60],mod-2);
 9     for(int i=59;i>=0;i--)
10     {
11         inv[i]=(inv[i+1]*(i+1))%mod;
12     }
13 }
14 
15 int C(int n,int m)
16 {
17     if(n<m||n<0||m<0)return 0;
18     else return ((fac[n]*inv[n-m])%mod*inv[m])%mod;
19 }
20 
21 
22 void solve()
23 {
24     init();
25     int n;cin>>n;
26     int cnt1=C(n-1,(n/2)-1);
27     int aa=n/2-2;
28     int cnt=1;
29     while(aa>0)
30     {
31         cnt1=((cnt1+C(n-4*cnt,aa-1))%mod+C(n-4*cnt-1,aa-1))%mod;
32         aa-=2;
33         cnt++;
34     }
35     int cnt2=((C(n,n/2)-cnt1)%mod-1)%mod;
36     cnt2=(cnt2+mod)%mod;
37     cout<<cnt1<<" "<<cnt2<<" ";
38     cout<<"1\n";
39 }