[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 的墓碑 - 洛谷博客