AcWing 1064. 小国王
原题链接
简单
作者:
最后五分钟
,
2024-03-26 22:56:17
,
所有人可见
,
阅读 6
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=110,M=1<<10;
typedef pair<int,int> PII;
int f[N][M][110];
int check(int a,int b)
{
if(a&b||a<<1&b||a&b<<1)return 0;
return 1;
}
int cul(int x)
{
int res=0;
while(x)
{
x-=x&-x;
res++;
}
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
f[0][0][0]=1;
for(int i=1;i<=n;i++)
{
for(int a=0;a<1<<n;a++)
{
for(int b=0;b<1<<n;b++)
{
if(!check(a,b))continue;
if(b&b<<1)continue;
int t=cul(b);
for(int s=t;s<=k;s++)
f[i][b][s]+=f[i-1][a][s-t];
}
}
}
int res=0;
for(int a=0;a<1<<n;a++)res+=f[n][a][k];
cout<<res<<endl;
return 0;
}