kmjp's blog

競技プログラミング参加記です

AtCoder ABC #236 : Ex - Distinct Multiples

これ系の言い換え苦手。
https://atcoder.jp/contests/abc236/tasks/abc236_h

問題

正整数N,Mと、長さNの整数列Dが与えられる。
以下を満たす正整数列Aは何通りか。

  • Aの各値は異なる。
  • A[i]は1以上M以下で、D[i]の倍数

解法

Sを、頂点対(i,j)の集合とする。
f(S)を少なくともSに含まれる頂点対の値が一致するようなAの組み合わせとする。
包除原理より、解は全Sにおけるf(S)*(-1)^|S|となる。

LCM(mask) := {1,...,N}の部分集合に対応するbitmask値のmaskに対し、それらの要素番号iに対するA[i]のLCMを
g(mask) := {1,...,N}の部分集合に対応するbitmask値のmaskに対し、floor(M/LCM(mask))
とする。

h(n) := n頂点の完全グラフの部分グラフにおいて、n頂点が連結であるとき、(-1)^(辺の数)の総和
とする。これはh(n)=-(n-1)*h(n-1)を満たす。

N頂点のグラフに対し、辺を張ったところいくつかの連結成分に分かれたとする。
それに対応して、各連結成分maskに対しg(mask)*h(|mask|)の積を取り、連結成分の別れ方毎に総和と取ると、最初のf(S)*(-1)^|S|と一致する。

あとは
dp(mask) := maskに対応する頂点群に対し、いくつかの連結成分への分解の仕方における、各連結成分に対応する部分集合mask'に対するg(mask')*h(|mask'|)の積の総和
を取ることを考えよう。
maskの部分集合のうち、頂点vを含むものmask'を総当たりすると、
dp(mask) := sum(g(mask')*h(|mask'|)*dp(mask-mask'))
となる。

int N;
ll M;
ll D[17];
ll G[1<<16];
ll H[17];
const ll mo=998244353;
ll dp[1<<16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>D[i];
	int mask;
	FOR(mask,1<<N) if(mask) {
		ll lcm=1;
		FOR(i,N) if(mask&(1<<i)) {
			ll a=D[i]/__gcd(D[i],lcm);
			if(M/a<lcm) {
				lcm=M+1;
				break;
			}
			lcm*=a;
		}
		G[mask]=(M/lcm)%mo;
	}
	
	
	H[1]=1;
	for(i=2;i<=N;i++) H[i]=mo-((i-1)*H[i-1])%mo;
	
	dp[0]=1;
	for(mask=1;mask<1<<N;mask++) {
		FOR(i,N) if(mask&(1<<i)) break;
		int sm=mask^(1<<i);
		for(int mask2=sm;mask2>=0;--mask2) {
			mask2&=sm;
			int mask3=mask2^(1<<i);
			(dp[mask]+=G[mask3]*H[__builtin_popcount(mask3)]%mo*dp[mask^mask3])%=mo;
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
	
}

まとめ

これをさっと書ける気はしないなぁ。