网站推广的基本手段,域名访问升级紧急中拿笔记好,简单网页制作,最简单的软件开发工具Atcoder ARC062F - AtCoDeerくんとグラフ色塗り / Painting Graphs with AtCoDeer
题目描述
简要题意#xff1a;给定一个有标号的无向图#xff0c;你可以给每条边染上KKK种颜色之一#xff0c;求本质不同的图的染色方案#xff08;两个图本质不同定义为不能通过若干次环…Atcoder ARC062F - AtCoDeerくんとグラフ色塗り / Painting Graphs with AtCoDeer
题目描述
简要题意给定一个有标号的无向图你可以给每条边染上KKK种颜色之一求本质不同的图的染色方案两个图本质不同定义为不能通过若干次环的旋转使这两个图每条边的染色相同。
Solution
分类讨论 倘若是一条单边不包含在任何环中则它的颜色任意方案数为KKK。
倘若是一个单环不与其他环的边相交则环上的颜色要旋转后本质不同经典的BurnsideBurnsideBurnside问题设环长为cntcntcnt则方案数为∑i0sz−1kgcd(i,sz)\sum_{i0}^{sz-1} k^{gcd(i,sz)}∑i0sz−1kgcd(i,sz)
倘若是两个或以上的环嵌套可以发现环上的颜色都是可以互换的两个嵌套环不同当且仅当某种颜色的个数不同因此方案数就是一个插板法设嵌套环有szszsz条边则方案数为C(szK−1,K−1)C(szK-1,K-1)C(szK−1,K−1)。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
vectorint e[MAXN],V[MAXN];
int fac[MAXN],inv[MAXN],dfn[MAXN],low[MAXN],stk[MAXN],flag[MAXN],top0,num0,DFN0,n,m,k;
inline int quick_pow(int x,int y)
{int ret1;for (;y;y1){if (y1) ret1ll*ret*x%mods;x1ll*x*x%mods;}return ret;
}
inline void Init(int n)
{fac[0]1; for (int i1;in;i) fac[i]1ll*fac[i-1]*i%mods;inv[n]quick_pow(fac[n],mods-2);for (int in-1;i0;i--) inv[i]1ll*inv[i1]*(i1)%mods;
}
inline int upd(int x,int y) { return xymods?xy-mods:xy; }
inline int gcd(int x,int y) { return y0?x:gcd(y,x%y); }
inline int C(int x,int y) { return 1ll*fac[x]*inv[y]%mods*inv[x-y]%mods; }
inline int Burnside(int n) { int ans0; for (int i0;in;i) ansupd(ans,quick_pow(k,gcd(i,n))%mods); return 1ll*ans*quick_pow(n,mods-2)%mods; }
inline void tarjan(int x,int father)
{dfn[x]low[x]DFN;stk[top]x;for (auto v:e[x]){if (vfather) continue;if (!dfn[v]){tarjan(v,x);upmin(low[x],low[v]);if (low[v]dfn[x]){int y;V[num].PB(x);while (ystk[top--]){V[num].PB(y);if (yv) break;}}}else upmin(low[x],dfn[v]);}
}
int main()
{nread(),mread(),kread();Init(mk);for (int i1;im;i){int uread(),vread();e[u].PB(v),e[v].PB(u);}for (int i1;in;i) if (!dfn[i]) tarjan(i,0);int ans1;for (int i1;inum;i){if (V[i].size()2) ans1ll*ans*k%mods;else{int cnt0;for (int i1;in;i) flag[i]0;for (auto x:V[i]) flag[x]1;for (auto x:V[i])for (auto v:e[x]) if (flag[v]) cnt;cnt1;if (cntV[i].size()) ans1ll*ans*Burnside(cnt)%mods;else ans1ll*ans*C(cntk-1,k-1)%mods;
// coutV[i].size() cnt ansendl;}}printf(%d\n,ans);return 0;
}
