1 条题解

  • 0
    @ 2023-4-28 9:28:15
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MOD = 998244353;
    const int MAXN = 100;  // 烹饪方法
    const int MAXM = 2000; // 食材
    int n, m;
    int a[MAXN + 5][MAXM + 5];
    int sum[MAXN + 5]; // sum[i] = sum(a[i][1]~a[i][m])
    // O(mn^3) = 84pt
    namespace subtask1
    {
        // 第wa种食材用多了时
        // 前i种烹饪方法中,有j种用了wa食材,k种用了其他食材,的方案数
        int f[MAXN + 5][MAXN + 5][MAXN + 5];
        // 前 i 种烹饪方式,炒出 j 道菜一共多少种方案
        int g[MAXN + 5][MAXN + 5];
        // 总方案,失败方案
        int all, sub;
        void work()
        {
            all = sub = 0;
            // 预处理 g[][]
            // 考虑有没有使用第 i 种烹饪方式
            g[0][0] = 1;
            for (int i = 1; i <= n; i++)
            {
                g[i][0] = 1;
                for (int j = 1; j <= n; j++)
                    g[i][j] = (g[i - 1][j] + sum[i] * g[i - 1][j - 1] % MOD) % MOD;
            }
            for (int i = 1; i <= n; i++)
                all = (all + g[n][i]) % MOD;
            // 枚举每种 j 对应的食材
            for (int wa = 1; wa <= m; wa++)
            {
                memset(f, 0, sizeof(f));
                // 处理 f[][][]
                f[0][0][0] = 1;
                for (int i = 1; i <= n; i++)
                {
                    for (int j = 0; j <= i; j++)
                    {
                        for (int k = 0; j + k <= i; k++)
                        {
                            // f[i - 1][j][k]:不用第 i 种烹饪方式
                            // a[i][wa] * f[i - 1][j - 1][k]:第 i 种烹饪方式烹饪了 wa 食材
                            //(sum[i] - a[i][wa]) * f[i - 1][j][k - 1]:第 i 种烹饪方式烹饪了其他食材
                            f[i][j][k] = f[i - 1][j][k];
                            if (j > 0)
                                f[i][j][k] += a[i][wa] * f[i - 1][j - 1][k] % MOD;
                            if (k > 0)
                                f[i][j][k] += (sum[i] - a[i][wa] + MOD) % MOD * f[i - 1][j][k - 1] % MOD;
                            f[i][j][k] %= MOD;
                            // 计数 gg
                            if (i == n && j > k)
                                sub = (sub + f[i][j][k]) % MOD;
                        }
                    }
                }
            }
            cout << (all - sub + MOD) % MOD << "\n";
        }
    }
    // O(mn^2) 100pt
    namespace subtask2
    {
        // 第wa种食材用多了时
        // 前i种烹饪方法中,wa食材比其他食材多用了 j 个,的方案数
        int f[MAXN + 5][2 * MAXN + 5];
        int BASE = MAXN;
        // 前 i 种烹饪方式,炒出 j 道菜一共多少种方案
        int g[MAXN + 5][MAXN + 5];
        // 总方案,失败方案
        int all, sub;
        void work()
        {
            all = sub = 0;
            // 预处理 g[][]
            // 考虑有没有使用第 i 种烹饪方式
            g[0][0] = 1;
            for (int i = 1; i <= n; i++)
            {
                g[i][0] = 1;
                for (int j = 1; j <= n; j++)
                    g[i][j] = (g[i - 1][j] + sum[i] * g[i - 1][j - 1] % MOD) % MOD;
            }
            for (int i = 1; i <= n; i++)
                all = (all + g[n][i]) % MOD;
            // 枚举每种 j 对应的食材
            for (int wa = 1; wa <= m; wa++)
            {
                memset(f, 0, sizeof(f));
                // 处理 f[][][]
                f[0][0 + BASE] = 1;
                for (int i = 1; i <= n; i++)
                {
                    for (int j = -i; j <= i; j++)
                    {
                        f[i][j + BASE] = f[i - 1][j + BASE];
                        f[i][j + BASE] += a[i][wa] * f[i - 1][j - 1 + BASE] % MOD;
                        f[i][j + BASE] += (sum[i] - a[i][wa] + MOD) % MOD * f[i - 1][j + 1 + BASE] % MOD;
                        f[i][j + BASE] %= MOD;
                        if (i == n && j > 0)
                            sub = (sub + f[i][j + BASE]) % MOD;
                    }
                }
            }
            cout << (all - sub + MOD) % MOD << "\n";
        }
    }
    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                cin >> a[i][j];
                sum[i] = (sum[i] + a[i][j]) % MOD;
            }
        if (n <= 40 && m <= 500)
            subtask1::work();
        else
            subtask2::work();
    
        return 0;
    }
    
    • 1

    信息

    ID
    43
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    10
    已通过
    5
    上传者