csp7连测day7T4

枚举字符串并计算概率

计 p(T, x) =

$\cfrac{\Pi(S\frac{t_i}{i})}{A^{\sum t_i}_{\sum s_i}}$

然后计算答案 P(T)

$P(T) = 1 - \Pi_{x = 1}^{n}(1-p(T,x))$

然后求所有P(T)的总和。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110, P = 998244353;
int n, m, ans, vec[N], dm[N][N], cnt[N][10], w[N], dp[N];
char c[N];
int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = (1ll * res * a) % P;
        a = (1ll * a * a) % P, b >>= 1;
    }
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", c + 1);
        for (int j = 1; j <= m; j++)
            cnt[i][c[j] - '0']++;
    }
    for (int i = 0; i <= m; i++)
    {
        dm[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            dm[i][j] = (1ll * dm[i][j - 1] * (i - j + 1)) % P;
        }
    }
    for (int i = 1; i < (1 << n); i++)
    {
        int cntt = 0, sum = 0;
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                vec[++cntt] = j + 1;
            }
        }
        dp[0] = 1;
        for (int j = 1; j <= m; j++)
        {
            dp[j] = 0;
        }
        for (int j = 0; j <= 9; j++)
        {
            for (int l = 0; l <= m; l++)
            {
                w[l] = qpow(dm[l][l], P - 2);
                for (int k = 1; k <= cntt; k++)
                {
                    w[l] = (1ll * w[l] * dm[cnt[vec[k]][j]][l]) % P;
                }
            }
            for (int l = m; l >= 0; l--)
            {
                for (int k = l - 1; k >= 0; k--)
                {
                    dp[l] = (dp[l] + (1ll * dp[k] * w[l - k]) % P) % P;
                }
            }
        }
        for (int l = 0; l <= m; l++)
        {
            int tmp = (1ll * dp[l] * dm[l][l]) % P, prod = qpow(dm[m][l], P - 2);
            sum = (sum + (1ll * tmp * qpow(prod, cntt)) % P) % P;
        }
        if (cntt & 1)
            ans = (ans + sum) % P;
        else
            ans = (ans - sum + P) % P;
    }
    printf("%d\n", ans);
    return 0;
}