数组共有n个元素，每个元素范围从L到R(包括边界点),所有元素之和为k的倍数，请问有多少个这样的数组？（结果对取余数）

数据范围

笔试的时候没做出来，最后想到了动态规划，但是写错了，后面自己再写了一遍，不知道对不对，仅供参考！

首先将从L到R中的每个数对k取余数，把余数相同的数分为一组，这样就可以把从L到R中所有的数分成k组了，使用一个数组f[0,...,k-1]记录余数为0,...,k-1的组的个数。

假设使用dp[i][j]代表第前i个数之和除以k余j的种数，那么递推方程为：

注意到第t组中任意一个数只有和第(j-t)%k组中任意一个数相加后除以k的余数才是j，最后dp[n][0]就是结果，参考代码。

#include h>  using  namespace  std;  long  long  MOD  =  1e9L; long  long  dp[2][100];  //只和前面的状态有关 long  long  cnt[100];  int  main() {  int  n, k, L, R;  cin  >>  n  >>  k  >>  L  >>  R;  int  num  = (R  -  L  +  1) /  k;  for (int  i  =  0; i    k; i++) cnt[i] =  num;  for (int  i  =  num  *  k  +  L; i    R; i++) cnt[i  %  k]++;//统计从L到R中除以k余i的数的个数  for (int  i  =  0; i    k; i++) dp[0][i] =  cnt[i];  for (int  i  =  1; i    n; i++) {  for (int  j  =  0; j    k; j++) {  dp[1][j] =  0;  for (int  t  =  0; t    k; t++)   dp[1][j] = (dp[1][j] +  dp[0][t] *  cnt[(j  -  t  +  k) %  k]) %  MOD;         }         for (int j = 0; j  k; j++) dp[0][j] = dp[1][j];     }     cout  dp[0][0]  endl;     return 0; }