【AtCoder Regular Contest 059 E】Children and Candies

mrsrz 2月 22, 2020

DP。

题目大意：

给定 $n$ 个人和 $a$ 个糖。

一个人喜悦值为 $x_i$，分到 $c$ 颗糖，则他的贡献为 $x_i^c$。一种分糖方案的总贡献为每个人的贡献的乘积。

定义 $f(x_1,x_2,x_3,\ldots,x_n)$ 表示每个人的喜悦值分别为 $x_1,x_2,x_3,\ldots,x_n$ 时，分完所有糖的所有不同方案的贡献之和。

求：

$\sum_{x_1=A_1}^{B_1}\sum_{x_2=A_2}^{B_2}\sum_{x_3=A_3}^{B_3}\cdots\sum_{x_n=A_n}^{B_n}f(x_1,x_2,x_3,\ldots,x_n)$

题解：

当确定一组 $x$ 的时候，我们可以直接做一个背包问题。时间复杂度 $O(n^3)$。

我们要求的是乘积的和，不难发现一个 $x$ 的所有取值是可以在一起计算的。

所以我们将所有取值一起算就好了。需要预处理 $k$ 次方前缀和。

时间复杂度 $O(n^3)$。

Code：

#include<cstdio>
typedef long long LL;
const int N=405,md=1e9+7;
int n,c,A[N],B[N],dp[N];
int pre[N][N],pw[N];
inline void upd(int&a){a+=a>>31&md;}
int main(){
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;++i)scanf("%d",A+i);
    for(int i=1;i<=n;++i)scanf("%d",B+i);
    dp[0]=1;
    for(int i=1;i<=400;++i)pw[i]=1;
    for(int i=0;i<=c;++i){
        int*P=pre[i];
        for(int j=1;j<=400;++j)upd(P[j]=P[j-1]+pw[j]-md),pw[j]=(LL)pw[j]*j%md;
    }
    for(int i=1;i<=n;++i){
        for(int C=c;~C;--C){
            int d=0;
            for(int j=0;j<=C;++j)
            d=(d+(LL)dp[C-j]*(pre[j][B[i]]-pre[j][A[i]-1]+md))%md;
            dp[C]=d;
        }
    }
    printf("%d\n",dp[c]);
    return 0;
}