結構難しい!!
問題概要
正の整数 に対して、
- := を二進法表現したときの各桁の総和を として を で割ったあまり
- := を で置き換える操作を繰り返したときに、何回で 0 になるか
として定める。たとえば のとき、, より、 となる。
今、二進法表記で 桁の整数 が与えられる。各 に対して、 の上から 桁目をビット反転した値 に対する の値を求めよ。
制約
考えたこと
とりあえず、とりあえず に対して一回 をとると 以下の整数にはなる。よって、 の値は小さそうだという予想はつく。1 つの整数に対して求めるだけなら愚直にシミュレーションしてもよさそう。
また、 を各桁ごとにビット反転することにる変化は
- の値は ±1 しか変化しない
- 自体の値も しか変化しない
ということがわかる。よって、この差分は高速に計算できる。
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } long long p(long long n) { long long nn = n, con = 0; while (nn) { con += nn % 2; nn /= 2; } return n % con; } long long f(long long n) { long long res = 0; while (n) { ++res; n = p(n); } return res; } int main() { int N; string S; cin >> N >> S; long long defa = 0; for (auto c : S) defa += c-'0'; vector<vector<long long>> power(3, vector<long long>(N, 1)); for (int iter = 0; iter < 3; ++iter) { long long base = defa + iter - 1; if (base <= 0) continue; for (int i = 0; i < N-1; ++i) { power[iter][i+1] = power[iter][i] * 2 % base; } } vector<long long> origin(3, 0); for (int iter = 0; iter < 3; ++iter) { long long base = defa + iter - 1; if (base <= 0) continue; for (int i = 0; i < N; ++i) { if (S[i] == '1') { origin[iter] = (origin[iter] + power[iter][N-i-1]) % base; } } } for (int i = 0; i < N; ++i) { long long base = defa, iter = 1; if (S[i] == '0') ++base, ++iter; else --base, --iter; if (base <= 0) { cout << 0 << endl; continue; } long long one = origin[iter]; if (S[i] == '0') one = (one + power[iter][N-i-1]) % base; else one = (one - power[iter][N-i-1] + base) % base; cout << f(one)+1 << endl; } }