AtCoder ABC #284 : Ex - Count Unlabeled Graphs

これはしんどい。
https://atcoder.jp/contests/abc284/tasks/abc284_h

問題

整数N,Kが与えられる。
N頂点からなる単純無向グラフのうち、以下のものは何通りか。

• 各点に1～Kのラベルを振るとき、1～Kはいずれも最低1回は登場する。
• ラベルを並べ替えて同じ形状のグラフになるものは、1つと数える。

解法

まず、包除原理の要領で、指定されたL色内における組み合わせを求められれば「最低1回」の条件は解決できる。

あとはポリアの数え上げ定理の要領で、ラベルの並べ替え方Pに対し、同形となるグラフの数を数え、その平均を取ればよい。
PがM個のサイクル(要素数C1,C2,C3,....)で表現される場合、サイクル内は同じ色でなければならないので、色の組み合わせはL^M通り。
あとはサイクル内およびサイクル間の辺の有無を考えていこう。

サイクル内に距離1～(|Ci|/2)の範囲の距離の点同士には辺があってもなくてもよいので、2^(|Ci|/2)だけ辺の有無の組み合わせがある。
また、要素数CiとCjのサイクルの間には、GCD(Ci,Cj)通りだけ辺を張っても張らなくてもよいので、2^GCD(Ci,Cj)だけ辺の有無の組み合わせがある。

あとは、CのバリエーションをDFSで求めて行こう。

int N,K;
ll mo;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}


ll dfs(vector<int>& V,int lef,int nex) {
	if(lef==0) {
		ll a=0;
		
		for(int i=1;i<=K;i++) {
			if((K-i)%2==0) {
				a+=comb(K,i)*modpow(i,V.size())%mo;
			}
			else {
				a-=comb(K,i)*modpow(i,V.size())%mo;
			}
		}
		map<int,int> M;
		FORR(v,V) M[v]++;
		ll pat=1;
		FORR2(a,b,M) pat=pat*factr[b]%mo;
		
		ll sum=0;
		int x,y;
		
		int lef=N;
		FOR(x,V.size()) {
			pat=pat*comb(lef,V[x])%mo*fact[V[x]-1]%mo;
			lef-=V[x];
		}
		
		FOR(x,V.size()) {
			sum+=V[x]/2;
			FOR(y,x) sum+=__gcd(V[x],V[y]);
		}
		return a*modpow(2,sum)%mo*pat%mo;
	}
	ll ret=0;
	for(int i=1;i<=min(lef,nex);i++) {
		V.push_back(i);
		ret+=dfs(V,lef-i,i);
		V.pop_back();
	}
	return ret%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>mo;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;

	vector<int> V;
	ll ret=dfs(V,N,N)%mo;
	ret=ret*factr[N]%mo;
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

うーん、こういう式変形が自力でできる気がしないけど、パターンとかあるのかな。