C. Card Game(dp&组合数)

C. Card Game(dp&组合数)

1.平局只有一种情况。

• 首先最大肯定在后手，不然先手直接赢。
• 然后次大肯定在先手 ，不然后手出牌的时候直接赢。
• 然后第三大肯定在先手，不然 先手若出次大，后手出最大接第三大，或者先手出其他，后手出第三大接最大。。
• 依此类推。

因为总情况一定$C(n,\frac{n}{2})$。

因此只需要计算先手赢的情况即可算出另一种情况。

考虑dp，利用前四大转移。

如果先手有最大直接赢，贡献是$C(i-1,\frac{2}{i}-1)$

然后考虑后手有最大的情况，那么显然先手必须有次大，不然会输。

已知先手次大，后手有最大。根据上面的情况可知第三大肯定也在先手。

接下来讨论论第四大情况，若在先手。先手可以先打次大，然后后手打最大，后手再打其他，先手打第三大，然后再打第四大赢。贡献为$C(i-4,\frac{i}{2}-1)$

然后是第四大在后手，那么先手会先打第三大，然后后手最大，然后后手会打第四大来消耗先手的次大，那么转移成了$dp(iz-4)$的情况。

因此可以dp。

预处理组合数。

时间复杂度：$O(n^2)$

#include 
#define ll long long
using namespace std;
const int N = 65, mod = 998244353;

int c[N][N];
int f[N];

void solve()
{
    int n;
    cin >> n;

    //组合数常见写法，从i中选j个
    for (int i = 0; i < N; i++){
        for (int j = 0; j <= i; j++){
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }

    f[2] = 1;
    f[4] = 3;
    for (int i = 6; i <= n; i += 2){
        f[i] = ((c[i - 1][i / 2 - 1] + c[i - 4][i / 2 - 1]) % mod + f[i - 4]) % mod;
    }
	
	//每次都要取模，不然就会溢出
    cout << f[n] << ' ' << (c[n][n / 2] - f[n] - 1 + mod) % mod << ' ' << 1 << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42