发现之前写过这题题解，今天突然记起这道题就发出来一下。
其实基本上是复读一遍 EI 题解（
题意
一个长度为 \(n\) 的环上等距排列 \(n\) 个点，任意两点之间均有一条无向边。每个点可以染一个 \([1,a]\) 内的整数颜色，每条边可以染一个 \([1,b]\) 内的整数颜色。
定义一个环是好的当且仅当其任意旋转一个角度或任意选择一条直线翻转得到的图案与原来不同构。
计数好环的数量。
\(n\leqslant 10^{18}\)。
分析
本题理论速通步骤：建立群论模型，缩减置换群数量，列出转移式，计算贡献。
可以发现有效的旋转、翻转数量是很少的，一个粗略的上界是 \(2n-1\) 种，即 \(x\mapsto(c-x)\bmod n\) 或 \(x\mapsto(x+c)\bmod n\)。
直接容斥，钦定一个操作集合表示在这些操作下图案不变，可以得到一个指数级的做法。
使用群论的语言表达，也就是给定一个置换群 \(G\)，求其作用于一个染色后的对象，有多少个染色方案的稳定子仅包含单位元，于是可以直接 dp，令 \(X(H)\) 为稳定子恰好为 \(G\) 的子群 \(H\) 的方案数：
\[X(H)=a^{O(H,V)}b^{O(H,E)}-\sum_{H<K\leqslant G}X(K) \]（\(O(H,V)\) 表示 \(H\) 在顶点 \(V\) 上的轨道数量，\(O(H,E)\) 同理，下文记 \(W(H)=a^{O(H,V)}b^{O(H,E)}\)）
记单位旋转操作为 \(r\)，以 \(1\) 号点为对称轴翻转操作为 \(s\)，那么任意操作都可以用 \(s,r\) 表示，且 \(rs=sr^{-1}\)，那么所有操作都可以写成 \(r^k\) 或 \(sr^k\) 的形式。
分析一下，如果一个置换群不包含翻转操作，那么其一定包含一个 \(r^d(d\mid n)\)，这样的置换群只有 \(d(n)\) 个。
如果其包含翻转操作，若其包含两种翻转 \(sr^a,sr^b\)，那么其包含 \(r^{b-a}\)，也一定包含 \(r^d(d\mid n)\)，那么这样的置换群有 \(\sum_{d\mid n}d=O(n\log \log n)\) 个，仔细分析一下，第二类群的数量只与其 \(d\)，以及是否存在 \(sr^t(2\not\mid t)\) 有关，于是只有 \(2d(n)\) 个。（可以发现，此时 \(W(H)\) 有了很大的简化，可以做到单 \(\log\) 计算）
于是直接列出 dp：（\(\mathrm{Rot}(d)\) 表示第一类群的数量，\(\mathrm{Refl_{0/1}(d)}\) 同理，多记一个 \(0/1\) 表示是否有奇数）
\[\mathrm{Rot}(d)=W(\{r^d\})-\sum_{d\mid k\mid n,d<k}\mathrm{Rot}(k)-\sum_{d\mid k\mid n}\frac{n}{2k}(\mathrm{Refl}_0(k)+\mathrm{Refl}_1(k))\\ \mathrm{Refl}_i(d)=W(\{r^d,sr^i\})-\sum_{d\mid k\mid n,d<k}\mathrm{Refl}_i(k) \]我们考虑每个 \(W(H)\) 对答案产生的贡献系数，若其出现在 \(\mathrm{Rot}(d)\) 中，其贡献系数 \(f(d)=1-\sum_{k\mid d,k<d}f(k)\)，这是经典的莫比乌斯函数，\(\mathrm{Refl}_i(d)\) 贡献系数同理。
于是答案为：
\[\mathrm{Rot}(1)=\sum_{d\mid n}\mu(d)(W(\{r^d\})-\sum_{d\mid k\mid n}\frac{n}{2k}(\mathrm{Refl}_0(k)+\mathrm{Refl}_1(k)))\\ \mathrm{Refl}_i(d)=\sum_{d\mid k\mid n}\mu(\frac kd)W(\{r^k,sr^i\}) \]根据经典结论 \(\sum_{abc=n}\frac{\mu(a)\mu(c)}{ab}=\mu(n)\)（证明只需两边同乘 \(n\)），展开上面的式子可得：
\[\mathrm{Rot}(1)=\sum_{d\mid n}\mu(d)(W(\{r^d\})-\frac{n}{2}(W(\{r^d,sr^0\})+W(\{r^d,sr^1\}))) \]莫比乌斯函数非零的因子只有 \(2^{\omega(n)}\) 个，复杂度 \(O(2^{\omega(n)}\log n)\)。
代码
#include<stdio.h>
#include<map>
using namespace std;
const int mod=998244353,maxn=25,maxs=1<<15,phi=mod-1,inv2=(mod+1)/2;
int k,a,b,srfl,srt;
long long n;
long long p[maxn],mul[maxs];
map<long long,int>mp;
int ksm(int a,long long b){
b=(b%phi+phi)%phi;
int res=1;
while(b){
if(b&1)
res=1ll*res*a%mod;
a=1ll*a*a%mod,b>>=1;
}
return res;
}
long long gcd(long long a,long long b){
return b==0? a:gcd(b,a%b);
}
int Rot(long long d){
long long orbv=d,orbe=(n-1)/2%phi*(d%phi)%phi;
if(n%2==0)
orbe=(orbe+gcd(d,n/2))%phi;
return 1ll*ksm(a,orbv)*ksm(b,orbe)%mod;
}
int Refl(long long d,int o){
long long orbv=d/2+(o|(d&1)),orbe=(n-1)/2%phi*((d+1)/2%phi)%phi;
if(d%2==0)
orbe+=(n/2-(o|(d&1)))/2;
if(n%2==0){
long long g=gcd(d,n/2);
orbe+=g/2+(o|(g&1));
}
return 1ll*ksm(a,orbv)*ksm(b,orbe)%mod;
}
int main(){
scanf("%d",&k),n=1;
for(int i=1,x;i<=k;i++)
scanf("%d",&x),mp[x]=1,n*=x;
scanf("%d%d",&a,&b),k=0;
for(map<long long,int>::iterator it=mp.begin();it!=mp.end();it++)
p[++k]=it->first;
mul[0]=n;
for(int i=0;i<(1<<k);i++){
if(i>0){
int l=(i&-i);
mul[i]=mul[i^l]/p[__builtin_ctz(l)+1];
}
int coef=__builtin_parity(i)? (mod-1):1;
long long d=mul[i];
srt=(srt+1ll*coef*Rot(d))%mod;
srfl=(srfl+1ll*coef*(Refl(d,0)+Refl(d,1)))%mod;
}
printf("%d\n",(srt+1ll*(mod-n%mod)*inv2%mod*srfl)%mod);
return 0;
}