题意:用三种颜色给长度为n(n < 24)的环状手镯涂色，若能通过旋转或翻转得到则表示为同一种，问不同种涂色方案为多少？
思路:纯粹的等价类计算问题；
重点:对旋转和翻转转化为置换操作；
旋转:对间隔的长度进行枚举，即0 <= i < n；这样循环节就为n/gcd(i,n);直接弄成3的幂次方求和即可；
翻转:分奇偶，再求出对称轴的个数和每种情况下循环节的个数即可；
上面求出的a+b只是不动点的个数总和，最后要除以总的置换的个数即2n;
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } ll f[30],ans[30]; template<typename T> int gcd(T a,T b){return b?gcd(b,a%b):a;} int main() { f[0] = 1; rep1(i,1,24) f[i] = f[i-1]*3; rep1(i,1,24){ ll a = 0,b = 0; rep0(j,0,i) a += f[gcd(i,j)]; if(i & 1) b = i*f[(i+1)/2]; else{ b = i/2*(f[i/2] + f[(i+2)/2]); } ans[i] = (a + b)/2/i; } int m; while(read1(m),m >= 0){ out(ans[m]);puts(""); } return 0; }
同类型的题:手镯操作一样，只是输入时先是颜色数后是珠子数；
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } ll f[40]; template<typename T> int gcd(T a,T b){return b?gcd(b,a%b):a;} int main() { int s,c; while(read2(c,s), s + c){ f[0] = 1; rep1(i,1,s) f[i] = f[i-1]*c; ll a = 0,b = 0; rep0(j,0,s) a += f[gcd(s,j)]; if(s & 1) b = s*f[(s+1)/2]; else b = s/2*(f[s/2] + f[(s+2)/2]); out((a + b)/2/s); puts(""); } return 0; }