P4270

· · 个人记录

（以下下标都是 \bmod n 剩余系内的）

还是考虑同一高度是内部贡献的，所以第 i 层下面总是有第 i-1 层的跟它一起移动，同时有相邻同一高度的块一定等距离（否则贡献不均匀），设第 i 层每移动 s_i 个块再次合法（则一定有 s_i \mid n），则 s_{i-1} \mid s_i，但是只有这个还是没什么用。

由于高度不变，不妨把所有高度全部减去最小值 m，那么至少有一个块此时是空的，并且有剩余的块不需要给自己留下一个（减去的最小值里包含这部分）。考虑此时的一个高度为 2 的块（即原本 h = m + 2 的块），则要使它操作后不变，必然有 h_{i-m} \ge 1 且 h_{i-m-1} \ge 2，那么再考虑 i-m-1 又有 h_{i-2m-1} \ge 1，以此类推可以得到环上每个块 h \ge 1，这与至少有一个块是空的矛盾，所以每个块的高度只可能是 m 或 m + 1。

（对于 h_i = m + 1，只有一条限制为 h_{i-m} \ge 1，而重复继续考虑 i-m 的过程可能只是形成一个子环内部 \ge 1 的限制，没有影响整个环）

然后又有 s_{m} \mid n，考虑上述限制又有 s_m \mid m（i \to i-m），于是 s_m 可能的取值有 \gcd (m,n) 种。

那么考虑把必然为 h = m 的点先标出来，有 n / \gcd (m,n) 个，每两个中间距离为 \gcd (m,n)（前闭后开），于是你只需要枚举其中一段的状态，所有段会自行改变适应，所以方案数有 2^{\gcd (m,n)} - 1（不能全部为 m+1）种。

求和就是

1 + \sum_{m=1}^{n-1} (2^{\gcd (n,m)} - 1) = 2-n-2^n + \sum_{m=1}^{n} 2^{(m,n)} = 2-n-2^n + \sum_{d \mid n} 2^{d} \sum_{m=1}^{n} [(m,n) = d] = 2-n-2^n + \sum_{d \mid n} 2^d \sum_{m=1}^{n/d} [(m,n/d) = 1] = 2-n-2^n + \sum_{d \mid n} 2^d \sum_{m=1}^{n/d} \sum_{t \mid m, t \mid n/d} \mu(t) = 2-n-2^n + \sum_{d \mid n} 2^d \sum_{t \mid n/d} \mu(t) \dfrac{n}{dt}

后面那坨是 \mu * \text{id} = \varphi？

然后就变成了

\large{ 2-n-2^n + \sum_{d \mid n} 2^d \varphi(\dfrac{n}{d}) }

这个要求 d(n) 个 \varphi，也就是 10^6 个（，那感觉有点【】。是不是把杜教筛板子粘过来就过了。（？？？）

可以把枚举 d 换成 dfs 枚举质因子，于是 \varphi 可以在路上求出来（，然后就无了应该。

复杂度是 O(\sqrt{n} \log p)，跑得飞快。 

    auto dfs = [](auto U,int u,ll d,ll phi)->int {
        if(u == D.size()) return Pow(2,d)*phi%p;
        auto t = D[u]; int res = 0;
        ll di = t.first, pw = t.second;
        for(int i=0;i<=pw;++i){
            P(res,U(U,u+1,d,phi));
            if(i == pw) break; d *= di;
            if(i == pw-1) phi /= (di-1); else phi /= di;
        } return res;
    };

质数处 res = n，已舍去。 

for 4 res 6 :
1 1 1 1
2 2 2 2
2 3 2 3
3 2 3 2
3 3 3 3
4 4 4 4
for 6 res 16 :
1 1 1 1 1 1
2 2 2 2 2 2
2 3 2 3 2 3
3 2 3 2 3 2
3 3 3 3 3 3
3 3 4 3 3 4
3 4 3 3 4 3
3 4 4 3 4 4
4 3 3 4 3 3
4 3 4 4 3 4
4 4 3 4 4 3
4 4 4 4 4 4
4 5 4 5 4 5
5 4 5 4 5 4
5 5 5 5 5 5
6 6 6 6 6 6
for 8 res 26 :
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
2 3 2 3 2 3 2 3
3 2 3 2 3 2 3 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
4 4 4 5 4 4 4 5
4 4 5 4 4 4 5 4
4 4 5 5 4 4 5 5
4 5 4 4 4 5 4 4
4 5 4 5 4 5 4 5
4 5 5 4 4 5 5 4
4 5 5 5 4 5 5 5
5 4 4 4 5 4 4 4
5 4 4 5 5 4 4 5
5 4 5 4 5 4 5 4
5 4 5 5 5 4 5 5
5 5 4 4 5 5 4 4
5 5 4 5 5 5 4 5
5 5 5 4 5 5 5 4
5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6
6 7 6 7 6 7 6 7
7 6 7 6 7 6 7 6
7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8
for 9 res 21 :
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
3 3 4 3 3 4 3 3 4
3 4 3 3 4 3 3 4 3
3 4 4 3 4 4 3 4 4
4 3 3 4 3 3 4 3 3
4 3 4 4 3 4 4 3 4
4 4 3 4 4 3 4 4 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6
6 6 7 6 6 7 6 6 7
6 7 6 6 7 6 6 7 6
6 7 7 6 7 7 6 7 7
7 6 6 7 6 6 7 6 6
7 6 7 7 6 7 7 6 7
7 7 6 7 7 6 7 7 6
7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9