高速ゼータ変換に関する覚書き

二週連続で食らったので
以下全て問題は
長さ2^nの配列Aが与えられ
各iに対して、j⊂iを満たすAjの和とする。
①まず愚直解

rep(i, 1 << n) {
	int ans = 0;
	rep(j, 1 << n) {
		if (j == (i& j))ans += a[j];
	}
	cout << ans << endl;
}

②高速ゼータ変換

/*
	dp[i][j]:=k⊂iを満たし、kの下からj番目以上のbitの状態がiとおなじになるような集合に対してのans
	つまり、0==jのときk=iなのでdp[i][0] = a[i]であり、求めたいものはdp[i][n]

	遷移は以下(貰うdp)
	iの下からj番目のbitが立っているならそこが0のものと1のものがdp[i][j+1]
	iの下からj番目のbitが立ってないならそこが0のものがdp[i][j+1]
	計算量は、O(2^n*n)
*/
vector<vector<int>> dp(1 << n, vector<int>(n + 1));
// 初期化
rep(i, 1 << n)dp[i][0] = a[i];
// 遷移
rep(j, n) {
	rep(i, 1 << n) {
		if (1 & (i >> j)) dp[i][j + 1] = dp[i & ~(1 << j)][j] + dp[i][j];
		else dp[i][j + 1] = dp[i][j];
		}
	}
}
rep(i, 1 << n)cout << dp[i][n] << endl;

③配列を使い回すことでメモリを軽減させる

/*
	次にメモリを軽減するO(n*2^n)->O(2^n)
*/
vector<int>dp(1 << n);
// 初期化
rep(i, 1 << n)dp[i] = a[i];
// 遷移
rep(j, n) {
	rep(i, (1 << n)) {
		if (1 & (i >> j))dp[i] += dp[i & ~(1 << j)];
	}
}
rep(i, 1 << n)cout << dp[i] << endl;