AOJ 0537 Bingo

解説

言い換えると
$1 \leq a_1 < a_2 < \ldots < a_n \leq M $
$a_1 + a_2 + \ldots + a_n = S$
をみたす $a_n$ の作り方を求める問題で,O(NMS) の解法はすぐわかると思いますが,実は O(NS) で解けます.
分割数のイメージでやるとよいです.DPでやることには変わりません.
dp[i][j] := i 個の異なる数(M以下の数)で,総和を j にする組み合わせ
とすると,遷移は
dp[i][j] = dp[i - 1][j - i] + dp[i][j - i] - dp[i - 1][j - M - 1]
となります.
第1項は,すでに出来ている i - 1個のそれぞれに 1 を加算し,i 番目に 1 を付け加えるという操作を表します.
第2項は,すでに出来ている i 個の数のそれぞれに 1 を加算してできるという意味を表します.
最後の項は,1を加算したことで M を超えるような場合の数を取り除くためのものです.dp[i][j] で M を超えるとしたら,遷移の仕方からその値は M + 1 で,かつその1つだけです.そのような場合の数は,他の i - 1 個の総和が j - M - 1 で,かつ M を超えるものが無い場合なので,dp[i - 1][j - M - 1] に対応します.

以上で O(NS) で解けました.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

constexpr int mod = 1e9 + 7;

int main() {
    int N, M, S;
    while(cin >> N >> M >> S, N) {
        vector<vector<int>> dp(N * N + 1, vector<int>(S + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= N * N; ++i) {
            for(int j = 0; j <= S; ++j) {
                if(i <= j) {
                    dp[i][j] += dp[i][j - i] + dp[i - 1][j - i];
                }
                if(j - M - 1 >= 0) {
                    dp[i][j] -= dp[i - 1][j - M - 1];
                }
                dp[i][j] = (dp[i][j] + mod) % mod;
            }
        }
        cout << dp[N * N][S] << endl;
    }
}

感想

制約を N <= 100, S <= 10^5, M <= 10^5 にするだけで解けなくなる人が出てきそう.