先往上套Burnside引理
既然要求没有$frac{2*π}{n}$的角，也就是说两个人不能挨着，那么相当于给一个环黑白染色，两个相邻的点不能染白色，同时求方案数。考虑$n$个置换子群，即向一边旋转i(1<=i<=n)个单位，那么每个置换子群下循环节的长度是$lcm(i,n)/i$，那循环节数目就是$n/(lcm(i,n)/i)=gcd(i,n)$，然后式子就出来了，设$p(i)$是给长度为$i$的环染色的方案
$ans=frac{sumlimits_{i=1}^np(gcd(i,n))}{n}$
如果我们能快速算$p$那么枚举$d=gcd(i,n)$即可，现在考虑如何算$p$，不妨先设$dp[i][0/1]$表示染了长度为$i$的环，两边白色的点的数目为$0/1$的方案数，转移显然
$dp[i][0]=dp[i-1][0]+dp[i-1][1],dp[i][1]=dp[i-1][0]$
可见$dp[i][0]$就是$i-1$的答案，$dp[i][1]$就是$dp[i-1][0]$也就是$i-2$的答案，所以$p[i]=p[i-1]+p[i-2]$，矩乘即可
注意$n=1$“两边”都是可以染白色的，判掉
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int mod=1e9+7; 6 struct a 7 { 8 int mat[2][2]; 9 void Clean() 10 { 11 memset(mat,0,sizeof mat); 12 } 13 void Init1() 14 { 15 Clean(); 16 mat[0][0]=1,mat[0][1]=3; 17 } 18 void Init2() 19 { 20 Clean(); 21 mat[0][1]=mat[1][0]=mat[1][1]=1; 22 } 23 }; 24 a Matime(a x,a y) 25 { 26 a ret; ret.Clean(); 27 for(int i=0;i<2;i++) 28 for(int k=0;k<2;k++) 29 for(int j=0;j<2;j++) 30 ret.mat[i][j]+=1ll*x.mat[i][k]*y.mat[k][j]%mod,ret.mat[i][j]%=mod; 31 return ret; 32 } 33 a Maqpow(a x,int k) 34 { 35 if(k==1) return x; 36 a tmp=Maqpow(x,k/2); 37 return k%2?Matime(x,Matime(tmp,tmp)):Matime(tmp,tmp); 38 } 39 int Calc(int x) 40 { 41 if(x==1) return 1; 42 if(x==2) return 3; 43 a fir,cal; fir.Init1(),cal.Init2(); 44 cal=Maqpow(cal,x-2),fir=Matime(fir,cal); 45 return fir.mat[0][1]; 46 } 47 int Phi(int x) 48 { 49 int ret=x; 50 for(int i=2;i*i<=x;i++) 51 if(x%i==0) 52 { 53 ret/=i,ret*=i-1; 54 while(x%i==0) x/=i; 55 } 56 if(x!=1) ret/=x,ret*=x-1; 57 return ret; 58 } 59 void exGCD(int a,int b,int &x,int &y) 60 { 61 if(!b) x=1,y=0; 62 else exGCD(b,a%b,y,x),y-=a/b*x; 63 } 64 int Inv(int x) 65 { 66 int xx,yy; 67 exGCD(x,mod,xx,yy); 68 return (xx%mod+mod)%mod; 69 } 70 int Solve(int x) 71 { 72 if(x==1) return 2; 73 int ret=0; 74 for(int i=1;i*i<=x;i++) 75 if(x%i==0) 76 { 77 ret+=1ll*Phi(x/i)*Calc(i)%mod,ret%=mod; 78 if(i*i!=x) ret+=1ll*Phi(i)*Calc(x/i)%mod,ret%=mod; 79 } 80 return 1ll*ret*Inv(x)%mod; 81 } 82 int main() 83 { 84 int n; 85 while(scanf("%d",&n)!=EOF) 86 printf("%d ",Solve(n)); 87 return 0; 88 }