同余dp

lxqiaoyixuan 2018-10-03 原文

先验知识：

　　余数的计算公式：c = a -⌊ a/b⌋ * b

　　其中，⌊ ⌋为向下取整运算符，向下取整运算称为Floor，用数学符号⌊ ⌋表示

题目：

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("%d\n", -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("Divisible\n") : printf("Not divisible\n");
    }
    return 0;
}