CCSP2019T2_纸牌计数 | 2019苏州CCSP大学生计算机系统与程序设计竞赛

题目描述

偶然在CSDN看到有人写了CCSP2019T2_纸牌计数的题解，突然想起来是一个不错的计数、dp题。
以前的U盘找不到了，记得当时存了一步步偏分到AC代码，可惜。又想起来18年打铁了。。。
此人的题解的链接 CCSP201902纸牌计数——解题报告
当年一共有5题，取自：https://www.sohu.com/a/347851686_610300
T1: 摘水果 fruit
T2：纸牌计数 card
T3：系统实现题 SQL 查询
T4：系统策略题 调度器 scheduler
T5：系统结构体 评测鱼 risc-v
T2的题面：

Description
我们有一副纸牌，它由 n 张牌组成，其中每张牌上标有一个数字（0 到 9）和一个大写字母（A 到 Z），例如 2C、1F。

我们如下定义一个字符串与一张牌之间的匹配关系：
字符串 ?? 与任何一张牌都匹配。
第一位为 ? 而第二位为字母的字符串，与任何一张标有该字母的牌匹配。例如，字符串 ?C 与任何标有 C 的牌匹配。
第一位为数字而第二位为字母的字符串，仅与内容完全一致的牌匹配。例如，字符串 0C 与内容为 0C 的牌匹配。
不会出现第一位为数字而第二位为 ? 的字符串。
我们称 m 个字符串 S1 ... Sm 与 m 张牌 C1 ... Cm 是匹配的，当且仅当：存在集合 { 1 , … , m } 上的一一映射 σ，使得对于任意 1 ≤ i ≤ m ，Si 与 C_σ(i) 匹配。

例如，对于 ?? 和 ?C 这两个字符串，可以匹配内容为 1C 和 2C 的牌，因为字符串 ?? 与内容为 2C 的牌匹配且字符串 ?C 与内容为 1C 的牌匹配，而 ?? 和 ?C 这两个字符串不能匹配内容为 1S 和 1P 的牌。

现在，给定 m 个字符串，你需要求解：如果在 n 张牌中（无放回地）随机选取 m 张，有多大概率与这些字符串匹配？

Input
每个输入文件包含多个输入数据。
第一行输入该文件的数据个数 T。
接下来依次输入每个数据。每个数据包含三行，其中：
第一行输入两个正整数 n 和 m；
第二行输入以空格分隔的 n 个字符串，表示每张纸牌的内容（每个字符串第一位为数字，第二位为大写字母）；
第三行输入以空格分隔的 m 个字符串，表示每个需要匹配的字符串（每个字符串第一位为数字，第二位为大写字母；或第一位为 ?，第二位为大写字母；或为 ??）。

Output
对于每个输入数据，输出一行，表示所求的概率。概率需要以最简分数 u/v 的形式输出，其中 0 ≤ u ≤ v 且 u, v 为互质的整数。
特殊地，对于 0 请输出 0/1，对于 1 请输出 1/1。

Subtasks
对于所有的数据，1 <= m <= n <= 60, T <= 1000, $1 \leq m \leq n \leq 60; T \leq 1000$。
（11分）m=1；
（23分）m=n；
（27分）n=30 且所有的牌为 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P；
（22分）n=40 且所有的牌为 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P；
（17分）没有特殊的限制。

题解

一时间不记得咋写的了，按记忆口胡了一个做法，感觉复杂度有点假，但好像跑不满，以后再看看吧：

• 求概率/期望的时候，两个独立事件（即正交的情况）可以分开考虑，答案为每个事件概率的乘积。类似于积性函数中的一些理念。
• n张牌的字母都是固定的，一般m个字符串的字母也是固定的（除非是两个问号??）。
• 考虑是否可以先分26个字母考虑，再考虑??。
• rdp[j][k] 表示考虑到数字j用了k个问号的（不）合法情况数（合不合法，即是否存在重复计数的），把单个?的情况用组合数计数分配一下
• 现在 ?? 还没处理吧，所以??可以在这个层次上再套一层dp
• val[i][w] 表示考虑到字母i已经用了w个??的合法方案数，最后背包dp一遍求答案
• （不确定有没有爆 long long，感觉复杂度可以减掉一个60？

