50分!求助!
查看原帖
50分!求助!
281499
Liar_Dancer楼主2021/7/29 14:41
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
typedef long long ll;
#define N 12
#define M 12
#define K 120
int n,m,k;
ll P[1<<M],sum[1<<M];
ll DP[N][1<<M][K];
int x,y,z,t;
int cnt;
int main(){
	scanf("%d%d",&n,&k);
	m=1<<n;
	for(int i=0;i<m;i++)
		if(!(i&(i<<1))&&!(i&(i>>1))){
			P[++cnt]=i;
			for(t=i;t;t>>=1)
				sum[cnt]+=t&1;
			DP[1][P[cnt]][sum[cnt]]=1;
		}
	for(int i=1;i<=n;i++)  
		for(int j=1;j<=cnt;j++)
			for(int a=1;a<=cnt;a++)
				if(!((P[j]&P[a])||(P[j]&(P[a]<<1))||(P[j]&(P[a]>>1))))
					for(int b=m;b>=sum[j];b--)
						DP[i][P[j]][b]+=DP[i-1][P[a]][b-sum[j]];
	ll sum=0;
	for(int j=1;j<=cnt;j++) 
		sum+=DP[n][P[j]][k];
	printf("%lld",sum);
	return 0;	
} 
2021/7/29 14:41
加载中...