P2049 魔术棋子题解

思路

设 \(f_{i, j, k}\) 表示从原点走到 \((i, j)\) 模 \(m\) 后的乘积为 \(k\) 的方案数。

状态转移：\(f_{i, j, ka_{i, j} \bmod m} = f_{i - 1, j, k} + f_{i, j - 1, k}\)

统计答案：\(f_{n, n, k}\)。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m, o;
int a[N][N];
int f[N][N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    cin >> n >> m >> o;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];

    f[1][1][a[1][1]] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k < o; k++) {
                // f[i][j - 1]
                // f[i - 1][j]
                f[i][j][(k * a[i][j]) % o] += f[i][j - 1][k];
                f[i][j][(k * a[i][j]) % o] += f[i - 1][j][k];
            }
        }
    }
    vector<int> ans;
    for (int k = 0; k < o; k++) if (f[n][m][k]) ans.push_back(k);
    cout << ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
    cout << '\n';
	return 0;
}