首页 技术 正文
技术 2022年11月23日
0 收藏 708 点赞 3,976 浏览 3207 个字

三道burnside入门题:

Burnside定理主要理解置换群置换后每种不动点的个数,然后n种不动点的染色数总和/n为answer。

对于旋转,旋转i个时不动点为gcd(n,i).

传送门:poj 2409

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdlib>
#define LL long long
#define N 25
#define mod 1000000007
using namespace std;
LL p[];
int gcd(int a,int b)
{
return b==?a:gcd(b,a%b);
}
LL power(LL a,LL n)
{
LL res=;
while(n)
{
if(n&)res*=a;
a=a*a;
n>>=;
}
return res;
}
int main()
{
int n,k;
while(scanf("%d%d",&k,&n)>)
{
if(n+k==)break;
LL ans;
if(n&)ans=n*power(k,n/+);
else ans=n/*(power(k,n/)+power(k,n/+));
for(int i=;i<=n;i++)ans+=power(k,gcd(n,i));
printf("%lld\n",ans/(*n));
}
}

传送门:poj 2154

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdlib>
#define LL long long
#define N 35000
#define mod 1000000007
using namespace std;
int n,p;
int prime[N+],tot;
bool vis[N+];
void init()
{
tot=;
memset(vis,false,sizeof(vis));
for(int i=;i<=N;i++)
{
if(!vis[i])
{
prime[tot++]=i;
}
for(int j=;j<tot;j++)
{
if(i*prime[j]>N)break;
vis[i*prime[j]]=true;
}
}
}
LL power(LL a,LL n)
{
LL res=;
while(n)
{
if(n&)res=res*a%p;
a=a*a%p;
n>>=;
}
return res;
}
LL Phi(int x)
{
int res=;
for(int i=;prime[i]*prime[i]<=x&&x>;i++)
{
if(x%prime[i]==)
{
res*=prime[i]-;
x/=prime[i];
while(x%prime[i]==)
{
x/=prime[i];
res*=prime[i];
}
}
}
if(x>)res*=x-;
return res;
}
int primefactor[N<<],sz;
void factor(int x)
{
sz=;
for(int i=;i*i<=x;i++)
{
if(x%i==)
{
primefactor[sz++]=i;
if(i*i!=x)primefactor[sz++]=n/i;
}
}
}
LL solve(int n)
{
factor(n);
LL ans=;
for(int i=;i<sz;i++)
{
ans=(ans+Phi(n/primefactor[i])*power(n,primefactor[i]-))%p;
}
return ans;
}
int main()
{
int T;init();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&p);
printf("%d\n",solve(n));
}
}

传送门:poj 2888

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdlib>
#define LL long long
#define N 35000
#define mod 9973
using namespace std;
int n,m,k;
int prime[N+],tot;
bool vis[N+];
struct matrix
{
int m[][];
void zore()
{
memset(m,,sizeof(m));
}
void unit()
{
for(int i=;i<;i++)
for(int j=;j<;j++)
m[i][j]=i==j;
}
}g;
matrix mult(matrix a,matrix b)
{
matrix c;
c.zore();
for(int k=;k<m;k++)
for(int i=;i<m;i++)
{
if(a.m[i][k]==)continue;
for(int j=;j<m;j++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
return c;
}
matrix quick_power(matrix a,int n)
{
matrix res;
res.unit();
while(n>)
{
if(n&)res=mult(res,a);
a=mult(a,a);
n>>=;
}
return res;
}
int calc(int n)
{
int ans=;
matrix res=quick_power(g,n);
for(int i=;i<m;i++)
{
ans=(ans+res.m[i][i])%mod;
}
return ans;
}
void init()
{
tot=;
memset(vis,false,sizeof(vis));
for(int i=;i<=N;i++)
{
if(!vis[i])
{
prime[tot++]=i;
}
for(int j=;j<tot;j++)
{
if(i*prime[j]>N)break;
vis[i*prime[j]]=true;
}
}
}
LL Phi(int x)
{
int res=;
for(int i=;prime[i]*prime[i]<=x&&x>;i++)
{
if(x%prime[i]==)
{
res*=prime[i]-;
x/=prime[i];
while(x%prime[i]==)
{
x/=prime[i];
res*=prime[i];
}
}
}
if(x>)res*=x-;
return res;
}
int primefactor[N<<],sz;
void factor(int x)
{
sz=;
for(int i=;i*i<=x;i++)
{
if(x%i==)
{
primefactor[sz++]=i;
if(i*i!=x)primefactor[sz++]=n/i;
}
}
}
int power(int a,int n)
{
int res=;
a%=mod;
while(n)
{
if(n&)res=res*a%mod;
a=a*a%mod;
n>>=;
}
return res;
}
int solve(int n)
{
factor(n);
int ans=;
for(int i=;i<sz;i++)
{
ans=(ans+Phi(n/primefactor[i])*calc(primefactor[i]))%mod;
}
return ans*power(n,mod-)%mod;
}
int main()
{
int T;
scanf("%d",&T);
init();
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
g.zore();
for(int i=;i<m;i++)
for(int j=;j<m;j++)
g.m[i][j]=;
while(k--)
{
int u,v;
scanf("%d%d",&u,&v);
u--;v--;
g.m[u][v]=g.m[v][u]=;
}
printf("%d\n",solve(n));
}
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,284
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,711
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,550
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,322
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,960
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,120