AT2021 キャンディーとN人の子供 / Children and Candies

题目

传送门

题解

机房大佬好像有非常简单易懂的题解但是我不懂（雾
然后乱想了一下有了一点思路
是个DP
用f[k][n]表示把n个糖果分给k个孩子所得到的x[i]^a[i]的乘积的和（显然就是答案），
f[k-1][n-m]表示把n-m个糖果分给k-1个孩子得到的结果，也就是说给了第k个孩子m个糖果。
考虑转移，情况有两种：
1.a[i]==b[i]的情况，f[k][n] += f[k-1][n-m] * (a[i]^m)。
2.a[i]!=b[i]的情况，f[k][n] += f[k-1][n-m] * (a[i]^m + (a[i]+1)^m + ... + b[i]^m);
关键点是在如何处理这一部分：(a[i]^m + (a[i]+1)^m + ... + b[i]^m);
这里提供一种可行的 效率可观的 求法
sum[i]表示a^i+(a+1)^i+(a+2)^i+……+b^i;

void calc(int a,int b){
    memset(sum,0,sizeof(sum));
    for (int i(a);i<=b;++i){
        ll t=1;
        for (int j(0);j<=c;++j){
            sum[j]=sum[j]+t,sum[j]%=mod;//如果只是看看不懂的话建议手动模拟
            t=t*i%mod;//每一次操作t的幂数都+1
        }
    }
}

代码

#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
const int mod(1e9+7),maxn(405);
int n,c;
ll sum[maxn],f[maxn][maxn];
int a[maxn],b[maxn];
void init(){
    n=read(),c=read();
    for (int i(1);i<=n;++i) a[i]=read();
    for (int i(1);i<=n;++i) b[i]=read();
    f[0][0]=1;
}

void calc(int a,int b){
    memset(sum,0,sizeof(sum));
    for (int i(a);i<=b;++i){
        ll t=1;
        for (int j(0);j<=c;++j){
            sum[j]=sum[j]+t,sum[j]%=mod;
            t=t*i%mod;
        }
    }
}

signed main(){
    init();
    for (int i(1);i<=n;++i){
        calc(a[i],b[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]*sum[k])%mod;
    }
    printf("%d\n",f[n][c]);
    return 0;
}