Count the Tetris

本文主要是介绍Count the Tetris，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Count the Tetris

题解

这是一道很经典的Burnside的题目。

我们很容易发现对于一个长度为n的环，需要一个置换中的不动点满足它的所有循环中的点颜色相同，那么在旋转i次的置换中，循环共有个。由于后面的循环都是重复的我们只需计算这段的染色方案即可。

看到题目限制，如果直接统计的话肯定会T，所以需要用矩阵乘法来进行统计。

考虑n特别大的范围，还需要欧拉函数对其进行优化，枚举置换的循环节个数i，与其等价的置换群共有个，需要再将其乘上去，而我们只需要枚举n的因数来进行计算。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define MAXN 40010
typedef long long LL;
//#define int LL
typedef pair<int,int> pii;
const int mo=9973;
#define gc() getchar()
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
int prime[MAXN],cntp,n,m,k;
bool oula[MAXN];
struct Matrix{int c[15][15];//Matrix(){memset(c,0,sizeof(0));}/*Martix operator * (const Martix &b)const{Martix res;for(int i=0;i<m;i++)for(int k=0;k<m;k++)if(c[i][k])for(int j=0;j<m;j++)(res.c[i][j]+=c[i][k]*b.c[k][j]%mo)%mo;return res;}*/
}mat;
Matrix mult(Matrix ta,Matrix tb){Matrix tc;memset(tc.c,0,sizeof(tc.c));for(int i=0;i<m;i++)for(int k=0;k<m;k++)if(ta.c[i][k])for(int j=0;j<m;j++)(tc.c[i][j]+=ta.c[i][k]*tb.c[k][j])%=mo;return tc;
}
Matrix Matpow(Matrix a,int s){Matrix t;memset(t.c,0,sizeof(t.c));for(int i=0;i<m;i++)t.c[i][i]=1;while(s){if(s&1)t=mult(t,a);a=mult(a,a);s>>=1;}return t;
}
int qkpow(int a,int s){int t=1;a%=mo;while(s){if(s&1)t=t*a%mo;a=a*a%mo;s>>=1;}return t;
}
void init(){for(int i=2;i<=4e4;i++){if(oula[i])continue;prime[cntp++]=i;for(int j=i*i;j<=4e4;j+=i)oula[j]=1;}
}
int euler(int cur){int ans=cur,x=cur;for(int i=0;i<cntp&&prime[i]*prime[i]<=cur;i++)if(x%prime[i]==0){ans=ans/prime[i]*(prime[i]-1);while(x%prime[i]==0)x/=prime[i];}if(x>1)ans=ans/x*(x-1);return ans%mo;
}
int cal(int len){int res=0;Matrix t=Matpow(mat,len);for(int i=0;i<m;i++)(res+=t.c[i][i])%=mo;return res;
}
int Polya(){int ans=0;for(int i=1;i*i<=n;i++){if(n%i)continue;if(i*i==n)(ans+=cal(i)*euler(i))%=mo;else (ans+=cal(i)*euler(n/i)+cal(n/i)*euler(i))%=mo;//printf("%d:%d\n",i,ans);}return ans*qkpow(n,mo-2)%mo;
}
signed main(){int T;read(T);init();while(T--){read(n);read(m);read(k);for(int i=0;i<m;i++)for(int j=0;j<m;j++)mat.c[i][j]=1;for(int i=1;i<=k;i++){int u,v;read(u);read(v);mat.c[u-1][v-1]=mat.c[v-1][u-1]=0;}printf("%d\n",Polya());}return 0;
}

 

这篇关于Count the Tetris的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---