GoogolS0です。
AGC039-Cについての理解をもっと深めようと思い、この問題の解説を書くことにしました。わかりにくかったらすみません。
問題
$X$以下の非負整数に対して、次の操作を最小何回行ったら元に戻るか(戻らない場合$0$)の和を$mod\ 998244353$で求めなさい。
・現在の整数が奇数なら$1$を引き$2$で割る。そうでなければ、$2$で割り$2^{N-1}$を足す。
解説
まず、この操作を$f$と表すことにします。
ここで、この操作は次のように言い換えられます。(ただし、$A$は$2$進数で$N-1$桁の数とします。また、この先$2$進数で$k$桁の数と表されうる数は、$2^k$未満の非負整数の二進数表記に$k$桁になるまでleading zeroをつけたもののみとします。)
- $f(A1)=0A$
- $f(A0)=1A$
この言い換えができることを示します。
まず、操作する数が偶数であっても奇数であっても、まず$2$で整数除算をしていることがわかります。この操作によって最上位のbitは必ず$0$になります。
その後、操作する数が偶数の時のみ$2^{N-1}$を足しています。ここで、操作する数は必ず$2$進数で$N$桁であることを考えると、$2^{N-1}$を足すことによって最上位のbitが$1$になることがわかります。これによって、この言い換えが成り立つことが示せました。
次に、この操作を$2$進数で$N$桁の数に対して行った場合、操作回数は何回になるかを考えてみます。
まず次のことが成り立つことがわかります。
$f^N(A)=A$の全bitが反転した数となる (ただし、$f^m$は$f$を$m$回適用することを指します。)
これは、$f^m(m≦N)$を次のように言い換えることでわかります。
- $2$進数で$0$桁の整数$B$を持つ。適用する整数の最下位のbitを反転させて$B$の先頭に置く。また、適用する整数の最下位のbitは削除される。最終的に残った整数の先頭に$B$を結合させて操作結果とする。
この操作を$m=N$で行った時、$B$が操作する整数の全bitを反転させた整数になるため、これが示せます。
また、そのため$2N$回操作をした場合、必ず元に戻ることがわかります。
ただし、すべての$2$進数で$N$桁の整数に対して最小回数が$2N$回になるわけではありません。たとえば、$f^2(010)=010$となります。
ここで、$A$が$2$進数で$m$桁の整数であり、($A'$を$A$の全bitが反転した数としたとき)操作する整数が$A A' A ... A A' A$のようになるとき、操作回数は$2m$回(以下)であることがわかります。これは、操作を$N$回行うことで全bitが反転することを示したときに使った言い換えをもう一度使うことで示すことができます。
まず、$A' A$の全bitを反転させた数は$A A'$です。ここで、その言い換えでの$B$が$A A'$になるまで操作したとき、残っている整数の$2$進数表記は操作する整数の$2$進数表記の下$N-2m$桁と一致することがわかります。また、そのとき$B$は操作する整数の上$2m$桁と一致することもわかります。そのため、これが示せました。
また、操作する整数を$A A' A ... A A' A$のように分割するためには、$m$が$N$を$3$以上の奇数で割った商になる必要があることがわかります。そのため、$N$の$N$でない奇数の約数を$m$としてすべて試し、それぞれの$m$に対して
・操作を$2m$回して初めて元に戻る数の個数$×2(N-m)$
を計算し、それらすべての和を$2N(X+1)$から引いて答えを($mod\ 998244353$で)求めればよいです。
これを求めるには、次のような方法を使えばよいです。
・まず、$N$のすべての約数$m$について$2m$回の操作で初めて元に戻るような数の個数を記録するための配列などを持っておく。
・$N$の小さい約数$m$から順に、「「$N/m$が$3$以上かつ奇数かどうか(そうであるなら$1$、そうでないなら$0$)」$×$(「$X$の上$m$桁を$2$進数として見た時の数(これは、Xよりも小さいことが上$m$桁を見るだけでわかるような$2m$回の操作で元に戻る数の個数です)」$+$「$X$と上$m$桁が等しいような$2m$回の操作で元に戻る数が$X$以下であるかどうか(そうであるなら$1$、そうでないなら$0$)(これは実際にそのような数を(文字列として)構成することでわかります)」$-$「$m$の$m$でないすべての約数$l$(これは$N$の$m$未満の約数すべてに対してそれが$m$を割り切るかを判定したほうがよいと思われます)に対して操作を$2l$回して初めて元に戻る数の個数の和」)」を記録する。
これで、すべての$N$でない$N$の約数$m$に対して操作を$2m$回して初めて元に戻る数の個数が求まるので、答えが求まります。
感想
考察するのがとても面白い問題でした。ただ、$100101101001$なども操作回数が$2N$回未満であることに気がつかずとても時間を使ってしまったことが反省点です。
初めて書き切ることができた解説ブログです。
(追記:ミスがありました。すみませんでした。(追記:$mod$を間違えていました。申し訳ありません。))
ここまで読んでいただき、ありがとうございました。