前言

計數題

題目相關

題目鏈接

題目大意

$n$個點的完全圖，對邊染色（顏色有$m$種），求本質不同的染色方案數，答案對$p$取模

數據范圍

$1\le n\le 53,1\le m\le 1000,1\le p\le 10^9$

題解

我們乍一看是染色問題，我們就想到了Polya定理
$$l=\frac{1}{|G|}\sum _{a_i\in G}{k}^{\lambda (a_i)}$$
我們可以用其式子來計算
但是我們發現染色的是邊而不是點，而是邊，所以我們計算的置換是對于邊的
我們考慮先不枚舉邊置換，而是枚舉點的置換，容易發現，一個點置換，其對應的邊置換是唯一確定的
這樣一來，就有了方便的枚舉置換方式
我們發現，點的置換有$n!$種，我們發現$53!$的復雜度顯然不能接受
我們考慮不直接枚舉所有點置換，而是枚舉本質不同的點置換，本質相同的點置換，對應的邊置換也是本質相同的
這樣的話復雜度就是$n$的整數劃分了，隨便寫個程序就可以發現當$n=53$時，整數劃分是$3?10^5$級別的，目前看起來可以接受
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$個循環，按循環長度排序后的第$i$個循環長度為$L_i$即$L_1\le L_2\le ???\le L_k$
我們思考對于這樣一個點置換，其對應的邊置換的循環數量（在Polya中要求的東西）
兩個端點在同一個長度為$L$的點循環內的情況：
我們發現，對于任意一條邊，將其兩邊的點轉動，這樣就可以產生一個大小為$L$的邊循環
然后這個時候有個特例，當$L$為偶數時，有一個大小為$\frac{L}{2}$的循環，即環上每組相對的點所組成的循環
即：
$L$為奇數時，循環數為$\frac{\left(\genfrac{}{}{0ex}{}{L}{2}\right)}{L}=\frac{L?(L?1)/2}{L}=\frac{L?1}{2}$
$L$為偶數時，循環數為$\frac{\left(\genfrac{}{}{0ex}{}{L}{2}\right)+\frac{L}{2}}{L}=\frac{L?(L?1)/2+L/2}{L}=\frac{L}{2}$
綜上，這里的邊循環數為$?\frac{L}{2}?$
兩個端點分別在長度為$L_a$、$L_b$的點循環內的情況：
容易發現，這里的邊循環長度為$lcm(L_a,L_b)$
那么循環數量為$\frac{L_a?L_b}{lcm(L_a,L_b)}=gcd(L_a,L_b)$

這樣的話，對于一個枚舉到的本質不同的點循環，其對Poyla定理中后面那個sigma的指數$C$就為
$$C=\sum _{i=1}^k?\frac{L_i}{2}?+\sum _{i=1}^k\sum _{j=i+1}^k(L_i,L_j)$$
我們也知道顏色數，現在還需要統計這種點循環的出現次數
容易發現，出現次數$S$可以直接計算
我們設$T_i$為長度為$i$的$L$出現的次數（另外，定義$0!=1$）
$$S=\frac{{\prod }_{i=1}^k(L_i?1)!\left(\genfrac{}{}{0ex}{}{n?{\sum }_{j=1}^{i?1}{L}_j}{L_i}\right)}{{\prod }_{i=1}^n{T}_i!}=\frac{n!}{{\prod }_{i=1}^n{T}_i!?{\prod }_{i=1}^k{L}_i}$$
這樣的話我們就能快速的求出$S$
最終答案就可以算出來了
$$l=\frac{S?m^C}{n!}$$

代碼

這份代碼為了方便理解，寫的復雜度比較大，實際可以有更好的寫法使程序跑得更快

#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定理就能解決這題
計數好難

總結

以上是生活随笔為你收集整理的[luogu4128][shoi2006]有色图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。