BZOJ 3113: Toy November 29, 2016 ###Description 外面有一圈N个结点，中心有一个结点与N个结点都相连，总共就是2*N条边，删除N条边，使N+1个点连通，旋转相同视为等价，问有多少种情况。 ![1.jpg][1] ###Input 输入N，M 3<=N<=10^9, 2<=M<=10^9 ###Output 输出方案数 Mod M的结果 ###Sample Input 3 10000 4 10000 4 10 ###Sample Output 6 13 3 ###Solution 考虑burnside引理，假设分成d块，那么每块的方案数是和bzoj1002一样的，可以用公式 f(n+1) = 3\*f(n) - f(n-1) + 2 计算 所以得到这个公式：1/n\*Sum_{d divides n} phi(n/d)*f(d) 于是直接根号n枚举d，然后根号d求phi，矩阵快速幂求f ###Code ```c++ #include<bits/stdc++.h> typedef long long ll; typedef long double ldb; ll mod; inline ll fm(ll x,ll y) { ll tmp=(x*y-(ll)((ldb)x/mod*y+1e-8)*mod); return tmp<0?tmp+mod:tmp; } inline void mul(ll (&a)[3][3],ll (&b)[3][3],ll (&c)[3][3]) { ll t[3][3]={{0,0,0},{0,0,0},{0,0,0}}; for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) t[i][k]+=fm(a[i][j],b[j][k]); for(int i=0;i<3;i++) for(int j=0;j<3;j++) c[i][j]=t[i][j]%mod; } inline ll f(int x) { if(x<=1)return x; x--; ll a[3][3]={{1,0,2},{0,0,mod-1},{0,1,3}},b[3][3]={{1,0,0},{0,1,0},{0,0,1}}; for(int i=1;i<=x;i<<=1) { if(i&x)mul(b,a,b); mul(a,a,a); } ll ret=b[0][2]+b[2][2]; if(ret>=mod)return ret-mod;return ret; } inline int phi(int x) { int t=x; for(int i=2;i*i<=x;i++) if(x%i==0) { t/=i,t*=i-1; x/=i; while(x%i==0)x/=i; } if(x>1)t/=x,t*=x-1; return t; } int main() { int n; while(~scanf("%d%lld",&n,&mod)) { mod*=n; ll a2=0; for(int i=1;i*i<=n;i++) if(n%i==0) { if(i*i==n) { a2+=fm(phi(i),f(i)); } else { a2+=fm(phi(i),f(n/i))+fm(phi(n/i),f(i)); } a2%=mod; } printf("%lld\n",a2/n); } } ``` [1]: /usr/uploads/2016/11/709092212.jpg