Codeforces #701 Div2 : F. Copy or Prefix Sum

あれ、Eより簡単？
https://codeforces.com/contest/1485/problem/F

問題

整数列Bが与えられる。
これに対応し、以下のいずれかを満たす数列Aは何通りか。

• B[i]=A[i]
• B[i]=sum(A[0...i])

解法

Aを1個ずつ決めていくと、基本的には上記2通りの値が考えられる。
ただし、A[0...(i-1)]の状態によっては、どちらも同じ値になるので、その分を適宜引いていこう。

int T,N;
const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll offset=0;
		ll S=0;
		map<ll,int> M;
		M[0]=S=1;
		FOR(i,N) {
			cin>>x;
			ll add=S+mo-M[-offset]%mo;
			offset+=x;
			(M[x-offset]+=add)%=mo;
			(S+=add)%=mo;
		}
		cout<<S<<endl;
	}
}

まとめ

Div2とはいえ最終問題の割に簡単。