[ARC059E] Children and Candies 题解

题目链接：[ARC059E] Children and Candies

题意：

给出 $N,C,A_i,B_i$ ，求

$$\sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} \ldots \sum_{x_N=A_N}^{B_N} f\left(x_1, x_2, \ldots, x_N\right)$$

其中 $f$ 定义为 $\prod x_1^{a_1}x_2^{a_2}\cdots x_N^{a_N}$ ，其中 $\sum_{i}a_i=C$ 。

$1 \le N,C \le 400,~1 \le A_i \le B_i\le 400(1\le i\le N)$

容易发现 $n$ 自增一次对答案的影响可以通过 $n$ 的答案得到（这行是废话）

考虑设 $f_{i,j}$ 表示前 $i$ 个人，发了 $j$ 个糖果（就是那个 $\sum_i a_i$）的答案，则

$$f_{i,j} = \sum_{k = 0}^{j}f_{i-1,j-k} \times \sum_{x=A_i}^{B_i}x^k$$

显然后者可以预处理。（听说前者也能用多项式优化，害怕）

时间复杂度 $\mathcal{O}(n^3)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(415))

const int m = 405;
int n,c,a[N],b[N],f[N][N],pwd[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> c;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    
    for(int i = 1; i < m; i++) pwd[i][0] = 1;
    for(int i = 1; i < m; i++)
        for(int j = 1; j < m; j++) pwd[i][j] = pwd[i][j - 1] * i % mod;
    for(int i = 1; i < m; i++)
        for(int j = 0; j < m; j++) pwd[i][j] = (pwd[i][j] + pwd[i - 1][j]) % mod;
    
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= c; j++)
            for(int k = 0; k <= j; k++)
                f[i][j] = (f[i][j] + f[i - 1][j - k] * (pwd[b[i]][k] - pwd[a[i] - 1][k] + mod) % mod) % mod;
    cout << f[n][c] << '\n';
    return 0;
}

---

参考文献：

[1] ARC059C - Lillia 的墓碑 - 洛谷博客