魔术棋子

题目描述

在一个M*N的魔术棋盘中，每个格子中均有一个整数，当棋子走进这个格子中，则此棋子上的数会被乘以此格子中的数。一个棋子从左上角走到右下角，只能向右或向下行动，请问此棋子走到右下角后，模（mod）K可以为几？

如以下2*3棋盘：

1
2
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个数，分别为此方阵中的数。

输出格式

第一行为可能的结果个数

第二行为所有可能的结果(按升序输出)

样例 #1

样例输入 #1

1
2
3
2 3 5
3 4 4
5 6 6

样例输出 #1

1
2
3
0 2 3

题解

题目解析

奇怪的背包题, 说实话这也不能算是背包题, 实际上算是一个dp题. 这道题需要对每一格都要模 $k$ , 所以每一格可以凑成的值就有 $k$ 种可能, 既然需要状态转移, 那么就需要把每一格的 $k$ 的可能都要存下来, 于是就需要开三维数组.

接着考虑如何转移, 假设这一格的坐标为 $(i,j)$ , 那么这一格的所有可能都是由左边和上面的数组转移而来的. 于是我们就得到了相应的状态转移方程:

解释一下就是: 只要左侧格和上侧格凑成 $n$ , 相应的就能在本格凑成 $na_{i,j}\mod k$ 这一值. 之所以最后还是或了本格, 是因为如果不或上自己可能在某个相乘的时候会把本身为 $1$ 的dp数组重新覆盖成 $0$ .

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef pair<int,int> PII;
typedef long long ll;
typedef long double lb;
typedef unsigned long long ull;

MAXN(100);
int n,m,k;
int a[MAXN][MAXN],dp[MAXN][MAXN][MAXN];;

signed main(){
	CIN_;CIN;
	cin >> m >> n >> k;
	fa(i,1,m){
		fa(j,1,n){
			cin >> a[i][j];
		}
	}
	dp[0][1][1] = 1,dp[1][0][1] = 1; 
	fa(i,1,m){
		fa(j,1,n){
			fa(f,0,k-1){
				dp[i][j][(f*a[i][j])%k] = dp[i-1][j][f] || dp[i][j-1][f] || dp[i][j][(f*a[i][j])%k];
			}
		}
	}
	int ans = 0;
	fa(i,0,k-1) if(dp[m][n][i]) ans++;
	cout << ans << endl;
	fa(i,0,k-1) if(dp[m][n][i]) cout << i << " ";
	cout << endl;
	return 0;
}