AcWing 1064. 小国王
原题链接
简单
作者:
leimingze
,
2022-02-22 15:25:15
,
所有人可见
,
阅读 115
//author:leimingze
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define _ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define LL long long
#define ULL unsigned unsigned
#define PII pair<int,int>
#define MOD 1e9+7
#define INF 0x3f3f3f3f
#define eps 1e-8
const double PI = acos(-1.0);
const int dx4[4] = { 0,-1,0,1 };
const int dy4[4] = { -1,0,1,0 };
//#pragma warning(disable:4786)//使命名长度不受限制
//#pragma comment(linker, "/STACK:102400000,102400000")//手工开栈
int qmi(int a, int k, int p) { int res = 1 % p; while (k) { if (k & 1)res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; }return res; }
template <typename T> void inline read(T& x)
{
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
//不开long long 见祖宗,递归剪枝
const int N = 12, M = 1 << N, C = N * N;
int n, m, k;
LL f[N][C][M];
int cnt[M];
vector<int>v1;
vector<int>v2[M];
bool check(int state)
{
return !(state & state >> 1);
}
int count(int state)
{
int res = 0;
for (int i = 0; i < n; i++)res += state >> i & 1;
return res;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < 1 << n; i++)
{
if (check(i))
{
v1.push_back(i);
cnt[i] = count(i);
}
}
m = v1.size();
for (auto x : v1)
for (auto y : v1)
if (!(x & y) && check(x | y))
v2[x].push_back(y);
f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i++)
for (int j = 0; j <= k; j++)
for (auto x : v1)
for (auto y : v2[x])
if(j - cnt[x] >= 0)
f[i][j][x] += f[i - 1][j - cnt[x]][y];
cout << f[n + 1][k][0] << endl;
return 0;
}