题目描述
在一个 M*N 的魔术棋盘中, 每个格子中均有一个整数, 当棋子走进这个格子中, 则此棋子上的数会被乘以此格子中的数. 一个棋子从左上角走到右下角, 只能向右或向下行动, 请问此棋子走到右下角后, 模 (mod)K 可以为几?
如以下 2*3 棋盘:
3 4 4
5 6 6
棋子初始数为 1, 开始从左上角进入棋盘, 走到右下角, 上图中, 最后棋子上的数可能为 288,432 或 540. 所以当 K=5 时, 可求得最后的结果为: 0,2,3.
输入输出格式
输入格式
第一行为三个数, 分别为 M,N,K(1≤M,N, K≤100);
以下 M 行, 每行 N 个数, 分别为此方阵中的数.
输出格式
第一行为可能的结果个数;
第二行为所有可能的结果 (按升序输出).
输入输出样例
输入样例
- 2 3 5
- 3 4 4
- 5 6 6
输出样例
3
0 2 3
题解
简单 dp, 三重循环暴力即可.
- #include <iostream>
- #include <cstdio>
- #define MAX_M (100 + 5)
- #define MAX_N (100 + 5)
- #define MAX_C (100 + 5)
- using namespace std;
- int m, n, c;
- int a[MAX_M][MAX_N];
- int dp[MAX_M][MAX_N][MAX_C];
- int ans;
- int main()
- {
- scanf("%d%d%d", &m, &n, &c);
- for(register int i = 1; i <= m; ++i)
- {
- for(register int j = 1; j <= n; ++j)
- {
- scanf("%d", &a[i][j]);
- }
- }
- dp[0][1][1] = 1;
- for(register int i = 1; i <= m; ++i)
- {
- for(register int j = 1; j <= n; ++j)
- {
- for(register int k = 0; k < c; ++k)
- {
- dp[i][j][k * a[i][j] % c] |= dp[i - 1][j][k] | dp[i][j - 1][k];
- }
- }
- }
- for(register int i = 0; i < c; ++i)
- {
- ans += dp[m][n][i];
- }
- printf("%d\n", ans);
- for(register int i = 0; i < c; ++i)
- {
- if(dp[m][n][i])
- {
- printf("%d", i);
- }
- }
- return 0;
- }
参考程序
来源: http://www.bubuko.com/infodetail-3004574.html