1745:Divisibility

keyword

動的計画法　C++

概要

数列a_iが与えられる。a_1にa_2,...,a_nを足すか引くかする。その和をkで割りきるようにすることができるか判定する問題。n<10^5、k<100。
k<100なのでa_iを長さ100の配列に詰めることができる。と考えてその後に詰まった。ひとつの考えに固執してしまってはいけないというよい教訓になった。
動的計画法でやる方がよい。m番目までの和(mod k)が作れるかどうかを覚えておけば簡単に計算できる。

int main(){
    bool dp[2][101];
    int n, k, x, i, j, r=0;
    REP(i,2)REP(j,101)dp[i][j] = false;

    scanf("%d%d%d",&n,&k,&x);
    dp[0][((x%k)+k)%k] = true;
    REPONE(i,n-1){
        r = i%2;
        scanf("%d",&x);
        REP(j,k)dp[r][j] = false;
        REP(j,k)if(dp[1-r][j]){
            dp[r][(((j+x)%k)+k)%k] = true;
            dp[r][(((j-x)%k)+k)%k] = true;
        }
    }

    if(dp[r][0])printf("Divisible\n");
    else printf("Not divisible\n");

    return 0;
}