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 にするだけで解けなくなる人が出てきそう.