10分求调!!!
查看原帖
10分求调!!!
1191361
daixihan楼主2025/7/31 18:56
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e3+5;
ll n,m,cnt,sta[N],dp[15][N][105],num[N];
void dfs(int x,int sum,int cur){
	if(cur>=n){
		sta[++cnt]=x;
		num[cnt]=sum;
		return ;
	}
	dfs(x,sum,cur+1);
	dfs(x|(1<<cur),sum+1,cur+2);
}
bool check(int a,int b){
	if(sta[a]&sta[b]) return 0;
	if((sta[a]<<1)&sta[b]) return 0;
	if(sta[a]&(sta[b]>>1)) return 0;
	return 1;
}
int main(){
	cin>>n>>m;
	dfs(0,0,0);
	for(int x=1;x<=cnt;x++){
		dp[1][x][num[x]]=1;
	}
	for(int i=2;i<=n;i++){
		for(int x=1;x<=cnt;x++){
			for(int y=1;y<=cnt;y++){
				if(!check(x,y)) continue;
				for(int k=num[x];k<=m;k++){
					dp[i][x][k]+=dp[i-1][y][k-num[x]];
				}
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=cnt;i++){
		ans+=dp[n][i][m];
	}
	cout<<ans;
	return 0;
}

2025/7/31 18:56
加载中...