CSAcademy Round #31 : F. Tokens on a grid

本番TLEがとれず…。
https://csacademy.com/contest/round-31/task/token-grid/

問題

N*Mのグリッドがある。
各マスは空であるか、アルファベットが埋まっている。
いくつかのマスのアルファベットを消し、以下の条件を満たすようにしたい。

• 各列は1種類までしかアルファベットを含まない。
• 全列が空である行がちょうどK行ある。

K=0～Nに対し、条件を満たすアルファベットの消し方の組み合わせ数を求めよ。

解法

O(2^N*(N+M))解法もあるようだが、ここではO(2^N*N*M)解法を紹介。
この場合、かなり定数倍最適化を頑張らないと通らない。

まず、各列において以下を求める。
f(c,x) := c列目のうち文字xが配置された列のbitmask
さらに以下を考えよう。
g(c,mask) := c列目のうちmaskに示す列のアルファベットを残したとき、1つ目の条件に合致するか否か
このg(c,mask)はmaskがf(c,x)のsubsetならTrueになるので、高速ゼータ変換の要領で求めることができる。

各列の結果をまとめよう。
h(mask) := 全列でmaskのsubsetにあたる範囲の列のアルファベットを残した場合の組み合わせ
これは各列でmaskのsubsetをsubmaskとしたとき、で計算できる。
この総和の計算は再度高速ゼータ変換で行おう。

h(mask)はbitcount(mask)個以下の列がアルファベットを含んでいるが、ちょうどbitcount(mask)個だけとは限らない。
そこは包除原理の要領でh(submask)の分を引いていけばよい。

int H,W;
string S[1010];
int ok[1<<16];
ll mo=1000000007;
int from[1<<16];
ll dpdp[1<<16];
ll dp[20];

inline int mulmod(int a,int b,int mo) {
	int d,r;
	if(a==0 || b==0) return 0;
	if(a==1 || b==1) return max(a,b);
	__asm__("mull %4;"
	        "divl %2"
		: "=d" (r), "=a" (d)
		: "r" (mo), "a" (a), "d" (b));
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(x,1<<H) from[x]=1;
	int mask;
	FOR(x,W) {
		ZERO(ok);
		int m[26]={};
		FOR(y,H) if(S[y][x]!='.') m[S[y][x]-'a'] |= 1<<y;
		FOR(y,26) for(i=m[y];i>=0;i--) i&=m[y], ok[i]=1;
		FOR(y,H) {
			mask=1<<y;
			for(i=mask;i<1<<H;i=(i+1)|mask) ok[i] += ok[i^mask];
		}
		FOR(mask,1<<H) from[mask]=mulmod(from[mask],ok[mask],(int)mo);
	}
	
	FOR(i,1<<H) {
		ll ret=from[i];
		for(j=i-1; j>=0; j--) j&=i, ret-=from[j];
		from[i]=(ret%mo+mo)%mo;
		(dp[H-__builtin_popcount(i)]+=from[i])%=mo;
	}
	FOR(x,H+1) _P("%lld%c",dp[x],(x==H)?'\n':' ');
}

まとめ

インラインアセンブラでゴリ押し。