2049 魔术棋子
貌似这个题,并没有啥思路
dp[i][j][l]表示在位置(i,j)能不能得到l,也就是dp数组只能是1或0
l*num[i][j]%k表示当前格子数乘从左边或上边传下来的数l再mod k
dp[i-1][j][l]和dp[i][j-1][l]表示在上方或左方能不能得到l
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int m,n,k,ans;
int num[105][105];
bool dp[105][105][105];
int main()
{
cin>>m>>n>>k;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>num[i][j];
num[i][j]%=k;//一开始的时候就取余,省点事
}
}
dp[1][1][num[1][1]]=true;//初始化
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int l=0;l<k;l++)//取数的范围最大就是k-1
if(!dp[i][j][l*num[i][j]%k])//没有更新 l*num[i][j]%k表示乘积
dp[i][j][l*num[i][j]%k]=dp[i-1][j][l]||dp[i][j-1][l];
//l*num[i][j]%k表示当前格子数乘从左边或上边传下来的数l再mod k
//dp[i-1][j][l]和dp[i][j-1][l]表示在上方或左方能不能得到l
for(int i=0;i<k;i++)//查找
{
if(dp[m][n][i]) ans++;
}
printf("%d\n",ans);
for(int i=0;i<k;i++)//然后输出每一个数
{
if(dp[m][n][i]) printf("%d ",i);
}
return 0;
}