前言
计数题
题目相关
题目链接
题目大意
n n n个点的完全图，对边染色（颜色有 m m m种），求本质不同的染色方案数，答案对 p p p取模
数据范围
1 ≤ n ≤ 53 , 1 ≤ m ≤ 1000 , 1 ≤ p ≤ 1 0 9 1\le n\le53,1\le m\le1000,1\le p\le10^9 1≤n≤53,1≤m≤1000,1≤p≤109
题解
我们乍一看是染色问题，我们就想到了Polya定理
l
=
1
∣
G
∣
∑
a
i
∈
G
k
λ
(
a
i
)
l=\frac{1}{|G|}\sum_{a_i\in G}k^{\lambda(a_i)}
l=∣G∣1ai∈G∑kλ(ai)
我们可以用其式子来计算
但是我们发现染色的是边而不是点，而是边，所以我们计算的置换是对于边的
我们考虑先不枚举边置换，而是枚举点的置换，容易发现，一个点置换，其对应的边置换是唯一确定的
这样一来，就有了方便的枚举置换方式
我们发现，点的置换有
n
!
n!
n!种，我们发现
53
!
53!
53!的复杂度显然不能接受
我们考虑不直接枚举所有点置换，而是枚举本质不同的点置换，本质相同的点置换，对应的边置换也是本质相同的
这样的话复杂度就是
n
n
n的整数划分了，随便写个程序就可以发现当
n
=
53
n=53
n=53时，整数划分是
3
∗
1
0
5
3*10^5
3∗105级别的，目前看起来可以接受
code
#include<cstdio>
#include<cctype>
#define rg register
template<typename T>inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template<typename T>inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template<typename T>inline void print(const T x){if(x>=0)printe(x);else putchar('-'),printe(-x);}
int n,ans;
void dfs(const int t,const int h)
{
if(t==0)ans++;
else for(rg int i=h;i<=t;i++)dfs(t-i,i);
}
int main()
{
read(n);
dfs(n,1);
print(ans);
return 0;
}
我们考虑现在得到了一个整数划分，其有
k
k
k个循环，按循环长度排序后的第
i
i
i个循环长度为
L
i
L_i
Li即
L
1
≤
L
2
≤
⋅
⋅
⋅
≤
L
k
L_1\le L_2\le···\le L_k
L1≤L2≤⋅⋅⋅≤Lk
我们思考对于这样一个点置换，其对应的边置换的循环数量（在Polya中要求的东西）
两个端点在同一个长度为
L
L
L的点循环内的情况：
我们发现，对于任意一条边，将其两边的点转动，这样就可以产生一个大小为
L
L
L的边循环
然后这个时候有个特例，当
L
L
L为偶数时，有一个大小为
L
2
\frac{L}{2}
2L的循环，即环上每组相对的点所组成的循环
即：
L
L
L为奇数时，循环数为
(
L
2
)
L
=
L
∗
(
L
−
1
)
/
2
L
=
L
−
1
2
\frac{\binom{L}{2}}{L}=\frac{L*(L-1)/2}{L}=\frac{L-1}2
L(2L)=LL∗(L−1)/2=2L−1
L
L
L为偶数时，循环数为
(
L
2
)
+
L
2
L
=
L
∗
(
L
−
1
)
/
2
+
L
/
2
L
=
L
2
\frac{\binom{L}{2}+\frac{L}{2}}{L}=\frac{L*(L-1)/2+L/2}{L}=\frac L2
L(2L)+2L=LL∗(L−1)/2+L/2=2L
综上，这里的边循环数为
⌊
L
2
⌋
\left\lfloor\frac L2\right\rfloor
⌊2L⌋
两个端点分别在长度为
L
a
L_a
La、
L
b
L_b
Lb的点循环内的情况：
容易发现，这里的边循环长度为
l
c
m
(
L
a
,
L
b
)
lcm(L_a,L_b)
lcm(La,Lb)
那么循环数量为
L
a
∗
L
b
l
c
m
(
L
a
,
L
b
)
=
g
c
d
(
L
a
,
L
b
)
\frac{L_a*L_b}{lcm(L_a,L_b)}=gcd(L_a,L_b)
lcm(La,Lb)La∗Lb=gcd(La,Lb)
这样的话，对于一个枚举到的本质不同的点循环，其对Poyla定理中后面那个sigma的指数
C
C
C就为
C
=
∑
i
=
1
k
⌊
L
i
2
⌋
+
∑
i
=
1
k
∑
j
=
i
+
1
k
(
L
i
,
L
j
)
C=\sum_{i=1}^k\left\lfloor\frac {L_i}2\right\rfloor+\sum_{i=1}^k\sum_{j=i+1}^k(L_i,L_j)
C=i=1∑k⌊2Li⌋+i=1∑kj=i+1∑k(Li,Lj)
我们也知道颜色数，现在还需要统计这种点循环的出现次数
容易发现，出现次数
S
S
S可以直接计算
我们设
T
i
T_i
Ti为长度为
i
i
i的
L
L
L出现的次数（另外，定义
0
!
=
1
0!=1
0!=1）
S
=
∏
i
=
1
k
(
L
i
−
1
)
!
(
n
−
∑
j
=
1
i
−
1
L
j
L
i
)
∏
i
=
1
n
T
i
!
=
n
!
∏
i
=
1
n
T
i
!
∗
∏
i
=
1
k
L
i
S=\frac{\prod_{i=1}^k(L_i-1)!\binom{n-\sum_{j=1}^{i-1}L_j}{L_i}}{\prod_{i=1}^{n}T_i!}=\frac{n!}{\prod_{i=1}^{n}T_i!*\prod_{i=1}^{k}L_i}
S=∏i=1nTi!∏i=1k(Li−1)!(Lin−∑j=1i−1Lj)=∏i=1nTi!∗∏i=1kLin!
这样的话我们就能快速的求出
S
S
S
最终答案就可以算出来了
l
=
S
∗
m
C
n
!
l=\frac{S*m^C}{n!}
l=n!S∗mC
代码
这份代码为了方便理解，写的复杂度比较大，实际可以有更好的写法使程序跑得更快
#include<cstdio>
#include<cctype>
#define rg register
typedef long long ll;
template<typename T>inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template<typename T>inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');}
template<typename T>inline void print(const T x){if(x>=0)printe(x);else putchar('-'),printe(-x);}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
ll n,m,p,L[61],fac[61],ans,tim[61];
inline ll pow(ll x,ll y)
{
ll res=1;
for(;y;y>>=1,x=x*x%p)if(y&1)res=res*x%p;
return res;
}
void dfs(const int step,const int t,const int h)
{
if(t==0)
{
ll xs=0,xf=1;
for(rg int i=1;i<step;i++)
{
xs+=L[i]>>1;
for(rg int j=i+1;j<step;j++)xs+=gcd(L[i],L[j]);
xf=xf*L[i]%p;
}
for(rg int i=1;i<=n;i++)xf=xf*fac[tim[i]]%p;
ans+=pow(m,xs)*pow(xf,p-2)%p;
}
else for(rg int i=h;i<=t;i++)
{
L[step]=i;
tim[i]++;
dfs(step+1,t-i,i);
tim[i]--;
}
}
int main()
{
read(n),read(m),read(p);
fac[0]=1;for(rg int i=1;i<=60;i++)fac[i]=fac[i-1]*i%p;
dfs(1,n,1);
print(ans%p);
return 0;
}
总结
代码非常的清真，良好的计数技巧配上Poyla定理就能解决这题计数好难