yukicoder : No.2717 Sum of Subarray of Subsequence

これは自力ですんなり。
https://yukicoder.me/problems/no/2717

問題

N要素の整数列Aが与えられる。
Aの部分列2^N通りに対し、連続部分列を選ぶことを考える。その総和を求めよ。

解法

数列中の値A[i]がどれだけ解に寄与するかを考える。
連続部分列を取ったときの両端がA[L]、A[R]だったとする。

A[0]～A[i-1]の選び方が何通りあるかを考える。

• A[0]～A[L-1]は「部分列に入れるが連続部分列に入れない」か「部分列に入れない」かそれぞれ2通り
• A[L+1]～A[i-1]は「部分列に入れるが連続部分列にも入れる」か「部分列に入れない」かそれぞれ2通り

A[L]=A[i]の場合も考えると、A[0]～A[i-1]の取り方は
f(i) = i*2*(i-1)+2^i
となる。
A[i+1]～A[N-1]の選び方も同様にf(N-1-i)通りと考えることができる。

よって解はA[i]*f(i)*f(N-1-i)の総和となる。

int N,A[202020];
const ll mo=998244353;

ll pat[202020],p2[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,201010) p2[i+1]=p2[i]*2%mo;
	
	cin>>N;
	
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		ll lef=((i?(i)*p2[i-1]:0)+p2[i])%mo;
		y=N-1-i;
		ll ri=((y?(y)*p2[y-1]:0)+p2[y])%mo;
		
		(ret=ret+lef*x%mo*ri)%=mo;
	}
	cout<<ret<<endl;
	
	
	
}

まとめ

最初もっと難しく考えてしまったが、すぐ路線修正できてよかった。