[dp+樹狀數組優化] LightOJ 1145 - Dice (I)

題意：給n個骰子，每個骰子有k個面，分别标上1～k，要求n個骰子和為s的方法數。其中1 <= n, k <= 1000, 1 <= s <= 15000。

題解：DP。令DP[i][j]表示前i個骰子和為j的方法數。

DP[1][j] = 1 ( 1 <= j <= k )

DP[i][j] = SUM( DP[i-1][j-p] ) ( 1 <= p <= k && j-p >= 1) 或者 DP[i+1][j+p] += DP[i][j] ( 1 <= p <= k && j+p <= s )

很容易看出這是一個個n*k*s的DP，但是注意到前一種轉移寫法裡面有SUM，可以用樹狀數組維護。

其實這個可以O(1)維護，強行加log之後複雜度n*k*log(s)，資料太弱，成功達成Statistics倒數第一。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using std::min;
const int mod = 100000007;
const int MX = 15005;
int tree[2][MX];
void update(int rt, int pos, int v){
    for(; pos < MX; pos += pos&-pos){
        tree[rt][pos] += v;
        if(tree[rt][pos] >= mod) tree[rt][pos] -= mod;
    }
}
int getsum(int rt, int pos){
    int res = 0;
    for(; pos > 0; pos -= pos&-pos){
        res += tree[rt][pos];
        if(res >= mod) res -= mod;
    }
    return res;
}
int main(){
    int T, ca = 1;
    scanf("%d", &T);
    while(T--){
        int n, k, s;
        scanf("%d%d%d", &n, &k, &s);
        memset(tree, 0, sizeof(tree));
        for(int i = 1; i <= k; ++i) update(1, i, 1);
        int fg = 0;
        for(int i = 2; i <= n; ++i, fg ^= 1){
            int up = min(s, i*k);
            memset(tree[fg], 0, sizeof(tree[fg]));
            for(int j = i; j <= up; ++j){
                int tmp = getsum(fg^1, j-1) - getsum(fg^1, j-k-1);
                if(tmp >= mod) tmp -= mod;
                else if (tmp < 0) tmp += mod;
                update(fg, j, tmp);
            }
        }
        printf("Case %d: %d\n", ca++, (getsum(fg^1, s) - getsum(fg^1, s-1)+mod)%mod);
    }
}