Untitled

 avatar
unknown
plain_text
3 years ago
1.3 kB
3
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...