■A - Coprime Pair 幅が大きい方から試すしかなさそう。 計算量が間に合うかどうかが問題。 問題の成約の下では、1500以上のサイズの素数砂漠は存在しないので間に合う。 ■B - Count 1's ここからここまでの区間をひっくり返すとどんだけ差分が出るかを考え…

問題特有の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)]; } …

二週連続で食らったので 以下全て問題は 長さ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][…