22杭电多校11 Find different（环计数问题）

题意：给定一个环，环大小为n，环上每个数取值范围为[0,m-1]，能通过旋转或者模m意义下整体加任意数得到的环视为同构体，求所以不同的方案数。

Solution:
\quad 本题有两个同构体条件。先看模意义下加法，可以转化为差分数组。
\quad 设环上的数为ai，设$b_i=a_i-a_{(i-1+mod)modm}$。因为整体是个环，所以有$\sum b_i=0$(模m意义下)。只考虑模意义下加法同构的话，也就是差分数组要不同的方案数为$m^{n-1}$（前n-1个bi任意取）
\quad 现在加上旋转同构体考虑，通过上面的分析，我们现在只要关注差分数组bi旋转同构即可。
\quad 我们用传统的环计数方法来推导（菜鸡博主不会用polyaQAQ）。考虑环的循环节，设$f(i)$表示环上最小循环节为i的方案数（含旋转同构，也就是说旋转同构会算重）,$g(i)$表示存在环循环节为i的方案数（含旋转同构）。比如说123123在g(6)中算，f(6)中不算,f(3)算。
\quad 设循环节长度为d，则有$\frac{n}{d}$个循环节。设一节的bi数组和为$s(modm)$,有$s={\sum }_{i=1}^d{b}_i$。因为$\sum b_i=0(modm)$，则有$m\mid s\ast \frac{n}{d}$，其中s的范围为[0,m-1]等价于[1,m]（模m意义下）。假如符合上述约束的s有k个,则$g(d)=m^{d-1}\ast k$。
$k={\sum }_{i=1}^m[m\mid i\ast \frac{n}{d}]$，提出$gcd(m,\frac{n}{d})，设p=\frac{m}{gcd(m,\frac{n}{d})},设q=\frac{\frac{n}{d}}{gcd(m,\frac{n}{d})}$，显然pq互质。
$k={\sum }_{i=1}^m[p\mid iq]=\frac{m}{p}=gcd(m,\frac{n}{d})$
\quad 则$g(d)=m^{d-1}\ast gcd(m,\frac{n}{d})$。而$g(d)={\sum }_{d^{\prime }\mid d}f(d^{\prime })$，由莫比乌斯反演有$f(d)={\sum }_{d^{\prime }\mid d}\mu (\frac{d}{d^{\prime }})g(d^{\prime })$。
\quad 则$$\begin{gathered} ans(n)={\sum }_{d\mid n}\frac{f(d)}{d}，去掉旋转同构 \\ ={\sum }_{d\mid n}\frac{1}{d}{\sum }_{d^{\prime }\mid d}\mu (\frac{d}{d^{\prime }})g(d^{\prime }) \\ ={\sum }_{d\mid n}\frac{1}{d}{\sum }_{d^{\prime }\mid d}\mu (\frac{d}{d^{\prime }})m^{d^{\prime }-1}\ast gcd(m,\frac{n}{d^{\prime }}) \end{gathered}$$，交换枚举顺序
$={\sum }_{d|n}{m}^{d-1}\ast gcd(m,\frac{n}{d}){\sum }_{d\mid t}\frac{1}{t}\mu \frac{t}{d}$，发现t没用，转成枚举d的k倍数
$$\begin{gathered} ={\sum }_{d|n}{m}^{d-1}\ast gcd(m,\frac{n}{d}){\sum }_{k\mid \frac{n}{d}}\frac{1}{kd}\mu (k) \\ ={\sum }_{d|n}{m}^{d-1}\ast gcd(m,\frac{n}{d})\ast \frac{1}{d}{\sum }_{k\mid \frac{n}{d}}\frac{\mu (k)}{k} \end{gathered}$$
后面的$\frac{\mu (k)}{k}$的狄利克雷前缀和可以O(nlogn)预处理出来，这样对于每个ans(n)只要枚举d，总复杂度O(nlogn)

const int N=1e5+5;
const int mod=998244353;
const double eps=1e-8;
int n,m;
int ans[N];
int v[N],p[N],cnt,ni[N];
int mu[N],eu[N],S_mu[N];
std::vector<int> factor[N];
ll qsm(int a,int b){
    ll ans=1,tmp=a;
    while( b ){
        if( b&1 ) ans = (ans * tmp)%mod;
        tmp = tmp * tmp%mod;
        b>>=1;
    }
    return ans;
}
void shai(int n){
_for(i,2,n){
    v[1]=1;
    eu[1]=1;
    mu[1]=1;
    if (!v[i]) {
        p[++cnt] = i;
        mu[i] = -1;
        eu[i] = i - 1;
        v[i]=i;
    }
    _for(j, 1, cnt){
        if (i * p[j] > n)break;
        v[i * p[j]] = p[j];
        if (i % p[j] == 0){
            mu[i*p[j]] = 0;//存在平方因子
            eu[i * p[j]] = eu[i] * p[j];
            break;
        }
        mu[i * p[j]] = -mu[i];
        eu[i * p[j]] = eu[i] * (p[j] - 1);
        }
    }
}
void ini(int n){
    _for(i,1,n) {
        for(int j=i ;j<=n  ;j+=i){
            factor[j].push_back(i);
            S_mu[j]  = (S_mu[j] + mod + mu[i]*ni[i]%mod)%mod;
        }
    }
}
void get_ni(int n){
    ni[0] = ni[1]=1;//0和1逆元
    _for(i,2,n){
        ni[i] = ((mod-mod/i)*ni[mod%i])%mod;
    }
    return;
}
void solve(){
    cin>>n>>m;
    _for(i,1,n){
        for(int j:factor[i]){
            ans[i] = (ans[i] + mod + qsm(m,j-1)*__gcd(m,i/j)%mod*ni[j]%mod*S_mu[i/j]%mod)%mod;
        }
    }
    _for(i,1,n) {
        cout<<ans[i]<<" \n"[i==n];
        ans[i]=0;
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif  
    IOS;
    get_ni(1e5);
    shai(1e5);
    ini(1e5);
    int T;cin>>T;
    while( T-- ) solve();
    AC; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80