CodeQUEEN 2025 決勝 : F - アクリルスタンド

これは割と典型な気がする。
https://atcoder.jp/contests/codequeen2025-final-Public/tasks/codequeen2025_final_f

問題

N個のアクリルスタンドを一列に並べたい。
その際、隣接させてはならないアクリルスタンドの対がM個指定される。
条件を満たす並べ方は何通りか。

解法

包除原理で解く。
隣接させてはならない対をいくつか定め、それらの対がいずれも隣接するような並べ方を考える。
N点のグラフに対し、隣接させてはならない対となるアクリルスタンドに対応する頂点間に辺を引こう。
その際、閉路ができたり、次数が３以上の辺がある場合、条件を満たす並び方は存在しない。
そうでない場合、(連結成分数)!×2^(2要素以上からなる連結成分)の数だけ並べ方がある。

int N,M;
int A[16],B[16];
const int NUM_=1400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
int E[32];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

const ll mo=998244353;
ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

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>>M;
	vector<int> V;
	FOR(i,M) {
		cin>>A[i]>>B[i];
		V.push_back(A[i]);
		V.push_back(B[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	FOR(i,M) {
		A[i]=lower_bound(ALL(V),A[i])-V.begin();
		B[i]=lower_bound(ALL(V),B[i])-V.begin();
	}
	ll ret=0;
	int mask;
	FOR(mask,1<<M) {
		UF<32> uf;
		ZERO(E);
		int ok=1;
		FOR(i,M) if(mask&(1<<i)) {
			if(uf[A[i]]==uf[B[i]]) break;
			uf(A[i],B[i]);
			E[A[i]]++;
			E[B[i]]++;
		}
		if(i<M) continue;
		int num=N-V.size();
		ll pat=1;
		FOR(i,V.size()) {
			if(E[i]>2) pat=0;
			if(uf[i]==i) {
				num++;
				if(uf.count(i)>1) pat=pat*2;
			}
		}
		pat=pat*fact[num]%mo;
		if(__builtin_popcount(mask)%2) {
			ret+=mo-pat;
		}
		else {
			ret+=pat;
		}
		
	}
	cout<<ret%mo<<endl;
	
}

まとめ

こちらはすんなり。