高速ゼータ変換に関する覚書き(その２)

問題特有のAdhocな部分の解説はしない
■典型
n進数での高速ゼータ変換

// 遷移
int x = 10;
rep(j, k) {//桁数
	int pw = 1;
	rep(i, j)pw *= x;
	rrep(i, sz) {
		// iの下からj桁目
		int num = (i / pw) % x;
		rep(k, num) {
			dp[i] += dp[i - pw * (num - k)];
		}
	}
}

整理すると

// 遷移
int x = 10;	
int pw = 1;
rep(j, k) {//桁数
	rep(i, sz) {
		if ((i / pw) % x)dp[i] += dp[i - pw];
	}
	pw *= x;
}

■ARC136D - Without Carry
考察を進めると10進数での高速ゼータ変換を行えばいいとわかる。
2進数のときと同じように考え、貰うdpで書いてみると以下。

// 遷移
rep(j, 6) {//桁数
	int ten = 1;
	rep(i, j)ten *= 10;
	rrep(i, 1000000) {
		// iの下からj桁目
		int num = (i / ten) % 10;
		rep2(k, 1, num + 1) {
			dp[i] += dp[i - ten * k];
		}
	}
}

少し無駄があるので改善をすると以下

// 遷移
rep(j, 6) {//桁数
	int ten = 1;
	rep(i, j)ten *= 10;
	rep(i, 1000000) {
		// iの下からj桁目
		int num = (i / ten) % 10;
		if (9 != num)dp[i + ten] += dp[i];
	}
}

貰うdpで書くなら以下

// 遷移
rep(j, 6) {//桁数
	int ten = 1;
	rep(i, j)ten *= 10;
	rep(i, 1000000) {
		// iの下からj桁目
		int num = (i / ten) % 10;
		if (0 != num)dp[i] += dp[i - ten];
	}
}

■ARC137D - Prefix XORs
考察を進めると包含しているものではなく、包含されているものについて考えればいいとわかる。
なので、基本的な高速ゼータ変換の逆(?)のようなもので以下のようにすればいい

// 遷移
rep(j, h) {//桁数
	rep(i, s) {//全要素
		if (1 & (i >> j))dp[i - (1 << j)] ^= dp[i];
	}
}

■ARC100E - Or Plus Max
iorj≦kに対しての問題を解きたい。
これは、iorj≦iなものについてまず考え、kまでの累積を考えればいい
なので、結局j⊂iなものについて考えればいいので

rep(i, 1 << n)dp[i] = { a[i],-INF };
// 遷移
rep(j, n) {//桁数
	rrep(i, (1 << n)) {//全要素
		if (1 & (i >> j)) {
			P l = dp[i];
			P r = dp[i & ~(1 << j)];
			if (l.second >= r.first) dp[i] = l;
			else if (r.second >= l.first) dp[i] = r;
			else dp[i] = { max(l.first,r.first),min(l.first,r.first) };
		}
	}
}
int ans = -INF;
rep2(i, 1, 1 << n) {
	ans = max(ans, dp[i].first + dp[i].second);
	cout << ans << endl;
}

■yukicoder No.896 友達以上恋人未満
倍数版

auto plist = sieve(1 << 24);
rep(i, plist.size()) {
	int p = plist[i];
	for (int j = ((1 << 24) / p)*p; j > 0; j -= p) {
		z[j / p] += z[j];
	}
}

■???
約数版

auto plist = sieve(n);
rep(i, plist.size()) {
	int p = plist[i];
        for(int j = 1;j * p < n;j++)){
               z[j * p] += z[j];
        }
}

流石にもう次は解けるやろ。。。