問題要約(相方担当)
- N個の数列が与えられる
- それぞれの数の間に"*" か "+"を入れた式を作る(通りの式ができる)
- 個の式の総和 MOD を出力せよ.
概要
なんとなくDPで解けそうだったので適当にやったら遷移できた
実験
を,数列を左から個読み込んだ時の式の総和とする.
とする
1つの要素の数列が与えられ,その間に"*"か"+"を挿入すると,
またこの総和をとする.
2つの要素の数列が与えられ,その間に"*"か"+"を挿入すると,
またこの総和をとする.
3つの要素の数列が与えられ,その間に"*"か"+"を挿入すると,
またこの総和をとする.
0->1の遷移に注目すると
1->2の遷移に注目すると
2->3の遷移に注目すると
との部分とそれ以外の部分()に分けることができた.
それ以外の部分もDPで求めることが出来る 具体的な証明や導出は省略するが,今回の場合は
と新たに増えた要素を使って簡単に表記できる.に係数2が付いているが,これは注目している数列の個数をとすると,となる.
大体法則性がわかったので一般化する.N個の数列をではなく, と表記する.
に関するDP遷移は以下のようになる.
では
に関するDP遷移は以下のようになる.
では
ここで,にかかってしまうので,計算しながらメモすることによってにする.
総計算オーダーはとなり,これで間に合う.
ソースコード
実は実装ミスって上のやつと添字がちょっと違う
void solve() { int N; cin >> N; vector<int> v; REP(i, N) v.push_back(in()); vector<int> twoPow(N); vector<int> m(N); twoPow[0] = 1; FOR(i, 1, N) twoPow[i] = twoPow[i - 1] * 2 % MOD; vector<int> dp(N), dpsum(N); dp[0] = v[0]; dpsum[0] = v[0]; m[0] = v[0]; FOR(i,0,N-1){ m[i + 1] = ((m[i] * v[i + 1])%MOD + (twoPow[i] * v[i + 1])%MOD)%MOD; dp[i + 1] = (dpsum[i] + m[i+1])%MOD; dpsum[i + 1] = (dpsum[i] + dp[i + 1])%MOD; } cout << dp[N - 1] << endl; }