同余dp

先验知识：

题目：

Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence,thus deriving di?erent arithmetical expressions that evaluate to di?erent values. Let us,for example,take the sequence: 17,5,-21,15. There are eight possible expressions:
17 + 5 + -21 + 15 = 16 17 + 5 + -21 - 15 = -14 17 + 5 - -21 + 15 = 58 17 + 5 - -21 - 15 = 28 17 - 5 + -21 + 15 = 6 17 - 5 + -21 - 15 = -24 17 - 5 - -21 + 15 = 48 17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example,the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5. You are to write a program that will determine divisibility of sequence of integers.

分析：

dp重点在于找到状态转移

dp[i][j]表示加到第i个数时是否能被j整除

/*同余dp*/
#include <bits/stdc++.h>
#define N 10010
#define M 110 

bool dp[N][M];

int main(){
    int t,n,k,a;
    /*
        取模运算和取余运算（余数没有负数）在负数运算上有差别
        printf("%dn",-13%5);
    */
    scanf("%d",&t);
    while(t --){
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&k);
        scanf("%d",&a);
        a = abs(a) % k;
        dp[0][a % k] = dp[0][(k - a) % k] = true;
        for(int i = 1; i < n; ++ i){
            scanf("%d",&a);
            a = abs(a) % k;
            for(int j = 0; j < k; ++ j){
                if(dp[i - 1][j]){
                    dp[i][(j + a) % k] = dp[i][(j - a + k) % k] = true;
                }
            } 
        }
        dp[n - 1][0] ? printf("Divisiblen") : printf("Not divisiblen");
    }
    return 0;
}