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：复制

Magic.in

2 3 5

3 4 4

5 6 6

输出样例#1：复制

3

0 2 3
思路：dp
f[i][j][k]表示到i,j时，模数可否为k。
正确性可以由 (a*b)%mod=(a%mod)*(b%mod)得到。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,mod,ans;

int map[][];

int f[][][];

int main(){

    scanf("%d%d%d",&n,&m,&mod);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            scanf("%d",&map[i][j]);

    f[][][map[][]%mod]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            for(int k=;k<mod;k++){

                if(f[i-][j][k])    f[i][j][k*map[i][j]%mod]=;

                if(f[i][j-][k])    f[i][j][k*map[i][j]%mod]=;

            }

    for(int i=;i<mod;i++)

        if(f[n][m][i])    ans++;

    cout<<ans<<endl;

    for(int i=;i<mod;i++)

        if(f[n][m][i])    cout<<i<<" ";

}

巴特西

洛谷 P2049 魔术棋子

P2049 魔术棋子

题目描述

输入输出格式

输入输出样例

最新文章

热门文章