要約
が与えられる.
: Memoryさんの初期点数
: 相手の初期点数
: 1ターンにの点数を得ることができる
: 2tターン行う
Memoryさんがかつことができるのは何通りか(MOD 1e9+7)
以下のようなdpを組む
その時間(time)で, Memoryさんのスコア-相手さんのスコアがdiffのときの場合の数
更新方法は簡単で,
- sumはしゃくとり的にやって計算量を減らす.
- 要素数は なので注意する(1敗)
最終的に, の部分がMemoryさんが勝つ場合の数なので,
が答えになる
配列の最大要素, くらいとっとけばいいと思ったけどなんかうまくいかなかった.
また, このままだと負の要素にアクセスすることになるので適当にオフセットかける
SourceCode
const int MOD = 1e9+7; void solve() { ll A, B, K, T; cin >> A >> B >> K >> T; //dp[time][diff] := cnt vector<vector<ll> > dp(2, vector<ll>(2*1000*(210) + 1)); int offset = 1000*(210); int cur = 0, tar = 1; if (A - B + offset <= 0) { cout << 0 << endl; return; } dp[tar][A-B+offset] = 1; for (int i = 0; i < 2 * T; ++i) { //REP(i, dp[tar].size()) cout << dp[tar][i]; //cout << endl; ll sum = 0; //全範囲更新 TLEしそうだったら頑張る しゃくとり的に REP(j, 2 * K+1) sum = (sum+dp[tar][j])%MOD; FOR(j, K, dp[cur].size()-K-1) { dp[cur][j] = sum; sum = (sum-dp[tar][j - K] + MOD)%MOD; sum = (sum+dp[tar][j + K + 1])%MOD; } swap(cur, tar); } //REP(i, dp[tar].size()) cout << dp[tar][i]; //cout << endl; ll res = 0; //REP(j, dp[tar].size()) { FOR(j,offset+1,dp[tar].size()){ res = (res + dp[tar][j]) % MOD; } cout << res << endl; }
謝辞, 参考
arrogantldiotさんのソースコードを参考にさせていただきました
codeforces.com