题目描述

塔子哥最近一直在学习数组，突然有了一个想法，他定义了一个“特别数组”，当且仅当满足以下三个条件:

1. 对于$1 \leq i \leq n，有1 \leq a_i \leq m$

思路：动态规划题

给出n和m的值，要求求出一个"特别数组"的数量，并对1e9+7取模

其实并没有什么其他好计算的办法，那么就想到动态规划能否解决问题，首先n和m的范围都在1000以内，那么代表支持$O(n^2logn)$的时间复杂度，那么dp的第一维肯定是我们有多少个数，另外"特别数组"是所有数加起来是n的倍数，也就是说模n为0，那么第二维就可以设置成当前所有数加起来模n为多少

所以我们设dp[i][j]，表示当前一共有i个数并且所有数加起来模n为j的数组的数量，那么在转移的时候可以枚举i与j和当前最后一个数是多少，最后一位数一定是i的倍数，所以我们可以用一个调和级数的时间复杂度去枚举它，最后答案即为dp[n][0]

转移方程为