747.Divisibility

这是一篇水水的无干货文章 题目地址

描述
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）不得了，怎么缩小规模呢？想到了同余类。

既然K最大只有100，那么建立一个bitset<102>nClass[102]是合适的，然后再将N缩成K的同余类。再利用欧拉定理将该类所能表示的同余类记录下来。最后利用动归逐类比较，找到可行表达。

逐类比较是O（K^3），这和咸鱼有什么区别呢？
粗暴的dp也就是O（N*K），简单明了。
所以，以上都是我自己的脑回路混乱之冗杂解法，是要坚决抛弃的。
最后的代码很常规。之前写的bug包括初始化没定好，数组行列弄反导致RE。

时间：96ms，内存：784kb，除了代码短时间内存过得去就没有什么优点了。

#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";
}