P2049 魔术棋子

题目描述

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

如以下2*3棋盘：

3 4 4

5 6 6

棋子初始数为1，开始从左上角进入棋盘，走到右下角，上图中，最后棋子上的数可能为288,432或540。所以当K = 5时，可求得最后的结果为：0,2,3。

输入输出格式

输入格式：

输入文件magic.in第一行为三个数，分别为M,N,K (1 ≤ M,N,K ≤ 100)以下M行，每行N个数，分别为此方阵中的数。

输出格式：

输出文件magic.out第一行为可能的结果个数

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

输入输出样例

输入样例#1： 复制

2 3 5
3 4 4
5 6 6

输出样例#1： 复制

3
0 2 3

/*dp[i][j][l]表示在位置(i,j)能不能得到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];
inline int read(int &num)
{
    num=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar()){num=num*10+c-'0';}
}
int main()
{
    read(m),read(n),read(k);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            read(num[i][j]);
            num[i][j]%=k;    //一开始就mod 
        }
    }
    dp[1][1][num[1][1]]=true;    //初始化位置(1,1)的数 
    for(int i=1;i<=m;i++)
     for(int j=1;j<=n;j++)
      for(int l=0;l<k;l++)    //因为mod k 后得到的数一定小于k，所以从0到k枚举 
       if(!dp[i][j][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
",ans);
    for(int i=0;i<k;i++)    //找可能得到的数 
    {
        if(dp[m][n][i]) printf("%d ",i);
    }
    return 0;
}