AOJ 2595 Cookie Counter

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2595

解法

1枚も食べない日を考えるとややこしい（し，Dがでかいのでそのまま求められない）ので，D 日のうち一枚も食べない日はあとで決めることにすればよい．
つまり，まずは一日に最低1枚は食べる場合の数を求める．すると，必ずN日目までには食べきるので，O(N^2) の DP に落とし込めそう．
dp[i][j] := i 日目までに j 枚のクッキーを食べる場合の数
としてDPする．一日に X 枚"未満"だけ食べられるので，以下の遷移が成り立つ．
dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-X+1]
これを愚直に書くと O(N^3) だが，よく見ると単純に区間和を求めているだけなので，累積和を取れば O(N^2) にできる．

最後に，一日に食べない日を D 日のうちから決めるのだが，D がでかいので Cmb(D, 1) から Cmb(D, min(N, D)) まで順番に求めていけば O(N) で求められる．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
constexpr ll M = 1e9+7;
 
// calc x
// ax %% 1 (mod M)
ll inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
 
int main() {
    ll N, D, X;
    while(cin >> N >> D >> X, N) {
        vector<vector<ll>> dp(N+1, vector<ll>(N+1));
        dp[0][0] = 1;
        vector<vector<ll>> dp_sum(N+1, vector<ll>(N+1));
        fill(dp_sum[0].begin(), dp_sum[0].end(), 1);
        for(int i=1; i<=N; ++i) {
            for(int j=i; j<=N; ++j) {
                if(j-X >= 0) {
                    dp[i][j] = (dp_sum[i-1][j-1] - dp_sum[i-1][j-X] + M) % M;
                } else {
                    dp[i][j] = dp_sum[i-1][j-1];
                }
            }
            for(int j=1; j<=N; ++j) {
                dp_sum[i][j] = (dp_sum[i][j-1] + dp[i][j]) % M;
            }
        }
        ll res = 0;
        ll cmb = 1;
        for(int i=1; i<=min(N, D); ++i) {
            cmb = (cmb * ((D-i+1) % M)) % M;
            cmb = (cmb * inv(i, M)) % M;
            res = (res + dp[i][N] * cmb) % M;
        }
        cout << res << endl;
    }
}