SnackDown Elimination 2017 PLUSMUL - くれなゐの雑記

問題

https://www.codechef.com/SNCKEL17/problems/PLUSMUL

問題要約(相方担当)

N個の数列が与えられる
それぞれの数の間に"*" か "+"を入れた式を作る( $2^{N-1}$ 通りの式ができる)
$2^{N-1}$ 個の式の総和 MOD $10^9+7$ を出力せよ．

概要

なんとなくDPで解けそうだったので適当にやったら遷移できた $\mathcal{O}(N)$

実験

$dp[n]$ を，数列を左から $n$ 個読み込んだ時の式の総和とする．
$dp[0] = 0$ とする

1つの要素の数列 $a$ が与えられ，その間に"*"か"+"を挿入すると，
$a$
またこの総和を $dp[1]$ とする．

2つの要素の数列 $a,b$ が与えられ，その間に"*"か"+"を挿入すると，
$a+b$
$ab$
またこの総和を $dp[2]$ とする．

3つの要素の数列 $a,b,c$ が与えられ，その間に"*"か"+"を挿入すると，
$a+b+c$
$ab+c$
$a+bc$
$abc$
またこの総和を $dp[3]$ とする．

0->1の遷移に注目すると
$dp[1] = dp[0] + a = dp[0] + x[0]$
1->2の遷移に注目すると
$dp[2] = dp[1] + (ab + b) = dp[1] + x[1]$
2->3の遷移に注目すると
$dp[3] = dp[1] + dp[2] + (2c+bc+abc) = dp[1]+dp[2] + x[2]$

と $dp$ の部分とそれ以外の部分( $x$ )に分けることができた．
それ以外の部分もDPで求めることが出来る具体的な証明や導出は省略するが，今回の場合は
$x[0] = a$
$x[1] = x[0]*b + b$
$x[2] = x[1]*c + 2c$
と新たに増えた要素を使って簡単に表記できる． $c$ に係数2が付いているが，これは注目している数列の個数を $M$ とすると， $2^{M-2}$ となる．

大体法則性がわかったので一般化する．N個の数列を $a,b,c...$ ではなく, $v[i]$ と表記する．
$x$ に関するDP遷移は以下のようになる．
$x[0] = v[0]$
$i>0$ では
$x[i] = x[i-1] \times v[i] + 2^{i-1} \times v[i]$
$dp$ に関するDP遷移は以下のようになる．
$dp[0] = 0$
$i>0$ では
$dp[i] = \sum_{j=0}^{i-1} dp[j] + x[i-1]$

ここで， $\Sigma$ に $\mathcal{O}(N)$ かかってしまうので，計算しながらメモすることによって $\mathcal{O}(1)$ にする．

総計算オーダーは $\mathcal{O}(N)$ となり，これで間に合う．

ソースコード

実は実装ミスって上のやつと添字がちょっと違う

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;
}