题解 P2049 【魔术棋子】

Drifterming · 2017-08-14 07:36:10 · 题解

/*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\n",ans);
    for(int i=0;i<k;i++)    //找可能得到的数 
    {
        if(dp[m][n][i]) printf("%d ",i);
    }
    return 0;
}