理论部分太长惹。。晚点填

1、模板:

poj2154 Color

给正$n$边形染$m$种颜色，问有多少种染色方案。

对任意正$n$边形有如下$2n$阶二面体群： $G = \{\rho^0,..,\rho^{n-1},\tau^1,\ldots,\tau^n\}$ 然后通过$\text{Burnside定理}$:$$N(G,\mathcal{C})=\frac 1{|G|}\sum_{f\in G}|\mathcal{C}(f)|$$求解

对于旋转产生的置换$\rho^i$产生的贡献$|\mathcal{C}(\rho^i)|$，奇偶都一样，要通过$gcd$来找循环节个数:$|\mathcal{C}(\rho^i)|=m^{gcd(n,i)}$

对反射产生的置换要分奇偶讨论 $$ \begin{cases} & \sum |\mathcal{C}(\tau^i)| & = & n\times m^{n/2+1} & (n\%2==1) \\ & \sum |\mathcal{C}(\tau^i)| & = & \frac n2\times m^{n/2}+\frac n2\times m^{n/2+1} & (n\%2==0) \\ \end{cases} $$ 最后的答案即$\frac {1}{2n} \sum |\mathcal{C}(f)|$

while(cin>>m>>n && n+m){
    ans = 0;
    rep(i,0,n-1){
        ans += (ll)pow(m,gcd(n,i)); // 旋转
    }
    if(n&1) ans += n*(ll)pow(m,n/2+1);  // 反射
    else ans += (ll)pow(m,n/2)*n/2 + (ll)pow(m,n/2+1)*n/2;
    ans /= 2*n;
    cout<<ans<<endl;
}

poj2409 Let it Bead

$n$种颜色染正$n$边形，忽略关于旋转带来的重复（即只算旋转的置换）

注意：$n$很大($1e9$)

由于去掉反射类型的置换那么答案就是

$$ans=\frac 1{|G|} \sum \mathcal{C}(\rho^i)=\frac 1n \sum _{i=1}^n n^{gcd(n,i)}$$ 如果直接用上面的公式显然会$t$

考虑如何化简上式，因为$gcd(n,i)=k$的$i$肯定有很多，所以可以枚举$n$的因数，这样复杂的就降到了$O(\sqrt n)$ $$ \begin{aligned} \sum_{i=1}^n n^{gcd(n,i)} &=\sum_{d|n}n^d\sum _{i=1}^n[gcd(n,i)==d]\\ &=\sum_{d|n}n^d\sum_{i=1}^n[gcd(\frac nd,i)==1]\\ &=\sum_{d|n}n^d\phi(\frac nd) \end{aligned} $$

其中$\phi (k)$表示$k$的欧拉函数

那么我们可以预处理出前$\sqrt n$个质数，并用远小于$O(\sqrt n)$的复杂度求出每个数的欧拉函数$\phi(k)$

for(i=1;i*i<n;i++){
    if(n%i==0) ans = (ans+1LL*qpow(n,i-1)*getPhi(n/i)%M+1LL*qpow(n,n/i-1)*getPhi(i)%M)%M;
}
if(i*i==n) ans = (ans+1LL*qpow(n,i-1)*getPhi(i)%M)%M;

2、poj2888 Magic Bracelet

$m$种颜色染正$n$边形，但有限制条件颜色$u$和$v$不能相邻出现

注意：$m<10$

对于颜色是否能同时出现的问题，考虑用一个关于颜色的邻接矩阵$G$来表示两个颜色之间的关系: $$G[u][v]=G[v][u]=0\; \leftrightarrow \; u和v不能同时出现$$ 接着更泛化地表示每个旋转置换$\rho^i$的对非等价着色数的贡献$\mathcal{C}(\rho^i)$

首先$\rho^i$会产生$gcd(n,i)$个长度为$\frac n{gcd(n,i)}$循环节，然后枚举每个循环节的颜色就得到了$\mathcal{C}(\rho^i)$，例如没有任何限制时每个循环节都可以取$m$种颜色，所以$\mathcal{C}(\rho^i)=m^{gcd(n,i)}$

对于有上述限制的，可以这么做，构造出邻接矩阵后，有

$$\mathcal{C}(\rho^i)=\sum_i\sum_j G^{gcd(n,i)-1}[i][j]\times [G[i][j]==1]$$

在离散数学的图论中曾提到$$G^k[i][j]\; :=\; i出发，经过k条边到达j的路径数$$

在这里就是$$G^k[i][j]\; :=\; 第1个循环节的颜色是i，第k+1个循环节节的颜色是j的染色数$$

因为最后一个循环节会和第一个循环节的下一个元素再次相邻，所以只对$G[i][j]==1$的$G^{gcd(n,i)-1}[i][j]$算贡献

然后我们会发现这实际上就是 $$\mathcal{C}(\rho^i)=\sum_i\sum_j G^{gcd(n,i)-1}[i][j]\times [G[i][j]==1]=\sum_iG^{gcd(n,i)}[i][i]$$

即第一个循环节颜色是$i$经过$gcd(n,i)+1$条合法路径又回到自身的数量

所以只要用矩阵快速幂优化一下就可以了