311165: CF1943D2. Counting Is Fun (Hard Version)
Description
This is the hard version of the problem. The only difference between the two versions is the constraint on $n$. You can make hacks only if both versions of the problem are solved.
An array $b$ of $m$ non-negative integers is said to be good if all the elements of $b$ can be made equal to $0$ using the following operation some (possibly, zero) times:
- Select two distinct indices $l$ and $r$ ($1 \leq l \color{red}{<} r \leq m$) and subtract $1$ from all $b_i$ such that $l \leq i \leq r$.
You are given two positive integers $n$, $k$ and a prime number $p$.
Over all $(k+1)^n$ arrays of length $n$ such that $0 \leq a_i \leq k$ for all $1 \leq i \leq n$, count the number of good arrays.
Since the number might be too large, you are only required to find it modulo $p$.
InputEach test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains three positive integers $n$, $k$ and $p$ ($3 \leq n \leq 3000$, $1 \leq k \leq n$, $10^8 < p < 10^9$) — the length of the array $a$, the upper bound on the elements of $a$ and modulus $p$.
It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^7$, and $p$ is prime.
OutputFor each test case, on a new line, output the number of good arrays modulo $p$.
ExampleInput4 3 1 998244853 4 1 998244353 3 2 998244353 343 343 998244353Output
4 7 10 456615865Note
In the first test case, the $4$ good arrays $a$ are:
- $[0,0,0]$;
- $[0,1,1]$;
- $[1,1,0]$;
- $[1,1,1]$.
Output
这是一个难题的较难版本。两个版本之间唯一的不同是关于 n 的限制。只有当问题的两个版本都被解决时，你才能进行黑客攻击。
定义一个由 m 个非负整数组成的数组 b 是“好的”，如果 b 的所有元素可以通过以下操作（可能零次）变为 0：
选择两个不同的索引 l 和 r (1 ≤ l < r ≤ m) 并将所有满足 l ≤ i ≤ r 的 b_i 减 1。
给你两个正整数 n、k 和一个素数 p。
在所有 (k+1)^n 个长度为 n 的数组中，使得 0 ≤ a_i ≤ k 对所有 1 ≤ i ≤ n，计算“好的”数组数量。
由于这个数字可能太大，你只需要找到它模 p 的结果。
输入输出数据格式：
输入：
每个测试包含多个测试用例。第一行包含一个整数 t (1 ≤ t ≤ 10^3) —— 测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含三个正整数 n、k 和 p (3 ≤ n ≤ 3000, 1 ≤ k ≤ n, 10^8 < p < 10^9) —— 数组 a 的长度、数组元素的上下界和模数 p。
保证所有测试用例的 n^2 之和不超过 10^7，且 p 是素数。
输出：
对于每个测试用例，输出一行，表示“好的”数组数量模 p 的结果。
示例：
输入：
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353
输出：
4
7
10
456615865
注意：
在第一个测试用例中，4 个“好的”数组 a 是：
[0,0,0];
[0,1,1];
[1,1,0];
[1,1,1]。题目大意： 这是一个难题的较难版本。两个版本之间唯一的不同是关于 n 的限制。只有当问题的两个版本都被解决时，你才能进行黑客攻击。 定义一个由 m 个非负整数组成的数组 b 是“好的”，如果 b 的所有元素可以通过以下操作（可能零次）变为 0： 选择两个不同的索引 l 和 r (1 ≤ l < r ≤ m) 并将所有满足 l ≤ i ≤ r 的 b_i 减 1。 给你两个正整数 n、k 和一个素数 p。 在所有 (k+1)^n 个长度为 n 的数组中，使得 0 ≤ a_i ≤ k 对所有 1 ≤ i ≤ n，计算“好的”数组数量。 由于这个数字可能太大，你只需要找到它模 p 的结果。 输入输出数据格式： 输入： 每个测试包含多个测试用例。第一行包含一个整数 t (1 ≤ t ≤ 10^3) —— 测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含三个正整数 n、k 和 p (3 ≤ n ≤ 3000, 1 ≤ k ≤ n, 10^8 < p < 10^9) —— 数组 a 的长度、数组元素的上下界和模数 p。 保证所有测试用例的 n^2 之和不超过 10^7，且 p 是素数。 输出： 对于每个测试用例，输出一行，表示“好的”数组数量模 p 的结果。 示例： 输入： 4 3 1 998244853 4 1 998244353 3 2 998244353 343 343 998244353 输出： 4 7 10 456615865 注意： 在第一个测试用例中，4 个“好的”数组 a 是： [0,0,0]; [0,1,1]; [1,1,0]; [1,1,1]。