洛谷 P2049 魔术妻子 题解

算法

dp

思路

直接用 set 统计即可。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n, m, k;
set <int> dp[105][105];
int a[105][105];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a[i][j];
        }
    }
    dp[0][1].insert(1);
    dp[1][0].insert(1);
    // dp[1][1].insert(a[1][1] % k);
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            for (auto it = dp[i - 1][j].begin(); it != dp[i - 1][j].end(); it ++) {
                dp[i][j].insert((*it * a[i][j]) % k);
            }
            for (auto it = dp[i][j - 1].begin(); it != dp[i][j - 1].end(); it ++) {
                dp[i][j].insert((*it * a[i][j]) % k);
            }
        }
    }
    cout << dp[n][m].size() << "\n";
    for (auto it = dp[n][m].begin(); it != dp[n][m].end(); it ++) {
        cout << *it << " ";
    }
    return 0;
}