题解 P2049 【魔术棋子】
斯德哥尔摩
2017-11-19 10:18:38
f[i][j][l] 表示在 （i，j）这个位置能否使乘积达到 l ，那么状态转移方程就很好推了：
f[i][j][l\*a[i][j]%k]=1（f[i-1][j][l]||f[i][j-1][l]==1）
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 110
using namespace std;
int n,m,k,ans=0,a[MAXN][MAXN],f[MAXN][MAXN][MAXN];
inline int read(){//无用的读优。。。
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
int main(){
n=read();m=read();k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read();//读入
f[1][0][1]=f[0][1][1]=1;//初始化，当初我傻傻地将第0行与第0列全部赋为1，然后爆炸了。。。
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)//枚举每个位置
for(int l=0;l<k;l++){//枚举每个能达到的数
if(f[i-1][j][l])
f[i][j][(l*a[i][j])%k]=1;//转移
if(f[i][j-1][l])
f[i][j][(l*a[i][j])%k]=1;//转移
}
for(int i=0;i<k;i++)if(f[n][m][i])ans++;//计算个数
printf("%d\n",ans);
for(int i=0;i<k;i++)if(f[n][m][i])printf("%d ",i);//输出结果
printf("\n");
return 0;
}
```