Codeforces ECR #142 : F2. Graph Coloring (hard version)

コードは短い。
https://codeforces.com/contest/1792/problem/F2

問題

整数Nが与えられる。
N頂点の完全グラフを考える。
各辺を赤または青で塗り分けることを考える。
頂点集合SがRed-connectedとは、S内の点同士は赤辺だけで連結していることをいう。Blue-connectedも同様に定義される。

以下を満たす塗り分けかたは何通りか。

• 赤辺も青辺も1つ以上ある。
• 2要素以上のあらゆるSについて、Red-connectedかBlue-connectedのいずれかである。

解法

ある無向グラフが非連結である場合、その補グラフは連結である。
また、補グラフが非連結である場合、元のグラフは連結である。

よって、Red-赤辺と青辺のグラフの少なくとも片方は連結となる。
問題は、両方連結となるケースが残っているのでそれを取り除く必要がある。

f(n)をnに対する解とする。f(n)はRed-disconnectedかBlue-disconnectedである。
g(n)はf(n)のうちBlue-connectedなグラフとすると、n＞1に対しf(n)=2*g(n)である。

1番の頂点とBlue-connectedな頂点数kを総当たりすると、
となる。
これでf(N)をO(N^2)で計算できる。

想定解はこれを畳み込むことでO(NlogN)にすることらしいが、O(N^2)でもギリギリ通る。

int N;
const ll mo=998244353;
ll A[50500],B[50500];
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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;

	cin>>N;
	A[1]=B[1]=1;
	for(i=2;i<=N;i++) {
		for(k=1;k<i;k++) B[i]+=B[k]*A[i-k]%mo*factr[k-1]%mo*factr[i-k]%mo;
		B[i]=B[i]%mo*fact[i-1]%mo;
		A[i]=B[i]*2%mo;
	}
	cout<<(A[N]+mo-2)%mo<<endl;
	
}

まとめ

ボス問でゴリ押しできるの珍しい。