90pts求调
查看原帖
90pts求调
573963
wbh20090611楼主2024/8/28 15:27

rt

#include <bits/stdc++.h>
#define int long long
#define lowbit(i) (i & -i)
using namespace std;
const int N = (1 << 12) + 10;
int n, m, dp[12][12][N], k;
int count(int a)
{
	int cnt = 0;
	while(a > 0)
		a -= lowbit(a), cnt++;
	return cnt;
}
signed main()
{
	cin >> n >> k;
	m = n;
	dp[0][0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int x = 0; x < (1 << m); x++)
		{
			if (((x << 1) & x) || ((x >> 1) & x))
				continue;
			for (int y = 0; y < (1 << m); y++)
			{
				if (((y << 1) & y) || ((y >> 1) & y))
					continue;
				if ((y & x) || ((y << 1) & x) || (y & (x << 1)))
					continue;
				int l = count(y);
				for (int j = 0; j <= k - l; j++)
					dp[i][j + l][y] += dp[i - 1][j][x];
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < (1 << m); i++)
		ans += dp[n][k][i];
	cout << ans;
}
2024/8/28 15:27
加载中...