1815: [Shoi2006]color 有色图
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 136 Solved: 50[Submit][Status]
Description
Input
输入三个整数N,M,P 1< = N <= 53 1< = M < = 1000 N< P < = 10^ 9
Output
即总数模P后的余数
Sample Input
input 1 3 2 97
Sample Output
output 1 4
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define PROB "graph"
#define MAXE MAXN*MAXN
#define MAXN 66
#define MAXM MAXN*MAXN
typedef long long qword;
int n,m,mod;
struct edge
{
int x,y;
}e[MAXE];
bool operator <
(edge e1,edge e2)
{
if (e1.x==e2.x)
return e1.y<
e2.y;
return e1.x<
e2.x;
}
bool vis[MAXN];
int vec[MAXN];
qword sum=
0;
int per[MAXM];
int g[MAXN];
qword pow_mod(qword x,qword y)
{
qword ret=
1;
while (y)
{
if (y&
1)ret=ret*x%
mod;
x=x*x%
mod;
y>>=
1;
}
return ret;
}
void init()
{
int i,j,k;
int m;
int x,y;
for (i=
2;i<=n;i++
)
{
m=
0;
for (j=
0;j<i;j++
)
for (k=j+
1;k<i;k++
)
e[m].x=j,e[m++].y=
k;
for (j=
0;j<m;j++
)
{
edge et;
et.x=min((e[j].x+
1)%i,(e[j].y+
1)%
i);
et.y=max((e[j].x+
1)%i,(e[j].y+
1)%
i);
per[j]=lower_bound(e,e+m,et)-
e;
}
for (j=
0;j<m;j++
)
{
if (~
per[j])
{
g[i]++
;
x=
j;
y=
per[x];
per[x]=-
1;
while (~
per[y]){
x=
y;
y=
per[x];
per[x]=-
1;
}
}
}
}
return ;
}
int gcd(
int x,
int y)
{
return x%y==
0?y:gcd(y,x%
y);
}
qword fact[MAXN],ufact[MAXN],uval[MAXN];
int gcdv[MAXN][MAXN];
int totv;
void dfs(
int s,
int b)
{
if (!
s)
{
register qword val=
1;
register int res=
0,n0=
n,i,j;
for (i=
0;i<totv;i++
)
for (j=i+
1;j<totv;j++
)
res=(res+gcdv[vec[i]][vec[j]])%(mod-
1);
for (i=
0;i<totv;i++
)
{
res=(res+g[vec[i]])%(mod-
1);
val=val*fact[n0]%mod*ufact[n0-vec[i]]%mod*ufact[vec[i]]%
mod;
n0-=
vec[i];
}
//for (int i=0;i<totv;i++)printf("%d ",vec[i]);printf("\n");
for (i=
0;i<
totv;)
{
for (j=i;j<totv && vec[j]==vec[i];j++
);
val=val*ufact[j-i]%
mod;
i=
j;
}
for (i=
0;i<totv;i++
)
val=val*fact[vec[i]]%mod*uval[vec[i]]%
mod;
//printf("val:%d\n",val);
//printf("res:%d\n",res);
sum+=pow_mod(m,res)*val%
mod;
sum%=
mod;
return ;
}
for (
int i=b;i<=s;i++
)
{
vec[totv++]=
i;
dfs(s-
i,i);
totv--
;
}
}
int main()
{
freopen("input.txt",
"r",stdin);
int i,j,k,x,y,z;
scanf("%d%d%d",&n,&m,&
mod);
init();
fact[0]=
1;
for (i=
1;i<=n;i++
)
for (j=
1;j<=n;j++
)
gcdv[i][j]=
gcd(i,j);
for (i=
1;i<=n;i++
)
fact[i]=fact[i-
1]*i%
mod;
for (i=
0;i<=n;i++
)
ufact[i]=pow_mod(fact[i],mod-
2);
for (i=
1;i<=n;i++
)
uval[i]=pow_mod(i,mod-
2);
dfs(n,1);
printf("%lld\n",sum*ufact[n]%
mod);
}
也许我的想法和标准的想法还是有那么一点点偏差，但还是能做的，我们考虑将这道题转换为标准的染色问题，由于图的变换可以是点的任意置换，所以说图的置换群是n!个点的置换，注意，是“点的置换”，与“边的染色”，所一我们考虑点与变得关系，最朴素的做法是：枚举n!个排列，对于每个排列，算出边的置换以及置换群个数，同ploya定理做。
然后考虑到n!的排列个数太慢了。于是考虑到置换的性质，我们可以直接枚举点置换的循环节长度的组成，对于跨越两个长度x,y循环节间的边，循环节长度必定为lcm(x,y)，变得个数为x*y，所以循环节个数为gcd(x,y),但是循环节内部的边就比较麻烦，虽然看其他程序这也是一个很简单的式子，但是我不会推，就直接暴力预处理求出循环节数。
最后通过各种排列组合的公式，算出每一个循环节组成代表的排列个数，这道题就完了。
转载于:https://www.cnblogs.com/mhy12345/p/4275923.html
