正题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=7207
题目大意
一个序列\(a\)，和它相同的序列当且仅当能通过以下操作实现相同：
- 将\(a_1\)丢到\(a_n\)，其余的向前移动一位。
- 令所有\(a_i=(a_i+1)\%m\)
对于\(n\in [1,N]\)，求有多少个不同的序列。
\(1\leq T\leq 100,1\leq N,m\leq 10^5,\sum N\leq 10^6\)
解题思路
根据\(\text{burnside}\)引理，我们要找所有置换的不动点数量和。
置换总共有\(n\times m\)种，假设一种为循环位移了\(x\)步，且所有数字加上了\(y\)。
那么我们有\(a_i\equiv a_{(i+x)\%n}+y\pmod m\)，从一个数开始一直加\(x\)模\(n\)，我们知道会产生\(\gcd(n,x)\)个环，对于每个环来说总共加了\(\frac{n}{\gcd(n,x)}\)次\(y\)，最终又走回了起点。
也就是对于这个\(y\)来说合法的条件当且仅当\(y\times \frac{n}{\gcd(n,x)}\equiv 1\pmod m\)，不难得到合法的\(y\)的数量就是\(\gcd(m,\frac{n}{\gcd(n,x)})\)。
所以答案就是
\[\frac{1}{nm}\sum_{i=0}^{n-1}\gcd(m,\frac{n}{\gcd(n,x)})^{\gcd(n,i)} \]\[\frac{1}{nm}\sum_{d|n}^n\varphi(\frac{n}{d})\gcd(m,\frac{n}{d})^{d} \]时间复杂度：\(O(n\log n)\)
code
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10,P=998244353;
ll T,n,m,cnt,pri[N],phi[N],ans[N];
bool v[N];
ll power(ll x,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*x%P;
x=x*x%P;b>>=1;
}
return ans;
}
ll gcd(ll x,ll y)
{return y?gcd(y,x%y):x;}
void Prime(){
phi[1]=1;
for(ll i=2;i<N;i++){
if(!v[i])phi[i]=i-1,pri[++cnt]=i;
for(ll j=1;j<=cnt&&i*pri[j]<N;j++){
v[i*pri[j]]=1;
if(i%pri[j]==0){
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
return;
}
signed main()
{
Prime();
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&m);
ll now=1,z=1;
for(ll i=1;i<=n;i++){
z=z*m%P;
for(ll j=i;j<=n;j+=i)
(ans[j]+=z*phi[j/i]%P*gcd(m,j/i)%P)%=P;
}
ll inv=power(m,P-2)%P;
for(ll i=1;i<=n;i++){
ans[i]=ans[i]*power(i,P-2)%P*inv%P;
printf("%lld%c",ans[i],(i==n)?'\n':' ');
ans[i]=0;
}
}
return 0;
}