這是一篇水水的無干貨文章 題目地址

描述
Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different 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.
輸入
The first line of the input file contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.
輸出
Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.

半夜睡不著覺的時候就起來隨便看點題，正巧看到了這題。花了不少時間，稍微記錄一下。

暴力遞歸O（2^N）不得了，怎么縮小規(guī)模呢？想到了同余類。

既然K最大只有100，那么建立一個bitset<102>nClass[102]是合適的，然后再將N縮成K的同余類。再利用歐拉定理將該類所能表示的同余類記錄下來。最后利用動歸逐類比較，找到可行表達。

逐類比較是O（K^3），這和咸魚有什么區(qū)別呢？
粗暴的dp也就是O（N*K），簡單明了。
所以，以上都是我自己的腦回路混亂之冗雜解法，是要堅決拋棄的。
最后的代碼很常規(guī)。之前寫的bug包括初始化沒定好，數(shù)組行列弄反導(dǎo)致RE。

時間：96ms，內(nèi)存：784kb，除了代碼短時間內(nèi)存過得去就沒有什么優(yōu)點了。

#include<iostream>
#include<bitset>
using namespace std;
bitset<10002>dp[102];
int main()
{
    int n,m,tmp,one,a,b;
    cin>>n>>m;
    dp[0][n]=1;
    while(n--)
    {
        cin>>tmp;
        a=(tmp%m+m)%m; 
        b=((-tmp)%m+m)%m;
        for(int i=0;i<m;++i)
        {
            if(dp[i][n+1]==1)
            {
                dp[(a+i)%m][n]=1;
                dp[(b+i)%m][n]=1;
            }
        }
    }
    if(dp[0][0]==1)cout<<"Divisible";else cout<<"Not divisible";
}