TopCoderOpen 2022 Wildcard : Hard CommitteeContinuity

こっちはきっちり解き切れてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=17763

問題

M人のメンバーがいる。
これらのメンバーに対し、Y回メンバーの部分集合を作る。
以下の条件を満たす、部分集合の作り方は何通りか。

• ある回次の部分集合に、あるメンバーが含まれる、という条件がいくつか与えられる。その条件を満たす部分集合である。
  • なお、この条件群に登場するメンバー数(=K)は最大10名である。
• 連続する回次の部分集合には、最低1人は共通して含まれるメンバーがいる。

解法

dp(n,mask,num) := n回目までの回次に対し条件を満たすよう部分集合を作ったとき、n回目に含まれる、条件群に登場するメンバーの有無はmaskであり、その他のメンバーのうち部分集合に含まれる人数がnum人であるような組み合わせの数
として、dp(n,*,*)からdp(n+1,*,*)への遷移を考える。

まず、不可な条件を無視するとdp(n+1,mask,num) = sum(dp(n,*,*))となる。
ここから条件に反するものを取り除こう。

• まず、n+1回目の回次に対し、含まれるべきメンバーが含まれていないようなmaskに対してはdp(n+1,mask,dp)=0で上書きする。
• もしmaskとmask'が共通部分を持たない場合、dp(n,mask,num)からdp(n+1,mask',num')への計上分は、num人とnum'人が共通部分を持たないケースの部分減算する。

後者について、maskとmask'を総当たりするとO(Y*(4^K)*M^2)かかりTLEする。
bitmaskの部分集合を取るテクでO(Y*(3^K)*M^2)にしても通るようだが、以下のコードは高速ゼータ変換を使いO(Y*K*(2^K)*M^2)にして通している。

int YM[55];
ll from[1<<10][55];
ll to[1<<10][55];
const ll mo=1000000007;

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

class CommitteeContinuity {
	public:
	int count(int M, int Y, vector <int> year, vector <int> member) {
		map<int,int> A;
		ZERO(from);
		ZERO(YM);
		int nex=0;
		int i;
		FOR(i,year.size()) {
			int m=member[i];
			if(A.count(m)==0) {
				A[m]=nex++;
			}
			YM[year[i]]|=1<<A[m];
		}
		int lef=M-nex;
		int mask;
		FOR(mask,1<<nex) if((mask&YM[0])==YM[0]) {
			FOR(i,lef+1) from[mask][i]=comb(lef,i);
		}
		from[0][0]=0;
		int yy;
		for(yy=1;yy<Y;yy++) {
			ZERO(to);
			ll sum=0;
			FOR(mask,1<<nex) FOR(i,lef+1) sum+=from[mask][i];
			sum%=mo;
			FOR(mask,1<<nex) FOR(i,lef+1) to[mask][i]=sum*comb(lef,i)%mo;
			
			int x,y;
			FOR(x,lef+1) {
				ll A[1<<10]={};
				FOR(mask,1<<nex) A[mask]=from[mask][x];
				FOR(y,nex) FOR(mask,1<<nex) if(mask&(1<<y)) (A[mask]+=A[mask^(1<<y)])%=mo;
				for(y=0;x+y<=lef;y++) {
					ll p=comb(lef-x,y);
					FOR(mask,1<<nex) (to[mask][y]+=mo-p*A[(1<<nex)-1-mask]%mo)%=mo;
				}
			}
			
			
			FOR(mask,1<<nex) if((mask&YM[yy])!=YM[yy]) {
				FOR(i,lef+1) to[mask][i]=0;
			}
			
			swap(from,to);
		}
		ll sum=0;
		FOR(mask,1<<nex) FOR(i,lef+1) sum+=from[mask][i];
		return sum%mo;
	}
}

まとめ

これはすんなり通せてよかったね。