NEERC 1999 Divisibility同余DP oj22640

题目大意：

输入n,m； ( 1 ≤ N ≤ 10000, 2 ≤ M ≤ 100 )

接下来n个数；Each integer is not greater than 10000 by it's absolute value.

判断他们按顺序做加减法后能否整除m

若能输出“Divisible”，否则输出“Not divisible”；

Sample Input

Sample #14 717 5 -21 15Sample #24 517 5 -21 15

Sample Output

Sample #1DivisibleSample #2Not divisible

对于第一个样例解释：

17 + 5 + -21 + 15 = 1617 + 5 + -21 - 15 = -1417 + 5 - -21 + 15 = 5817 + 5 - -21 - 15 = 2817 - 5 + -21 + 15 = 617 - 5 + -21 - 15 = -2417 - 5 - -21 + 15 = 4817 - 5 - -21 - 15 = 18

-14可整除7

 

#include <bits/stdc++.h> using namespace std; bool dp[10005][105]; /// dp[i][j]表示第i个数时余数为j的状态存不存在 1为存在 0则不存在 int main() { int n,m,a; while(~scanf("%d%d%d",&n,&m,&a)) { memset(dp,0,sizeof(dp)); dp[1][(a%m+m)%m]=1; // 到第1个数时 a%m 存在 for(int i=2;i<=n;i++) { scanf("%d",&a); a=fabs(a); a%=m; /// 防止出现负数 先取绝对值 对求余没影响 for(int j=0;j<m;j++) if(dp[i-1][j]) // 若上一个数时 余j 的状态存在 dp[i][(j+a)%m]=dp[i][(j-a+m)%m]=1; /// 则可由 上个数余j的状态 推出 /// 到当前数时(+a或-a) 余(j+a)%m 和 余(j-a+m)%m /// 两个状态可存在 } if(dp[n][0]) printf("Divisible\n"); else printf("Not divisible\n"); } return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/9092804.html