くれなゐの雑記

身の回りの人や自分が困っていたことを記事にしています

SnackDown Elimination 2017 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;
}