Untitled
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...