思路应该没问题啊,求调!!qwq
查看原帖
思路应该没问题啊,求调!!qwq
1014583
封禁用户楼主2024/10/9 19:03
#include<bits/stdc++.h>
#define int long long
#define MOD 998224353
#define N 505
using namespace std;
int n,k,to;
int c[75][2],f[25],se[25],d[75][505];
void bebebe(int x){
	int u = 0;
	for (int i = k - 1; i >= 0; i--){
		if (!c[u][x >> i & 1]) c[u][x >> i & 1] = to++;
		u = c[u][x >> i & 1];
	}
	se[u] = 1;
}
void dp(){
	queue<int> q;
	if (c[0][0]) f[c[0][0]] = 0, q.push(c[0][0]);
	if (c[0][1]) f[c[0][1]] = 0, q.push(c[0][1]);
	while (!q.empty()){
		int u = q.front();
		q.pop();
		if (c[u][0]){
			f[c[u][0]] = c[f[u]][0];
			se[c[u][0]] |= se[c[f[u]][0]];
			q.push(c[u][0]);
		}else c[u][0] = c[f[u]][0];
		if (c[u][1]){
			f[c[u][1]] = c[f[u]][1];
			se[c[u][1]] |= se[c[f[u]][1]];
			q.push(c[u][1]);
		} else c[u][1] = c[f[u]][1];
	}
}
signed main(){
	scanf("%d%d", &n, &k);
	int cnt = 0;
	for(int t=0;t<=((1 << (1 << k)) - 1);t++){//	F(t, 0, (1 << (1 << k)) - 1)
		to = 0;
		memset(c, 0, sizeof(c));
		memset(se, 0, sizeof(se));
		memset(f, 0, sizeof(f));
		for(int i=0;i<=((1<<k)-1);i++){//F(i, 0, (1 << k) - 1){
			if (!(1 << i & t)){
				bebebe(i);
			}
		}
		dp();
		int u = 0, flag = 0;
		for(int i=0;i<=((1<<k)-1);i++){
			u = c[u][t >> i & 1];
			if (se[u]){
				flag = 1; 
				break;
			}
		}
		if (flag) continue;
		memset(d, 0, sizeof(d));
		d[u][0] = 1;
		for(int i=1;i<=n-(1<<k);i++){//F(i, 1, n - (1 << k))
			for(int a=0;a<=to;a++){//F(a, 0, to)
				if (!se[c[a][0]]) d[c[a][0]][i] = (d[c[a][0]][i] + d[a][i - 1]) % MOD;
				if (!se[c[a][1]]) d[c[a][1]][i] = (d[c[a][1]][i] + d[a][i - 1]) % MOD;
			}
		}
		for(int a=0;a<=to;a++) cnt = (cnt + d[a][n - (1 << k)]) % MOD;
	}
	cout<<cnt;
	return 0;
}
2024/10/9 19:03
加载中...