bzoj2560 진주 서브집합 dp

비록 내가 이렇게 약하지만 이런 sb문제를 푸는 것은 여전히 문제없다...아침 내내 물 흘렸어.
f[i]로 집합이 i일 때의 방안 수를 표시하고 전체 집합에서 비합법적인 것을 빼면 된다.비합법적이라면 하나의 정점으로 열거할 수 있다.시간 복잡도 O(3^N+N^2·2^N).
AC 코드는 다음과 같습니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define mod 1000000007
using namespace std;

int n,bin[25],f[1<<16],g[1<<16],a[25][25];
int main(){
	scanf("%d",&n); int i,j,k;
	bin[0]=1; for (i=1; i<=n; i++) bin[i]=bin[i-1]<<1;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++) scanf("%d",&a[i][j]);
	for (k=1; k<bin[n]; k++){
		f[k]=1;
		for (i=1; i<=n; i++) if (k&bin[i-1])
			for (j=1; j<i; j++) if (k&bin[j-1])
				f[k]=(ll)f[k]*(a[i][j]+1)%mod;
		g[k]=f[k]; i=k^(k&-k);
		for (j=i; j; j=(j-1)&i) f[k]=(f[k]-(ll)g[j]*f[k^j]%mod+mod)%mod;
	}
	printf("%d
",f[bin[n]-1]);
	return 0;
}

by lych
2016.4.16