#include <bits/stdc++.h>
#define fi first
#define se second
#define o2(x) (x) * (x)
#define mk make_pair
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(register int i = (s), LIM=(t); i > LIM; --i)
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
// mt19937 rng(time(NULL));//std::clock()
// mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
// shuffle(arr, arr + n, rng64);
inline int64 read() {
    int64 x = 0;int las = 0;char ch = getchar();
    while (ch < '0' || ch > '9') las |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch =
    getchar(); return x = las ? -x : x;
}
inline void write(int64 x, bool las = true) {
    if (x == 0) {putchar('0'); if(las)putchar('\n');else putchar(' ');return;}
    if (x < 0) {putchar('-');x = -x;}
    static char s[23];
    int l = 0;
    while (x != 0)s[l++] = x % 10 + 48, x /= 10;
    while (l)putchar(s[--l]);
    if(las)putchar('\n');else putchar(' ');
}
int lowbit(int x) { return x & (-x); }
template <class T>
T big(const T &a1, const T &a2) {return a1 > a2 ? a1 : a2;}
template <class T>
T sml(const T &a1, const T &a2) {return a1 < a2 ? a1 : a2;}
template <typename T, typename... R>
T big(const T &las, const R &... r) {return big(las, big(r...));}
template <typename T, typename... R>
T sml(const T &las, const R &... r) {return sml(las, sml(r...));}
void debug_out() { cout << '\n'; }
template <typename T, typename... R>
void debug_out(const T &las, const R &... r) {
    cout << las << " ";
    debug_out(r...);
}
#ifdef LH_LOCAL
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);
#else
#define debug(...) ;
#endif
#define debug(...) ;
/*================Header Template==============*/
const int mod = 998244353;// 998244353
int ksm(int a, int64 b, int kmod = mod) {int res = 1;for(;b > 0;b >>= 1, a = (int64)a * a % kmod) if(b &1) res = (int64)res * a % kmod;return res;}
const int INF = 0x3f3f3f3f;
const int MXN = 2e5 + 5;
const int MXM = 5e6 + 7;
int n, m;
char card[65][3], str[65][3];
// 0 <= . <= 9, A <= . <= Z  -> 1 <= . <= 10
int cnt[30][15], need[30][15];
int sum[2][30];
LL fdp[30], rdp[15][65], val[30][65], dp[30][65];

LL COMB(int n, int m) {
    if(n == m) return 1;
    if(n < m) return 0;
    LL res = 1;
    for(int i = 0; i < m; ++i) {
        res *= (n - i);
        res /= i + 1;
    }
    return res;
}

void work() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) scanf("%s", card[i]);
    for(int i = 1; i <= m; ++i) scanf("%s", str[i]);
    int flag = 1;
    for(int i = 1; i <= n; ++i) {
        cnt[card[i][1] - 'A'][card[i][0] - '0' + 1] ++;
        sum[0][card[i][1] - 'A'] ++;
    }
    LL ww = m;
    for(int i = 1; i <= m; ++i) {
        if(str[i][1] != '?') {
            if(str[i][0] != '?') need[str[i][1] - 'A'][str[i][0] - '0' + 1] ++;
            else need[str[i][1] - 'A'][0] ++;
            sum[1][str[i][1] - 'A'] ++;
            ww --;
        }
    }
    LL res = 1;
    for(int i = 0; i < 26; ++i) {
        if(sum[0][i] < sum[1][i]) {
            flag = 0;
            break;
        }
        for(int w = 0; w <= ww; ++w) {
            need[i][0] += w;
            fdp[i] = 1;
            memset(rdp, 0, sizeof(rdp));
            rdp[0][0] = 1;
            // rdp[j][k] 表示考虑到数字j用了k个问号的（不）合法情况数（合不合法，即是否存在重复计数的）
            // 把单个?的情况用组合数计数分配一下
            // ?? 还没处理吧，所以??可以在这个层次上再套一层dp
            // val[i][w] 表示考虑到字母i已经用了w个??的合法方案数
            for(int j = 1; j <= 10; ++j) {
                if(cnt[i][j] < need[i][j]) {
                    flag = 0;
                    break;
                }
                fdp[i] = fdp[i] * COMB(cnt[i][j], need[i][j]);
                // for(int k = 0; k <= need[i][0]; ++k) rdp[j][k] = rdp[j - 1][k];
                if(1 || cnt[i][j] > need[i][j] && need[i][j] > 0) {
                    for(int h = 0; h <= cnt[i][j] - need[i][j]; ++h) {
                        for(int k = h; k <= need[i][0]; ++k) {
                            rdp[j][k] = rdp[j][k] + rdp[j - 1][k - h] * COMB(cnt[i][j], need[i][j] + h);
                            // debug(h, j, k, rdp[j][k])
                        }
                    }
                    // if(i == 'C' - 'A') debug(j)
                }else {
                    // if(i == 'C' - 'A') debug(j, rdp[j][1], rdp[j - 1][1])
                }
            }
            // rdp[10][0] = 0;
            fdp[i] = fdp[i] * COMB(sum[0][i] - (sum[1][i] - need[i][0]), need[i][0]);
            LL ret = rdp[10][need[i][0]];
            if(i == 'C' - 'A') debug(i, w, need[i][0], fdp[i], rdp[10][need[i][0]], fdp[i] - rdp[10][need[i][0]], ret, fdp[i] - ret)
            res *= (ret);
            need[i][0] -= w;
            val[i][w] = ret;
            if(i == 'C' - 'A' && val[i][w] > 1) debug(i, w, val[i][w])
        }
    }
    for(int j = 0; j <= ww; ++j) dp[0][j] = val[0][j];
    for(int i = 1; i < 26; ++i) {
        for(int j = 0; j <= ww; ++j) {
            for(int k = 0; k <= j; ++k) {
                dp[i][j] = dp[i][j] + dp[i - 1][j - k] * val[i][k];
            }
        }
    }
    res = dp[25][ww];
    LL allcase = COMB(n, m);
    LL agcd = __gcd(allcase, res);
    debug(allcase, res, res / agcd, allcase / agcd)
    if(flag == 0) {
        printf("0/1\n");
    }else {
        printf("%lld/%lld\n", res / agcd, allcase / agcd);
    }
    // 不确定有没有爆 long long
    for(int i = 0; i < 26; ++i) {
        sum[0][i] = sum[1][i] = 0;
        for(int j = 0; j <= 10; ++j) {
            cnt[i][j] = need[i][j] = 0;
        }
        for(int j = 0; j <= ww; ++j) {
            val[i][j] = 0;
            dp[i][j] = 0;
        }
    }
}

