题目：给n个范围，第i个范围选pi，然后定义特征值k=p1+p2+...+pn。这次的开心度就是A(k%m)。m是给的一个数组A，长度为m。

 

要求：

 

 

就是个全排列组合的问题，找规律。

 

举个例子，有n个礼物，分别是(L1，R1) (L2, R2) (Ln, Rn)

  1. 每个区间取个数然后相加，所有出现的结果，其实就是A[L1+L2+...Ln], A[L1+L2+...Ln+1] ...... A[R1+R2+....+Rn]
  2. 就是这些每个区间的最小值到这些区间最大值，就是这些结果，关键就是每个结果出现了多少次？
  3. 多少次其实就是一个组合数，比如A[L1+L2+...Ln+1]这个结果出现了多少次？也就是这个+1的这个1是由哪个区间提供，就想成有这么多座位：tot = R1+R2+..+Rn - L1-L2-...Ln，要占一个座位，随便占一个的可能性为C(tot, 1)
  4. 知道了3就知道算A[L1+L2+...Ln + x]出现的情况了，其实就是C(tot, x)

 

算一下复杂度：

　　C(tot, i)的复杂度：这个每次都是在C(tot, i-1)地基础上算，很简单，直接忽略

　　也就是for循环一下从L1+L2+...Ln到R1+R2+....+Rn，这也就1e8

结果就是这样：

for(int i = totl, j = 0; i <= totr; i++, j++)

　　ans = (ans + C(totr-totl, j) %mod * A[i%m] % mod) % mod;