dp

之前看了，雨神的关于dp优化的思路视频。感觉很神奇。就在cf上做了一做。
磕磕碰碰。。
但是，确实思路是雨神说的。
首先对于这道题，我们要判断是否可以取出一些数其和能整除m
直接设状态方程dp[i][j]即到第i个为止是否能够凑出符合要求的数。
对于这种能否凑出来整除的题，我们往往有一个技巧就是先进行取模。
这会方便许多，这样只要我们能凑出来0即dp[i][0]=true那么就能满足。
那么怎么转移状态方程呢？dp[i][j] = dp[i-1][?]|dp[i-1][?]
这里有一个技巧，我们这样写状态转移方程是十分困难的。
所以，我们不妨这样dp[i][j] = true 那么dp[i+1][j]=true dp[i+1][(j+a[i+1])%m]=true
我们从后面像前面转移。这样会方便很多，也不容易出错。

我们想的很好，但是啊，看一看数据范围会发现这是1e9级别的。
很明显是不可行的。

那么我们要进行dp的优化了！
首先显然！看到了吗显然！这是雨神说的思路。我们回到问题，看问题的的本质。
我们发现，当n>=m时，一定时存在的！
为什么呢？
首先我们对前缀和进行取余，那么这n个前缀和的余数范围在0到m-1。

因为我么没有0，所以一旦出现0那么就YES

而因为n>=m所以一定有两个余数一样的前缀和，那么这两个前缀和相减，就是0.
这意味着就是这两个前缀和所夹的区间，满足条件。

因此,只有n<m时我们才有必要进行动态规划。
时间复杂度为O(m^2)

优化成功