状压:二进制状压
注意范围,n一般在60以内,大了会爆LL,其实一般在10~20
n在30以内可以用状压和搜索,30~50一般是折半搜索和状压,60一般是状压
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1030;
int n,m,k,cnt;
int st[N],num[N];
void dfs(int w,int s,int step){
if(step>=n){
st[++cnt]=w;
num[cnt]=s;
return ;
}
dfs(w,s,step+1);
dfs(w+(1<<step),s+1,step+2);
}
ll f[12][N][90];
int main(){
cin >> n >> m;
dfs(0,0,0);
for(int i=1;i<=cnt;++i) f[1][i][num[i]]=1;
for(int i=2;i<=n;++i){
for(int j=1;j<=cnt;++j){
for(int k=1;k<=cnt;++k){
if(st[j]&st[k]) continue;
if((st[j]>>1)&st[k]) continue;
if((st[j]<<1)&st[k]) continue;
for(int s=num[j];s<=m;++s) f[i][j][s]+=f[i-1][k][s-num[j]];
}
}
}
ll ans=0;
for(int i=1;i<=cnt;++i) ans+=f[n][i][m];
cout << ans;
return 0;
}

京公网安备 11010502036488号