P1896 [SCOI2005] 互不侵犯

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
ll dp[21][1 << 10 + 1][101],ans;
int dpbitcnt[1 << 10 + 10];
int bitcnt(int x) { //x中的1个数(记忆化) 
	if (dpbitcnt[x]) return dpbitcnt[x];
	while (x) {
		x &= (x - 1);
		++ dpbitcnt[x];
	}
	return dpbitcnt[x];
}
int main() {
	scanf("%d%d",&n,&k);
	for (int S = 0;S < (1 << n);S ++)
		if (!(S & (S << 1))) dp[1][S][bitcnt(S)] = 1;
	for (int i = 2;i <= n;i ++)
		for (int S = 0;S < (1 << n);S ++)
			if (!(S & (S << 1)))
				for (int T = 0;T < (1 << n);T ++)
					if ((!(T & (T << 1))) && (!(S & T)) && (!((S << 1) & T)) && (!(S & (T << 1)))) {
						int cnt = bitcnt(S);
						for (int l = cnt;l <= k;l ++)
							dp[i][S][l] += dp[i - 1][T][l - cnt];
					}
	for (int S = 0;S < (1 << n);S ++)
		ans += dp[n][S][k];
	printf("%llu\n",ans);
	return 0;
}