题意简化
给一个有N个珠子的环染色,颜色一共有M种,旋转或翻转后能够完全重合在一起而且对应位置颜色一致为一种情况,问方案数?
算法一—Pólya定理
解题思路
先考虑有多少不同的置换,分为两类:旋转与翻转
- 旋转置换
一共n个置换,第i个置换的循环节的个数为gcd(n, i)。
故此:$$\sum_{k=0}^{m}m^{(n,k)}$$
证明:
有了循环节,接下来只要将循环节数c作为幂求m^c就是不动点数量。- 翻转置换
n为奇数:$$ n\times m^{\frac{n+1}{2}} $$
n为偶数:$$ \frac{(n\times m^{\frac{n}{2}+1} +n\times m^{\frac{n}{2}})}{n/2} $$
代码
/*
题意简化:给一个有N个珠子的环染色,颜色一共有M种,
旋转或翻转后能够完全重合在一起而且对应位置颜色一致为一种情况,问方案数?
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int f(int a,int b){
int res=1,t=a;
while(b){
if(b&1)res=res*t;
t=t*t;
b>>=1;
}
return res;
}
int main(){
int m,n;
while(cin>>m>>n,m||n){
ll res=0;
for(int i=0;i<n;i++)res+=f(m,gcd(n,i)); //旋转
if(n%2)res+=n*f(m,(n+1)/2); //翻转
else res+=n/2*(f(m,n/2+1)+f(m,n/2));
cout<<res/n/2<<endl;
}
}
式子的锅是不是有点多了,旋转的那个上界是n-1,翻转的那个分母是2不是n/2
博主 想请问一下这里不定方程的最小解为什么就直接等于n/d了啊?
巨巨,其实上面的证明可以看一下,或者就按着y总讲的,我们可以画一个串珠子看他有多少个不动点,然后去找循环节的个数得到这个不定方程,有着一个定理
方程a*x+b*y=c有解,当且仅当 c%gcd(a,b)=0
,故根据这个不定方程的算式在计算时可以得到最小值t=n/d*c
!嗯嗯 了解了 感谢巨佬!