CF773F Test Data Generation 做题记录

生成测试数据并非简单的任务！生成大的随机数据通常不能够完全保证解法的正确性。

举个例子，考虑以前 Codeforces round 的一道题。它的输入格式如下：

第一行是一个整数 $n(1\leq n \leq max_n)$ 表示集合的大小，第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\dots,a_n(1\leq a_i\leq max_a)$ 表示集合中的元素，升序排列。

如果你不注意题目的解法，看起来生成一个好的测试数据是非常容易的。令 $n=max_n$，从 $1\sim max_a$ 中生成 $n$ 个不相同的数，并排序。但是马上你就会知道这不那么简单。

下面是这道题目的真实解法。令 $g$ 为 $a_1,a_2,\dots,a_n$ 的最大公约数，令 $x=a_n/g-n$，如果 $x$ 是奇数输出 Alice，如果 $x$ 是偶数输出 Bob

考虑这道题两个错误的解法，它们与正解只在计算 $x$ 中不同。

第一个解法令 $x = a_n/g$ （不减去 $n$）

第二个解法令 $x=a_n-n$（不除以 $g$）

如果一个测试数据令这两个解法都输出错误的答案，称这个数据是有趣的。

给定 $max_n, max_a, q$ 求满足限制且有趣的测试数据的数量对 $q$ 取模的结果。

$1\leq max_n\leq 30000, max_n\leq max_a\leq 10^9, 10^4\leq q\leq 10^5+129$

多项式和最大公因数又有什么关系呢？

哦，目标显然是让 $n$ 为奇数且 $g$ 包含了 $a_n$ 的所有因子 $2$，并且 $a_n$ 是偶数。

那么可以枚举 $g$ 的因子 $2$ 的个数，假设 $g$ 有 $k$ 个因子 $2$，问题就变为求 $a_i\le \left\lfloor\dfrac{max_a}{2^k}\right\rfloor$，$n$ 为奇数且 $a_n$ 为奇数的方案数。

设 $f_{i,j}$ 表示 $n=j$，$a$ 的取值范围为 $[1,i]$ 且 $a_j$ 为偶数的方案数；$g_{i,j}$ 表示 $n=j$，$a$ 的取值范围为 $[1,i]$ 且 $a_j$ 为奇数的方案数。那么我们只要求出 $f$ 的转移方法就能类似地推出 $g$ 的转移方法了。

显然有转移：

$f_{i,j}=f_{i-1,j}+[i\operatorname{mod}2=0](f_{i-1,j-1}+g_{i-1,j-1})$

意思是，我们可以让 $a_j<i$ 或者让 $a_j=i$。

然后换一种转移方式，考虑从取值范围 $[1,x]$ 和取值范围 $[1,y]$ 转移到取值范围 $[1,x+y]$：

$f_{x+y,i}=\sum\limits_{j=0}^{i-1}(f_{x,j}+g_{x,j})([x\operatorname{mod}2=0]f_{y,i-j}+[x\operatorname{mod}2=1]g_{y,i-j})$

意思是，前 $j$ 个数满足 $1\le a_i\le x$，后 $i-j$ 个数满足 $x+1\le a_i\le x+y$ 且最后一个数是偶数。

边界条件是 $f_{1,1}=0$。

总结一下：

$\begin{cases}f_{1,1}=0\\f_{i,j}=f_{i-1,j}+[i\operatorname{mod}2=0](f_{i-1,j-1}+g_{i-1,j-1}+[j=1])\\f_{2i,j}=f_{i,j}+\sum\limits_{k=0}^{j-1}(f_{i,k}+g_{i,k})([i\operatorname{mod}2=0]f_{i,j-k}+[i\operatorname{mod}2=1]g_{i,j-k})\end{cases}$

类似地：

$\begin{cases}g_{1,1}=1\\g_{i,j}=g_{i-1,j}+[i\operatorname{mod}2=1](f_{i-1,j-1}+g_{i-1,j-1}+[j=1])\\g_{2i,j}=g_{i,j}+\sum\limits_{k=0}^{j-1}(f_{i,k}+g_{i,k})([i\operatorname{mod}2=1]f_{i,j-k}+[i\operatorname{mod}2=0]g_{i,j-k})\end{cases}$

然后就可以倍增地边求 $f$ 边求 $g$，求出答案了。