int main() {
#ifdef LH_LOCAL
    freopen("c:/lh/system-lab/acm_code/OJ/in.txt", "r", stdin);
    // freopen("c:/lh/system-lab/acm_code/OJ/out.txt", "w", stdout);
#endif
    for(int cas = 1, tim = (1 ? read(): 1); cas <= tim; ++ cas) {
        work();
    }
    // 56160000
    debug(26*60*10*60*60)
#ifdef LH_LOCAL
    cout << "Debug log: time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}
/*
3
40 2
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
?C 1C
40 16
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
0C 0C 1C 2C ?C ?C ?C ?C 3S 4S ?S ?S 5P 6P ?P ?P
60 30
1A 1B 1C 1D 1E 1F 1G 1H 1I 1J 1K 1L 1M 1N 1O 1P 1Q 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 0A 1A 2A 3A 4A 5A 6A 7A 8A 9A 1S 3S 5S 7S 9S 0U 2U 4U 6U 8U 2Z 3Z 5Z 7Z 1C 1C 1C 1C 1C 1C 1C 1C 1S 1P
1C 1C 1S 1P 2A 0A 1A 9A ?S ?U ?Z ?H ?O ?U ?? ?? ?? ?? ?? ?? ?S ?S ?S ?U ?U ?U ?Z ?Z ?C ?C

37/780
167384/2417388525  -> 4351984/x -> 5551 * 28 * 28
50442363273/29566145391215356 -> 201769453092/x

Sample
Input
15
6 1
0C 0S 0P 1C 1S 1P
1S
6 1
0C 0S 0P 1C 1S 1P
?C
6 2
0C 0S 0P 1C 1S 1P
?C ?C
6 2
0C 0S 0P 1C 1S 1P
?C ?S
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?S ?P
6 4
0C 0S 0P 1C 1S 1P
0C ?C ?S ?P
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?S ??
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?? ??
6 4
0C 0S 0P 1C 1S 1P
?A ?? ?? ??
6 4
0C 0S 0P 1C 1S 1P
0C 0C ?S ?P
30 8
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
0C ?C ?C ?C 1S ?S 2P ?P
40 2
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
?C 1C
40 2
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
?C 1S
40 16
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
0C 0C 1C 2C ?C ?C ?C ?C 3S 4S ?S ?S 5P 6P ?P ?P
60 30
1A 1B 1C 1D 1E 1F 1G 1H 1I 1J 1K 1L 1M 1N 1O 1P 1Q 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 0A 1A 2A 3A 4A 5A 6A 7A 8A 9A 1S 3S 5S 7S 9S 0U 2U 4U 6U 8U 2Z 3Z 5Z 7Z 1C 1C 1C 1C 1C 1C 1C 1C 1S 1P
1C 1C 1S 1P 2A 0A 1A 9A ?S ?U ?Z ?H ?O ?U ?? ?? ?? ?? ?? ?? ?S ?S ?S ?U ?U ?U ?Z ?Z ?C ?C
Output
1/6
1/3
1/15
4/15
4/15
4/15
1/3
2/5
0/1
0/1
252/216775
37/780
1/39
167384/2417388525
50442363273/29566145391215356

Hint
对于分数 a/b，设 g=gcd(a,b)，那么其最简分数形式为 (a/g)/(b/g)。


*/