AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies

問題

arc059.contest.atcoder.jp

解法

まず部分点解法を考えてみますと, dp[i][rest] = (i 番目まで考えた時点でべき乗する数が C から rest まで減っているような時の和) というのを考えると, この i 番目でべき乗する数をいくつ使うかで場合分けして A[i]^j * dp[i+1][rest-j] というのの和を取れば良いことがわかります。

満点解法では A[i] <= Xi <= B[i] を満たすものすべてを扱わなければなりませんが, これは上記の A[i]^j というのを A[i]^j + (A[i]+1)^j ... + B[i]^j とすれば良いです(a*c + a*d + b*c + b*d = (a+b) * (c+d) みたいのと同じ考え方)。あらかじめ累積和を取っておけばこれは上と変わらない計算量で求められるので間に合います。

ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

const int MAXN = 404;
const int MOD = 1e9+7;
int A[MAXN], B[MAXN];
int N, C;

ll memo[MAXN][MAXN];
ll sum[MAXN][MAXN];
ll dp[MAXN][MAXN];

ll dfs(int now, int rest) {
    ll& ret = dp[now][rest];
    if (ret >= 0) return ret;
    if (now == N-1) {
        //return ret = memo[A[now]][rest];
        ret = sum[B[now]+1][rest] - sum[A[now]][rest];
        ret = (ret%MOD+MOD)%MOD;
        return ret;
    }
    ret = 0;
    for (int i = 0; i <= rest; i++) {
        //ll tmp = memo[A[now]][i];
        ll tmp = sum[B[now]+1][i] - sum[A[now]][i];
        tmp = (tmp%MOD+MOD)%MOD;
        tmp *= dfs(now+1, rest-i);
        (ret += tmp%MOD) %= MOD;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXN; j++) {
        memo[i][j] = mod_pow(i, j, MOD);
    }
    memset(sum, 0, sizeof(sum));
    for (int i = 0; i < MAXN; i++) {
        for (int j = 1; j < MAXN; j++) {
            sum[j][i] = sum[j-1][i] + memo[j-1][i];
            sum[j][i] %= MOD;
        }
    }
    cin >> N >> C;
    for (int i = 0; i < N; i++)
        cin >> A[i];
    for (int i = 0; i < N; i++)
        cin >> B[i];
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, C) << endl;
    return 0;
}