题目：求有多少个长度为 n 且任意相邻两个数的最大公约数都不为 k 的排列？

#include <bits/stdc++.h>
using namespace std;
const int N = 3005, M = (1 << 10) + 1, mod = 998244353;
int n, k, m;
int f[N][M][11],cont[N];
int dfs(int t, int l, int g) {
	if (f[t][g][l] != -1) return f[t][g][l];
	if (t == 0) return f[t][g][l] = 1;
	if (!g) {
		int ans = 1;
		for(int i=2;i<=t;i++) ans = (1ll * ans * i) % mod;
		return f[t][g][l] = ans;
	}
	int res = 0;
	if (t - cont[g] > 0) res = (1ll * (t - cont[g]) * dfs(t - 1, 0, g)) % mod;
	if (g) {
		int x = g;
		while (x) {
			int y = log2(x & -x) + 1;
			if (l == 0 || __gcd(l, y) != 1)
				res = (res + dfs(t - 1, y, g ^ (x & -x))) % mod;
			x -= x & -x;
		}
	}
	return f[t][g][l] = res;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	freopen("permutation.in", "r", stdin);
	freopen("permutation.out", "w", stdout);
	cin >> n >> k;
	m = n / k;
	int l = (1 << m) - 1;
	for(int i=1;i<=l+1;i++) cont[i]=cont[i-(i&-i)]+1;
	memset(f, 0xff, sizeof f);
	cout << dfs(n, 0, l);
	return 0;
}