「BZOJ1478」Sgu282 Isomorphism

2015年4月25日4,7893

Description

给定一个N 个结点的无向完全图（任意两个结点之间有一条边），现在你可以用 M 种颜色对这个图的每条边进行染色，每条边必须染一种颜色。若两个已染色的图，其中一个图可以通过结点重新编号而与另一个图完全相同，就称这两个染色方案相同。现在问你有多少种本质不同的染色方法，输出结果 mod P。P 是一个大于N 的质数。

Input

仅一行包含三个数，N、M、P。

Output

仅一行，为染色方法数 mod P 的结果。

Sample Input

3 4 97

Sample Output

HINT

数据范围：1≤N≤53，1≤M≤1000，N<p≤10 9=”” 。<br=””>

题解

http://wenku.baidu.com/link?url=i2mtMxLrmZg9JfaCcDxbBYarmqaL4Puu102REwGaCVKysP1ou_df_YzTHQw7A1Ld7RR7_pOwtbqzcvznO3BqPLTYZiVmLElrZS0Ds274OQK

论文最后一道例题

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
ll n,m,P,tot,ans;
int l[60],K[60];
ll fac[60];
ll qpow(ll a,ll b)
{
	ll ans=1;
	for(int i=b;i;i>>=1,a=a*a%P)
		if(i&1)ans=ans*a%P;
	return ans;
}
void cal(int k)
{
	ll s=1;
	for(int i=1;i<=n;i++)K[i]=0;
	for(int i=1;i<=k;i++)K[l[i]]++;
	for(int i=1;i<=k;i++)s=s*l[i]%P;
	for(int i=1;i<=n;i++)s=s*fac[K[i]]%P;
	int c=0;
	for(int i=1;i<=k;i++)
	{
		c+=l[i]/2;
		for(int j=i+1;j<=k;j++)
			c+=gcd(l[i],l[j]);
	}
	ans=(ans+qpow(m,c)*fac[n]%P*qpow(s,P-2)%P)%P;
}
void dfs(int x,int k,int last)
{
	if(x==n+1)
	{
		cal(k-1);
		return;
	}
	for(int i=1;i<=last&&x+i<=n+1;i++)
	{
		l[k]=i;
		dfs(x+i,k+1,i);
	}
}
int main()
{
	n=read();m=read();P=read();
	fac[0]=1;for(int i=1;i<60;i++)fac[i]=fac[i-1]*i%P;
	dfs(1,1,n);
	printf("%lld\n",ans*qpow(fac[n],P-2)%P);
	return 0;
}

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int gcd(int a,int b)

{

return b==0?a:gcd(b,a%b);

}

ll n,m,P,tot,ans;

int l[60],K[60];

ll fac[60];

ll qpow(ll a,ll b)

{

ll ans=1;

for(int i=b;i;i>>=1,a=a*a%P)

if(i&1)ans=ans*a%P;

return ans;

}

void cal(int k)

{

ll s=1;

for(int i=1;i<=n;i++)K[i]=0;

for(int i=1;i<=k;i++)K[l[i]]++;

for(int i=1;i<=k;i++)s=s*l[i]%P;

for(int i=1;i<=n;i++)s=s*fac[K[i]]%P;

int c=0;

for(int i=1;i<=k;i++)

{

c+=l[i]/2;

for(int j=i+1;j<=k;j++)

c+=gcd(l[i],l[j]);

}

ans=(ans+qpow(m,c)*fac[n]%P*qpow(s,P-2)%P)%P;

}

void dfs(int x,int k,int last)

{

if(x==n+1)

{

cal(k-1);

return;

}

for(int i=1;i<=last&&x+i<=n+1;i++)

{

l[k]=i;

dfs(x+i,k+1,i);

}

int main()

{

n=read();m=read();P=read();

fac[0]=1;for(int i=1;i<60;i++)fac[i]=fac[i-1]*i%P;

dfs(1,1,n);

printf("%lld\n",ans*qpow(fac[n],P-2)%P);

return 0;

}

« 「POJ2154」Color 「BZOJ3206」[Apio2013] 道路费用 »

De℃,.: )

论文地址没有贴全？

hzwer

有什么问题么。。

De℃,.: )

http://wenku.baidu.com/link?url=i2mtMxLrmZg9JfaCcDxbBYarmqaL4Puu102REwGaCVKysP1ou_df_YzTHQw7A1Ld7RR7_pOwtbqzcvznO3BqPLTYZiVmLElrZS0Ds274OQK

贴上了，只不过正文中没有显示全……

hzwer.com _ Home | http://hzwer.com

「BZOJ1478」Sgu282 Isomorphism

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论