Codeforces #225(383 Div1) D. Antimatter

問題

長さnの数列a[i]が与えられる。
aの任意の空でない区間[l, r]で、a[i]の符号を好きに反転してよい。
このようにして[l, r]内の総和が0になるようにする方法は何通りあるか。

制約条件

n≦1000
-1000≦a[i]≦1000
a[i]の総和≦10000

方針

Div1 D史上最も酷い問題？
dp[pos][sum] := [x, pos]の和をsumにする場合の数。xは1〜pos全部
とするだけ。

ソースコード

const int mod = inf + 7;
int n, a, dp[2][20001];

int main(){
	scanf("%d", &n);
	int cur = 0, next = 1;
	ll ans = 0;
	
	rep(i, n){
		scanf("%d", &a);
		memset(dp[next], 0, sizeof(dp[next]));
		rep(j, 20001) if(dp[cur][j]){
			(dp[next][j + a] += dp[cur][j]) %= mod;
			(dp[next][j - a] += dp[cur][j]) %= mod;
		}
		ans += dp[next][10000];
		dp[next][10000 + a]++;
		dp[next][10000 - a]++;
		swap(cur, next);
	}
	cout << ans % mod << endl;
	
	return 0;
}

余談

writerの想定解は分割統治だったらしく、
(l, r)の場合の数は、m = (l + r) / 2を区間がまたがない場合とまたぐ場合。
前者は(l, m), (m, r)を解けばよく、
後者は、(l, m), (m, r)でナップサックをして、それぞれで和がxになる場合の数をcnt[x] = Σdp[i][x]としてまとめ、cnt[x]同士をかける。

これでO(n m log n).