Untitled
unknown
plain_text
4 years ago
1.3 kB
7
Indexable
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e5+10;
//#define cout fout
//ofstream fout("ans.txt");
int dp[11][101][1500];
std::vector<int> v;
bool check(int mask,int mask2)
{
mask|=((mask<<1)|(mask>>1));
if(mask&mask2)
return false;
return true;
}
void solve(int n,int k)
{
for(int j=1;j<=n;j++)
for(int d=0;d<=k;d++)
for(auto mask:v)
if(mask<(1<<n) && d>=__builtin_popcount(mask))
for(auto mask2:v)
if(mask2<(1<<n) && check(mask,mask2))
dp[j][d][mask]+=dp[j-1][d-__builtin_popcount(mask)][mask2];
}
int sum(int n,int k)
{
int ret=0;
for(int mask=0;mask<(1<<n);mask++){
// if(n==2 && k==1)
// cout<<"debug "<<mask<<" "<<dp[n][k][mask]<<" "<<dp[1][0][0]<<endl;
ret+=dp[n][k][mask];
}
return ret;
}
int32_t main()
{
for(int mask=0;mask<(1<<10);mask++)
if((mask&(mask<<1))==0)
v.push_back(mask);
int n,k;
cin>>n>>k;
for(int i=0;i<=10;i++)
for(int d=0;d<=100;d++)
for(int mask=0;mask<=1024;mask++)
dp[i][d][mask]=0;
dp[0][0][0]=1;
if(n%2==0)
solve(n,n*n/4);
else
solve(n,(n+1)*(n+1)/4);
//cout<<sum(1,2)<<endl;
// cout<<"{";
// for(int k=0;k<=100;k++)
// cout<<sum(n,k)<<" ,"[k<100];
// cout<<"},";
//cout<<endl;
cout<<sum(n,k)<<endl;
}
/*
a[10][10]={{},{},,,}*/Editor is loading...