CF1943D2 Counting Is Fun (Hard Version)

这是该问题的困难版本。两个版本的唯一区别在于 $ n $ 的约束条件。只有当两个版本的问题都被解决时，你才能进行 hack。 一个长度为 $ m $ 的非负整数数组 $ b $ 被称为“好”的，如果可以通过以下操作若干次（可能为零次）使得所有 $ b $ 的元素都变为 $ 0 $： - 选择两个不同的下标 $ l $ 和 $ r $（$ 1 \leq l < r \leq m $），并对所有满足 $ l \leq i \leq r $ 的 $ b_i $ 减去 $ 1 $。 给定两个正整数 $ n $、$ k $ 和一个质数 $ p $。 在所有长度为 $ n $ 的数组 $ a $ 中，满足 $ 0 \leq a_i \leq k $（$ 1 \leq i \leq n $），统计“好”数组的个数。 由于答案可能很大，你只需要输出答案对 $ p $ 取模的结果。

每组测试数据包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^3 $）——表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个正整数 $ n $、$ k $ 和 $ p $（$ 3 \leq n \leq 3000 $，$ 1 \leq k \leq n $，$ 10^8 < p < 10^9 $）——数组 $ a $ 的长度、$ a $ 元素的上界以及模数 $ p $。 保证所有测试用例中 $ n^2 $ 的和不超过 $ 10^7 $，且 $ p $ 是质数。

对于每个测试用例，输出一行，表示好数组的个数对 $ p $ 取模的结果。

在第一个测试用例中，$ 4 $ 个好数组 $ a $ 分别为： - $ [0,0,0] $； - $ [0,1,1] $； - $ [1,1,0] $； - $ [1,1,1] $。 由 ChatGPT 4.1 翻译