这题的主要就是找循环节数，这里用找字符串最小覆盖来实现，也就是n-next[n],证明在这http://blog.csdn.net/fjsd155/article/details/6866991
#include<iostream> #include<stdio.h> #include<algorithm> #include<iomanip> #include<cmath> #include<string> #include<vector> using namespace std; __int64 mod=100000007; int dis[360005],data[360005],next[360005]; __int64 euler(__int64 n) { int i; __int64 ans=1; for(i=2;i*i<=n;i++) if(n%i==0) { ans*=i-1; n/=i; while(n%i==0) { ans*=i; n/=i; } } if(n>1) ans*=n-1; return ans%mod; } int get_next(int n) { int i=0,j=-1; next[0]=-1; while(i<n) { if(j==-1||dis[i]==dis[j]) { i++; j++; next[i]=j; } else j=next[j]; } i=n-j; if(n%i) return n; return i; } __int64 pows(__int64 a,__int64 b) { __int64 ans=1; a%=mod; while(b) { if(b&1) ans=(ans*a)%mod; b>>=1; a=(a*a)%mod; } return ans%mod; } __int64 polya(__int64 m,__int64 n) { int i,j; __int64 ans=0; for(i=1;i*i<=n;i++) { if(n%i==0) { ans=(ans+pows(m,n/i)*euler(i)%mod)%mod; if(i*i!=n) ans=(ans+pows(m,i)*euler(n/i)%mod)%mod; } } return (ans*pows(n,mod-2))%mod; } int main() { int n,i,j,k,t,m,s,p; while(cin>>s>>p) { if(s==-1&&p==-1) break; for(i=0;i<p;i++) cin>>data[i]; sort(data,data+p); for(i=1;i<p;i++) dis[i]=data[i]-data[i-1]; dis[0]=360000-data[p-1]+data[0]; int len=get_next(p); printf("%I64d ",polya(pows(s,len),p/len)); } return 0; }