問題概要
関数 $\mathit{ popcount }$ を以下のように定める．
- $\mathit{ popcount }( n ) := $ $n$ を 2 進数表記シたときの $1$ の個数
また，関数 $f$ を，
- $f( n ) := $ $n$ を $n \bmod { \mathit{ popcount }( n ) }$ で置き換える操作を繰り返して，$n$ が $0$ になるまでの操作回数
とする．
2 進数表記で $N$ 桁の整数 $X$ が与えられる．意味のある全ての $i$ それぞれについて，$X$ の上から $i$ 桁目をビット反転した整数をそれぞれ $X_i$ とする．$f( X_1 ), f( X_2 ), \dots, f( X_N )$ を求めよ．
制約
- $1 \leq N \leq 2 \times 10^5$
解法
まず操作について考えてみます．整数 $n$ に対して一回操作を行うと，次に残る値は $\mathit{ popcount }( n )$ 未満になることから，操作のたびに $n$ のビット長は元々のビット長以下になっていくことになります（Leading zero を除いて）．従って，操作回数はそんなに大きくはならず，2 回目以降の操作時は $n \leq 2 \times 10^5$ なので，愚直にやったとしても問題ありません．なので問題となってくるのは一回目の操作をどのように扱うかです．
一回目の操作時，巨大な数を何らかの数で $\bmod$ する必要があります．ちょっとよく考えると，$\bmod$ の法は $\mathit{ popcount }$ の値から決まるので，1 ビット反転することと合わせると $\mathit{ popcount }( X ) \pm 1$ のいずれかになります．特定の法の上で $X$ を計算するだけならば，$X$ を上位ビットから舐めつつ，
- 答えを $2$ 倍する
- 答えに今見ているビットを足す
を適宜 $\bmod$ をとりながらやってあげれば求まります．同じようなことは下位ビットから行うこともできて，右から $i$ ビット目までだけを読んだ場合の $X$ の値を $X_r( i )$ とし（便宜上 $X_r( -1 ) = 0$ とする），$X$ の右から $i$ ビット目を $X[i]$ とすれば，
- $X_r( i ) = X_r( i - 1 ) + X[i] 2^i$
という風に計算できます（右から走査して，新しく読んだビットに対応する 2 冪をかけて足していく）．この値を前計算しておくと，上から走査して $X$ を構成している最中に，「残りのビット分を全部まとめて足し込む」ということができるようになります．これができれば，構成途中の $X$ に，着目しているビットを反転させた値を足し，残りのビットをまとめて足すことができるようになり，一回目の操作を高速に処理できるようになります．
より具体的には，左から $i$ ビット目を見ているとき，上記の構成方法で構成途中の $X$ を $X_l$ とします．ここでやるべきことは，
- $X_l$ に $2 ^ { N - i }$ をかけて，最後まで読み切った場合のビットの位置までシフトさせる
- $( 1 - X[i] ) 2^{ N - 1 - i }$ を足して，着目ビットを反転したものを適切にシフトしつつ足す
- $X_r( i + 1 )$ を足して，残りのビットの分をまとめて足す
というのを，適切な法の上で行えば一回目の操作を高速に処理できます．2 回目以降は愚直に処理できるので，これで問題を解けます．
計算量としては，2 パスあるそれぞれで $N$ 回 $2^i$ を計算していて，ここに反復自乗法を用いれば $O( N \log N )$ 時間となります．また，操作の回数の総和も同じ上界をもつので，全体でも $O( N \log N )$ 時間です．
コード
// a^x を mod で求める // 反復二乗法 // O( log x ) long long mod_pow( long long a, long long x, long long mod ); int solve( int n ) { int res = 1; for ( ; n; n %= __builtin_popcount( n ) ) { ++res; } return res; } int main() { IN( int, N ); IN( string, S ); const int popcount = count( ALL( S ), '1' ); if ( popcount == 0 ) { REP( N ) { cout << 1 << '\n'; } cout << flush; return 0; } const int mod_m = 1 < popcount ? popcount - 1 : 1; const int mod_p = popcount + 1; VT< LL > rest_m( N + 1 ), rest_p( N + 1 ); for ( LL i = 0; i < N; ++i ) { const int D = S[ N - 1 - i ] - '0'; rest_m[ N - 1 - i ] = ( rest_m[ N - i ] + D * mod_pow( 2, i, mod_m ) ) % mod_m; rest_p[ N - 1 - i ] = ( rest_p[ N - i ] + D * mod_pow( 2, i, mod_p ) ) % mod_p; } LL a = 0, b = 0; REP( i, N ) { const int D = S[i] - '0'; if ( D ) { if ( popcount == 1 ) { cout << 0 << '\n'; } else { cout << solve( ( a * mod_pow( 2, N - i, mod_m ) % mod_m + rest_m[ i + 1 ] ) % mod_m ) << '\n'; } } else { cout << solve( ( b * mod_pow( 2, N - i, mod_p ) % mod_p + mod_pow( 2, N - 1 - i, mod_p ) + rest_p[ i + 1 ] ) % mod_p ) << '\n'; } ( a *= 2 ) %= mod_m; ( a += D ) %= mod_m; ( b *= 2 ) %= mod_p; ( b += D ) %= mod_p; } cout << flush; return 0; }
