题目传送门:http://poj.org/problem?id=1286
polya的板题,其中置换的循环节先用一下程序算,之后再写程序
#include<iostream> #include<cstdio> using namespace std; const int MAXN = 100; int to[MAXN],tag[MAXN],ty,delta,n; inline int Get_M(){ int ret = 0; for (int i=1,w;i<=n;i++) if (!tag[i]) { ret++; w = i; while (!tag[w]) tag[w] = 1, w = to[w]; } return ret; } int main(){ cin>>n>>delta>>ty; if (ty == 1) { for (int i=1;i<=n;i++) to[i] = i + delta; for (int i=1;i<=n;i++) if (to[i] > n) to[i] -= n; } else { for (int j=1,i=delta;j<=n;j++,i=++i>n?i-n:i) to[i] = n - i; } cout<<Get_M(); return 0; }
主程序:
#include<iostream> #include<cstdio> #define LL long long using namespace std; const int col = 3; inline LL pow(int w, int t) { LL ret = 1; while (t) { if (t & 1) ret *= w; t >>= 1, w *= w; } return ret; } int GCD(int a, int b){return b?GCD(b,a%b):a;} inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ for (int n=read();~n;n=read()) { if (n == 0) {cout<<0<<endl; continue;} else { LL vout = 0; int t = n; for (int i=1;i<=n;i++) vout += pow(col,GCD(i,n)); if (n & 1) {for (int i=1;i<=n;i++) vout += pow(col,n/2+1); t += n;} else { for (int i=1;i*2<=n;i++) vout += pow(col,n/2+1); t += n/2; for (int i=1;i*2<=n;i++) vout += pow(col,n/2); t += n/2; } vout /= t; printf("%lld\n",vout); } } return 0; }
This is a topic close to my heart cheers, where are your contact details though?
It’s hard to find knowledgeable people on this topic, but you sound like you know what you’re talking about! Thanks