UVA 10294 Arif in Dhaka

https://vjudge.net/problem/UVA-10294

题目

某人看到商店里面有项链和手镯,是由一圈珠子构成的。有k种颜色的珠子,每种珠子随便用,问n个珠子能制作成多少种不同的项链和手镯。

项链或手镯可以旋转,如果旋转后能够重合的两个项链或者手镯看作一种项链或手镯。

手镯除了可以旋转以外还可以翻转。如果翻转后能够重合的两个手镯看作一种手镯。

输入n,k,0<n<51,0<t<11

输出项链和手镯的种数,保证答案不超过11位数。

题解

用Burnside引理 https://oi-wiki.org/math/permutation-group/

$\left\lvert X/G\right\rvert = \frac{1}{\left\lvert G\right\rvert} \sum_{g\in G} \left\lvert X^g\right\rvert$

$ X^g=\{x|x\in X,g(x)=x\} $

那么对于项链,有旋转0次、旋转1次、旋转2次……旋转n-1次,如果要求旋转后不变(整个项链看成一个元素,旋转看成置换),那么旋转i次就要求第0,i,2i,3i……个珠子颜色相同,可以得到有$lcm(n,i)/i=n/gcd(n,i)$个珠子颜色相同,这就把项链分成了$gcd(n,i)$份,每一份有t种涂色方式,因此得到项链种数为

\[\frac{1}{n}\sum_{i=0}^{n-1} {t^{gcd(n,i)}}\]

剩下的还是直接套公式就可以了……

#include<cstdio>
using namespace std;
typedef long long ll;
int gcd(int a, int b) {
	return b==0? a:gcd(b,a%b);
}
ll qpow(unsigned long long a, int b) {
	ll ans=1;
	for(;b;b>>=1) {
		if(b&1) ans*=a;
		a*=a;
	}
	return ans;
}
int main() {
	int n,t;
	while(~scanf("%d%d", &n, &t)) {
		ll ans=0;
		for(int i=0; i<n; i++) {
			ans += qpow(t, gcd(n,i));
		}
		printf("%lld ", ans/n);
		if(n&1) {
			ans+=n*qpow(t,(n+1)/2);
			printf("%lld\n", ans/2/n);
		} else {
			ans+=n/2*(qpow(t,(n+2)/2)+qpow(t,n/2));
			printf("%lld\n", ans/2/n);
		}
	}
}

 

上一篇:ACM Contest and Blackout UVA - 10600


下一篇:例题7-6(uva-140)