魔术棋子

魔术妻子

魔术棋子

题目链接

这道题是关于矩形一类动归的拓展题

因为魔术模数的取值范围很小，所以开数组完全存的开。

也可以通过判断数据取值范围确定时间复杂度

#include<iostream> 
#include<cstdio>
using namespace std;
int map[101][101];
int dp[101][101][101];
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&map[i][j]);
			map[i][j]%=k;
		}
	dp[1][1][map[1][1]]=true;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int l=0;l<k;l++)
			{
				if(dp[i-1][j][l])
					dp[i][j][(l*map[i][j])%k]=true;
				if(dp[i][j-1][l])
					dp[i][j][(l*map[i][j])%k]=true;
			}
	int ans=0;
	for(int i=0;i<k;i++)
		if(dp[n][m][i])
			ans++;
	printf("%d
",ans);
	for(int i=0;i<k;i++)
		if(dp[n][m][i])
			printf("%d ",i);
	return 0;
}