前言
今天练习赛出了这道题，由于我太菜没有在考场上做出来。
翻了题解后，感觉题解讲的并不是十分直观，所以自己写一篇。
题目大意
太长了，不讲了。
数据范围：
(1leq Nleq 400)
(1leq Cleq 400)
(1leq A_i,B_ileq 400)
解题思路
考虑 ( ext{DP})（至于为什么是 ( ext{DP}) 。。。靠经验吧）
设 (f[i][j]) 表示当前 ( ext{DP}) 到了第 (i) 个人，已经发了 (j) 个糖果的答案。
那么转移方程为：
[f[i][j]=sum_{k=0}^jf[i-1][j-k]left( sum_{x=A_i}^{B_i}x^k
ight)
]
这样来理解：
我们枚举一个 (k (0 leq k leq j))，表示我们当前这个人也就是第 (i) 个人分到了 (k) 个糖果。
我们需要在之前的 (i-1) 个人的答案中都乘上当前这个人的贡献：(sumlimits_{x=A_i}^{B_i}x^k)。
这就是转移方程的意义。
此外我们加一个前缀和优化就可以达到 (O(n^3)) 的复杂度。
细节注意事项
- 注意取模的问题，减法记得加一个模数再去模
- 中间运算记得用 ( ext{long long})
参考代码
/*--------------------------------
Author: The Ace Bee
Blog: www.cnblogs.com/zsbzsb
This code is made by The Ace Bee
--------------------------------*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= (c == '-'), c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
typedef long long LL;
const int p = 1000000007;
const int _ = 410;
int n, c, a[_], b[_];
LL pw[_][_], f[_][_];
int main() {
read(n), read(c);
for (rg int i = 1; i <= n; ++i) read(a[i]);
for (rg int i = 1; i <= n; ++i) read(b[i]);
for (rg int i = 1; i < _; ++i) pw[i][0] = 1ll;
for (rg int i = 1; i < _; ++i)
for (rg int j = 1; j < _; ++j)
pw[i][j] = 1ll * pw[i][j - 1] * i % p;
for (rg int i = 1; i < _; ++i)
for (rg int j = 0; j < _; ++j)
pw[i][j] = (pw[i][j] + pw[i - 1][j]) % p;
f[0][0] = 1;
for (rg int i = 1; i <= n; ++i)
for (rg int j = 0; j <= c; ++j)
for (rg int k = 0; k <= j; ++k)
f[i][j] = (f[i][j] + 1ll * f[i - 1][j - k] * (pw[b[i]][k] - pw[a[i] - 1][k] + p) % p) % p;
printf("%lld
", f[n][c]);
return 0;
}
完结撒花(qwq)