自动搬运

查看原文

来自洛谷，原作者为

	GY程袁浩 2025.11月前不改签

搬运于2025-08-24 23:03:01，当前版本为作者最后更新于2025-02-03 16:23:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

建议评蓝。

想爽了。有趣数数题。

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

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

$\textbf{Motivation 1}：$观察样例。

2C AD AC JC JH 该怎么排列？有两个 A 和 J。

第一组：2C AD JC JH AC。

第二组：2C AC JC JH AD。

欸，这个 A 两个不同花色的是不是换了个位置。等下，是不是我随便排列同样面值的所有牌构造的序列还是合法的？

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

$\textbf{Observation 1}：$随便排列同样面值的所有牌构造的序列还是合法的。

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

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

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

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

$\textbf{Motivation 2}：$刚刚我的观察本质是找到了等价情况，我能不能再找一些？

当然可以找到。

$\textbf{Observation 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;
}