在下面的代码中，按照我们所容斥的：$a_{i-1}>a_{i-2}+a_i$。那么转移方程式中 $\max\{a_{i-2}\}$ 就应该是 $(k-a_i-1)$。

但是改成 $(k-x)$ 却过了，why。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3 + 5;
int n, k, p, ans, dp[3][2][N];
int pres[3][2][N], prei[3][2][N]; 
int g3(int x) { return (x % 3 + 3) % 3; }
int g2(int x) { return (x % 2 + 2) % 2; }
void solve() {
	memset(dp, 0, sizeof dp); memset(pres, 0, sizeof pres); memset(prei, 0, sizeof prei);
	cin >> n >> k >> p; dp[0][0][0] = 1;
	for(int i = 1;i <= n + 1; ++i) {
		memset(dp[g3(i)], 0, sizeof dp[g3(i)]); memset(pres[g3(i)], 0, sizeof pres[g3(i)]);
		memset(prei[g3(i)], 0, sizeof prei[g3(i)]);
		for(int j = 0;j <= 1; ++j) {
			pres[g3(i - 1)][j][0] = dp[g3(i - 1)][j][0];
			for(int X = 1;X <= k; ++X) 
				pres[g3(i - 1)][j][X] = (dp[g3(i - 1)][j][X] + pres[g3(i - 1)][j][X - 1]) % p, 
			prei[g3(i - 1)][j][X] = (dp[g3(i - 1)][j][X] * X % p + prei[g3(i - 1)][j][X - 1]) % p; 
		}
			
		for(int j = 0;j <= 1; ++j) {
			for(int X = 0;X <= k; ++X) {
				int Ymax = k - X; // Z > X + Y, choose k - X - 1 - Y 个 
				dp[g3(i)][j][X] = pres[g3(i - 1)][j][k];
				if(Ymax < 0 or i == 1) continue ;
				int dp1 = Ymax * pres[g3(i - 2)][g2(j - 1)][Ymax] % p;
				dp[g3(i)][j][X] = (dp[g3(i)][j][X] + dp1) % p;
				dp[g3(i)][j][X] = (dp[g3(i)][j][X] - prei[g3(i - 2)][g2(j - 1)][Ymax]) % p;
			} 
		}
	} 
	ans = (dp[g3(n + 1)][0][0] - dp[g3(n + 1)][1][0]) % p; // 求 f(0) 
	cout << (ans + p) % p << "\n";
}
/*
num 表示至少有几个不满足   则 X+Y<=nowchoose 
dp[i&1][num&1][X] = \sum dp[i-1&1][num-1&1][Y] * (k - X - 1 - Y)
维护 sum dp[i][num] 
，以及 sum dp[i][num]*i 即可 
*/
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}
/*
满足 :  a[i] >= a[i - 1] - a[i - 2] 
*/