移調の限られた旋法 [yukicoder 890]

https://yukicoder.me/problems/no/890

前提知識

• 10⁹+7mod上での二項係数
• 約数系包除原理

解説

https://yukicoder.me/submissions/382005

回転対称性について考える。
まず、beetさんが質問していたので見てみる。

回転対称性を持つとはある整数i(0<i<n)が存在して、任意の整数jに対して、  
j(mod N)番目の点が選ばれているかとj+i(mod N)番目の点が選ばれているかが  
同じであることです  

なるほど。
つまり、回転したときに同じになる場合は最初以外のどこかであればいいことになる。

こういう回転して、同じになるというのは周期性を用いる問題が多い。
円で考えず、列として考えたときに、同じパターンが連続する、つまり、周期性を持てば、回転すれば同じパターンになる場合が存在する。
そして、最小周期で全探索して数え上げしていく問題はいくつも見たことがある。
例えば、N=8であれば、最小周期が1,2,4である場合を考えればいい。

今回は選べる点の数がK個となっているが、最小周期をminloopとすると、グループはN/minloop個できる。
よって、KがN/minloopで割り切れる必要がある。そうでないと周期を作れない。
あとは、各周期について、最小周期がminloopとなるような列を構成すればいい。
これは、C(minloop, K/(N / minloop))をすればいい。
繰り返されるパターンを作るものである。

だが、これだけでは不十分で、こうして作られたパターンは周期がminloopであることは保証されるが、
最小周期がminloopでない可能性がある。
minloopの約数の周期になっている場合がある。
よって、この場合を引こう。
これは、約数系包除原理というテクである。
minloopの小さい方から計算をしていき、cnt[x] := 最小周期がxである組み合わせ
これを使って、ダブっているパターンを引いていく。

int N, K;
mint cnt[1010101];
Comb<mint, 2010101> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    auto ed = enumdiv(N);
    fore(minloop, ed) if (minloop < N and K % (N / minloop) == 0)
    {
        cnt[minloop] = com.aCb(minloop, K / (N / minloop));
        fore(x, ed) if (x < minloop and minloop % x == 0) cnt[minloop] -= cnt[x];
    }

    mint ans = 0;
    fore(minloop, ed) ans += cnt[minloop];
    cout << ans << endl;
}