题解 P1356 【数列的整数性】

courage · 2013-08-15 15:08:10 · 题解

此题可以用动态规划解决

考虑到k比较小，令f[i][j]表示加上或减去第i个数后模k是否可能等于j，则答案为f[n][0]。

状态转移方程：f[i][j]=f[i-1][p(j-x)] or f[i-1][p(j+x)]

函数p(x)是将x模k的余数

#include<cstdio>
#include<cstring>
int x,k,n,t;
bool f[10010][110];
int p(int x){
    x%=k;
    if (x<0) x+=k;
    return x;
}
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&k);
        memset(f,0,sizeof(f));
        scanf("%d",&x);
        f[0][p(x)]=f[0][p(-x)]=1;
        for (int i=1;i<n;i++){
            scanf("%d",&x);
            for (int j=0;j<k;j++) f[i][j]=f[i-1][p(j-x)]|f[i-1][p(j+x)];
        }
        if (f[n-1][0]) printf("Divisible\n");else printf("Not divisible\n");
    }
}