Writer 解説: https://img.atcoder.jp/agc039/editorial.pdf

問題概要

整数 $ N (\leq 2 \times 10^5)$，$ X (\lt 2^N)$ が与えられる．0以上X 以下のすべての整数 k (leading-zero あり) に対し次の操作を繰り返したとき，次に k に戻るまでの操作回数を足し合わせた値を 998244353 で割った値を求めよ．

操作

現在の値が奇数なら，1を引いて2で割る．
現在の値が偶数なら，2で割って $ 2^{N-1}$ を足す．

解法概要

問題の操作は，「一番下の桁の値を反転させて一番上の桁に移動させる」という操作を等価である．そのため，2N 回操作をすればどんな k でも元に戻る．

それでは，2N 回に満たない操作回数でも元に戻るような k はどんな条件を持っているだろうか．

例えば 001100 であれば，

100110
110011
011001
001100

のように，4回で元に戻る．

いくつか試してみると，2N 回に満たない操作回数でも元に戻るような k はあるビットパターンを p として p と ~p (ここでは p の各ビットを反転させたもの) の交互の繰り返しでできていることがわかる．では， p と ~p の交互の繰り返しであれば 2N 回に満たない操作回数で元に戻るかというと，実はそうでもない．

例えば 000111 であれば，

000011
000001
000000
100000
110000
111000
111100
111110
111111
011111
001111
000111

というように，元に戻るまで 12回かかる．

もう少し抽象化して考えてみると，p ~p p ~p ... p ~p というように p と ~p の交互の繰り返しでかつ p と ~p が同数になるような k の場合， p の長さ $|p| $ 回だけ操作を行うと p p ~p p ~p ... p となり， p 同士が隣り合ってしまう．これを解消して元に戻るにはここから $ N - |p| $回操作することで ~p p ~p p ... ~p p にして，さらに $ N $ 回操作しないと元に戻らない．つまり計 2N 回の操作必要になる．

一方，p ~p p ~p ... p というように p と ~p の交互の繰り返しでかつ p が1回多くなるような k の場合， $|p| $ 回だけ操作を行うと ~p p ~p p ~p ... ~p，さらに $|p| $ 回操作すると p ~p p ~p p ~p ... p と， $2|p| $ 回で元に戻る．

つまり， k が元に戻るまでの操作回数は k があるパターン p とそのビット反転 ~p の交互の繰り返しでかつ奇数個に分割できるとき，$2 |p| $ 回ということになる．

Writer 解説によると今回の問題の範囲内では N の奇数の約数はせいぜい72個とのことなので，間に合うようにプログラムを書くことができる．私の解は多分 $ O(Nd^2) $． ($ d $ は $ N $ の奇数の約数の数)

0以上X 以下の範囲内に収まっているかを確かめながら数えるには桁 DP が楽そう．他の桁 DP の問題でもよく見られるように，「すでにその桁よりも下の桁がどんな値になっていても X 以下であることが確定しているか？それとも未確定か？」のフラグを持って DP する．

また，同じ k を重複して数えないように気をつける必要がある．例えば 001100 は全体を3つに分割する場合 (ソースコード中の $ \mathit{divisors}_i = 3$) の場合にカウントされるが，何も考えずに DP をすると全体を 1 つに分割する場合にもカウントされてしまう．これを防止するには $ \mathit{divisors}_i $ を大きい順にみていき，もし前に見た場合のパターン長が今回のパターン長の約数となっていたら前に見た場合のパターン数を引けばよい．例えば，$ n = 6, \mathit{divisors}_i = 3$ のとき，パターン長は 2 である．これは $ \mathit{divisors}_i = 1$ のときのパターン長 6 の約数であるから，$ \mathit{divisors}_i = 1$ のときのパターン数を考える際には $ \mathit{divisors}_i = 3$ のときのパターン数を引く．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

using ll =  long long;

constexpr ll MOD = 998244353;

void get_odd_divisors(ll n, vector<ll> &divisors) {
    for(ll i=1;i*i<=n;++i) {
        if(n % i) continue;
        if(i % 2) divisors.push_back(i);
        if(i * i != n && (n/i) % 2) divisors.push_back(n/i);
    }
    return;
}

ll calc_patterns(ll d, ll n, string &s) {
    int pattern_length = n / d;
    vector<vector<ll>> dp(n+1, vector<ll>(2, 0));
    dp[n][0] = 1;
    for(int i=n;i>n-pattern_length;--i) {
        if(s[n-i] == '1') {
            dp[i-1][0] = dp[i][0];
            dp[i-1][1] = (dp[i][0] + (2 * dp[i][1]) % MOD) % MOD;
        } else {
            dp[i-1][0] = dp[i][0];
            dp[i-1][1] = (2 * dp[i][1]) % MOD;
        }
    }
    if(dp[n-pattern_length][0] == 0) return dp[n-pattern_length][1];
    for(int i=n-pattern_length;i>0;--i) {
        char pattern_c = s[(n-i)%pattern_length];
        if(((n-i) / pattern_length) % 2 == 1) {
            pattern_c = (pattern_c == '1') ? '0' : '1';
        }
        if(s[n-i] == '1') {
            if(pattern_c == '1') {
                dp[i-1][0] = dp[i][0];
            } else {
                dp[i-1][1] = dp[i][0];
            }
        } else {
            if(pattern_c == '1') {
                
            } else {
                dp[i-1][0] = dp[i][0];
            }  
        }
        dp[i-1][1] += dp[i][1];
        dp[i-1][1] %= MOD;
    }
    return (dp[0][0] + dp[0][1]) % MOD;
}

int main() {
    ll n;
    cin >> n;
    vector<ll> divisors;
    get_odd_divisors(n, divisors);
    string s;
    cin >> s;

    int nd = divisors.size();
    sort(divisors.rbegin(), divisors.rend());
    ll ans = 0LL;
    vector<ll> patterns(nd);
    for(int i=0;i<nd;++i) {
        int pattern_length_i = n / divisors[i];
        patterns[i] = calc_patterns(divisors[i], n, s);
        for(int j=0;j<i;++j) {
            int pattern_length_j = n / divisors[j];
            if(pattern_length_i % pattern_length_j == 0) {
                patterns[i] += MOD - patterns[j];
                patterns[i] %= MOD;
            }
        }
        ans += (((patterns[i] * pattern_length_i) % MOD) * 2) % MOD;
        ans %= MOD;
    }

    cout << ans << endl;
}

所感

「約数包除の問題を解くぞ！」って言って解いたのに約数包除を使わずに解いてしまったことにブログを書いてから気づいた．

NoiminのNoise

AtCoder Grand Contest 039 C - Division by Two with Something

問題概要

解法概要

ソースコード

所感