これ系の言い換え苦手。
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; }
まとめ
これをさっと書ける気はしないなぁ。