2 条题解

  • 1
    @ 2026-11-22 9:38:28
    # include <bits/stdc++.h>
    # define int long long
    using namespace std;
    const int N=1e3+5;
    const int INF=0x3f3f3f3f;
    int n,k,ans;
    int state[N],len;
    int num[N];
    int dp[10][1000][100];
    int getNum(int x){
    	int sum=0;
    	while(x){
    		sum++;
    		x-=(x&-x);
    	}
    	return sum;
    }
    void init(){
    	for(int i = 0;i<(1<<n);i++){
    		if(!(i&(i<<1))){
    			state[++len]=i;
    			num[len]=getNum(i);
    			dp[1][len][num[len]]=1;
    		}
    	} 
    }
    signed main(){
    	cin>>n>>k;
    	init();;
    	for(int i = 2;i<=n;i++){
    		for(int j = 1;j<=len;j++){
    			for(int l = 1;l<=len;l++){
    				int x=state[j],y=state[l];
    				if((x&y)||(x&(y<<1))||(x&(y>>1)))continue;
    				for(int z = 0;z<=k-num[j];z++){
    					dp[i][j][z+num[j]]+=dp[i-1][l][z];
    				}
    			}
    		}
    	}
    	for(int i = 1;i<=len;i++)
    		ans+=dp[n][i][k];
    	cout<<ans;
    	return 0; 
    }
    
    
    • 1
      @ 2026-7-19 15:43:51
      # include <bits/stdc++.h>
      # define int long long
      using namespace std;
      const int N=1e3+5;
      const int INF=0x3f3f3f3f;
      int n,k,ans;
      int state[N],len;
      int num[N];
      int dp[10][1000][100];
      int getNum(int x){
      	int sum=0;
      	while(x){
      		sum++;
      		x-=(x&-x);
      	}
      	return sum;
      }
      void init(){
      	for(int i = 0;i<(1<<n);i++){
      		if(!(i&(i<<1))){
      			state[++len]=i;
      			num[len]=getNum(i);
      			dp[1][len][num[len]]=1;
      		}
      	} 
      }
      signed main(){
      	cin>>n>>k;
      	init();;
      	for(int i = 2;i<=n;i++){
      		for(int j = 1;j<=len;j++){
      			for(int l = 1;l<=len;l++){
      				int x=state[j],y=state[l];
      				if((x&y)||(x&(y<<1))||(x&(y>>1)))continue;
      				for(int z = 0;z<=k-num[j];z++){
      					dp[i][j][z+num[j]]+=dp[i-1][l][z];
      				}
      			}
      		}
      	}
      	for(int i = 1;i<=len;i++)
      		ans+=dp[n][i][k];
      	cout<<ans;
      	return 0; 
      }
      
      • 1

      信息

      ID
      3576
      时间
      1000ms
      内存
      256MiB
      难度
      4
      标签
      (无)
      递交数
      21
      已通过
      15
      上传者