リンク:
beta.atcoder.jp
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
問題文
の範囲の数字個をそれぞれについて以上以下の好きな個数だけ黒板に書いたあと、次の操作を繰り返す。
・黒板に書かれている整数のうち、つ以上ある整数をつ消して、黒板にを1つ書く。
最終的につの整数が黒板に書かれているようにできるような整数の書き方は何通りあるかをで求めよ。
制約
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
操作を繰り返しても数字を大きくするしか出来ないことが分かる。
よって黒板に書かれた一番小さい数xは1個or偶数個である。
1個のときはそれより大きい数字は書かれていてはいけない。
偶数個のときは愚直に全部のをに変換すると、一番小さい数がになるため、この数について再び同じように考える。
これを繰り返すと、ある決まった整数の書かれ方について条件を満たしているか判定ができる。
ただしの各整数の書き方のパターンはおおよそなので膨大であり愚直な全探索はできない。
ただこのことから、が個あるとは個増えるということが分かるのでこの遷移を使ってを書く。
:= 整数が個黒板に書かれているような場合の数。
の範囲は初期状態のからに加えて、整数を操作したときのことも考慮してぐらい必要。
またの範囲は初期状態のからに加えて、操作を行い1つ小さい数字の半分の個数が加わることを考慮してぐらい必要(雑に漸化式を立てると分かる)
よってテーブルをとする。
の各整数はの個の範囲で好きに選べるため
また各整数が個のパターンは常に通りはあるため
遷移に関して。
整数が個あるとき、は個増えるので、整数が個のときを考えると
こうして遷移を終えた後のの和が答えとなる。
以下実装。
遷移の際、更新した値を他の遷移に影響させないために一時的な配列を用いている。
その他は愚直。
#include <iostream> #include <vector> using namespace std; using ll = long long; const ll MOD = (ll)1e9 + 7; int main() { int T; cin >> T; vector<ll> a(T+1,0); for(int i = 1;i <= T; ++i) { cin >> a[i]; } //dpテーブル vector<vector<ll>> dp(333, vector<ll>(601, 0)); //各iがa[i]個以下である書き方が1通りずつ for(int i = 1; i <= T; ++i) { for(int j = 1; j <= a[i]; ++j) { dp[i][j] = 1; } } //各iが0個である書き方が1通りずつ for(int i = 1; i <= 332; ++i) { dp[i][0] = 1; } //小さい方から見る for(int i = 1; i <= 332; ++i){ //一時的な配列 vector<ll> tmp(601, 0); //遷移 for(int j = 1; j <= 300; ++j) { for (int k = j; k <= 600; ++k) { (tmp[k] += (dp[i][k-j]*dp[i - 1][2*j])%MOD)%=MOD; } } //更新 for(int j = 1; j <= 600; ++j) { (dp[i][j] += tmp[j]) %= MOD; } } //iが1個になる場合の数を計算 ll ans = 0; for(int i = 1; i <= 332; ++i) { (ans += dp[i][1])%=MOD; } cout << ans << endl; return 0; }