题解：P10968 扑克牌

· · 题解

建议评蓝。

想爽了。有趣数数题。

考虑把位置作为阶段，那么我们的决策就是目前在这个位置上放什么牌。为了知道目前放什么牌，所以我们要知道目前手上有的牌和上一个位置的牌。

如果我们把每种花色、面值不同的牌都记录下来，那么状态数就是 O(2^nn) 的，显然我们没办法接受。

`2C AD AC JC JH` 该怎么排列？有两个 `A` 和 `J`。 第一组：`2C AD JC JH AC`。 第二组：`2C AC JC JH AD`。 欸，这个 `A` 两个不同花色的是不是换了个位置。等下，是不是我随便排列同样面值的所有牌构造的序列还是合法的？

此时我们就有了第一个观察：

以下称同一面额的牌为同一种牌。

好了，现在我们只在乎不同面值牌的摆放情况，拿这个乘上不同面值牌数量的阶乘的积即可。

这样我们的状态是 O(4^mm) 的，其中 m 是牌面值种类的个数，转移是 O(m) 的，总体是 O(4^mm^2) 的。

然而这样仍然不足以通过此题。

当然可以找到。

举个例子，J 有两张，K 有一张这种情况的方案数与 K 有两张，J 有一张这种情况的方案数相等。原因是我们并不在乎具体牌是什么面值。

因此，我们有状态是 f_{p,i,j,k,l}，其中 p 表示我们除去当前位置填的那种牌现在还剩多少张（倒退意义下），i,j,k,l 分别表示放置的 1,2,3,4 张牌的不同种类牌的个数。

那么状态个数就是 O(m^4)，转移是 O(1) 的。我们可以先预处理计算出 f 数组，多测时直接 O(n) 输出即可。

具体转移方程见代码，当然，鼓励读者自己思考。

// Problem: P10968 扑克牌
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10968
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int unsigned long long
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 15;
int f[5][N][N][N][N], fac[101];
int n, tt;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    f[0][0][0][0][0] = 1;
    upp(l, 0, 13) upp(k, 0, 13) upp(j, 0, 13) upp(i, 0, 13) upp(p, 0, 3) {
        if (p == 0 && !i) continue;
        if (p == 1 && !j) continue;
        if (p == 2 && !k) continue;
        if (p == 3 && !l) continue;
        int dist = 0;
        if (p == 0) {
            dist += f[0][i - 1][j][k][l]; //上上个选了 1
            dist += f[1][i - 1][j][k][l]; //上上个选了 2
            dist += f[2][i - 1][j][k][l]; //上上个选了 3
            dist += f[3][i - 1][j][k][l]; //上上个选了 4
        } else if (p == 1) {
            dist += f[0][i + 1][j - 1][k][l] * i;       //上上个选了 1
            dist += f[1][i + 1][j - 1][k][l] * (i + 1); //上上个选了 2
            dist += f[2][i + 1][j - 1][k][l] * (i + 1); //上上个选了 3
            dist += f[3][i + 1][j - 1][k][l] * (i + 1); //上上个选了 4
        } else if (p == 2) {
            dist += f[0][i][j + 1][k - 1][l] * (j + 1); //上上个选了 1
            dist += f[1][i][j + 1][k - 1][l] * j;       //上上个选了 2
            dist += f[2][i][j + 1][k - 1][l] * (j + 1); //上上个选了 3
            dist += f[3][i][j + 1][k - 1][l] * (j + 1); //上上个选了 4
        } else {
            dist += f[0][i][j][k + 1][l - 1] * (k + 1); //上上个选了 1
            dist += f[1][i][j][k + 1][l - 1] * (k + 1); //上上个选了 2
            dist += f[2][i][j][k + 1][l - 1] * k;       //上上个选了 3
            dist += f[3][i][j][k + 1][l - 1] * (k + 1); //上上个选了 4
        }
        f[p][i][j][k][l] = dist;
    }
    fac[0] = 1;
    upp(i, 1, 20) fac[i] = fac[i - 1] * i;
    cin >> tt;
    upp(_tt, 1, tt) {
        map<char, int> ha;
        cin >> n;
        int a[5] = {0, 0, 0, 0, 0};
        upp(i, 1, n) {
            string str;
            cin >> str;
            ha[str[0]]++;
        }
        int res = 1;
        for (auto iter : ha) res *= fac[iter.second], a[iter.second]++;
        int ans = 0;
        ans += f[0][a[1]][a[2]][a[3]][a[4]];
        ans += f[1][a[1]][a[2]][a[3]][a[4]];
        ans += f[2][a[1]][a[2]][a[3]][a[4]];
        ans += f[3][a[1]][a[2]][a[3]][a[4]];
        cout << "Case #" << _tt << ": "
             << res * ans * fac[a[1]] * fac[a[2]] * fac[a[3]] * fac[a[4]]
             << endl;
    }
    return 0;
}