1 good子序列的性质挖掘
1.1
对一个序列\(\{b_i\}\)，每个元素\(b_i\)对应一个等差数列\(\{x,x+1,x+2,...,x+b_i-1\}\)，很显然该数列由首项\(x\)唯一确定，其和为\(xb_i+\frac{b_i(b_i-1)}{2}\)
因此good序列满足\(\sum\limits_{i=1}^n xb_i+\frac{b_i(b_i-1)}{2}=0\)，即\(\sum\limits_{i=1}^nx_ib_i=\sum\limits_{i=1}^n\frac{b_i(1-b_i)}{2}\)。
如何判断一个序列是不是good？根据上述推导，一个序列good等价于该关于\(x_1,x_2,...,x_n\)的一次方程存在一组整数解。
根据裴蜀定理，该方程有整数解等价于\(gcd(b_1,b_2,...,b_n) | \sum\limits_{i=1}^n\frac{b_i(b_i-1)}{2}\)。这就是判断一个序列是否为good的充要条件。
以上都是很普通的数学推导。
1.2
记\(f(a)=\frac{a(a-1)}{2}\)。
注意到如下事实：当\(a\)为奇数时，\(f(a)=\frac{a-1}{2}\cdot a\)，此时\(a\mid f(a)\)，因此\(f(a)\% gcd(a,.,.,...)=0\).换句话说，当一个\(a\)为奇数时，它在式\(\sum\limits_{i=1}^n\frac{a_i(a_i-1)}{2}\% gcd(a_1,a_2,...,a_n)\)（记为式X）中对和式\(\sum\limits_{i=1}^n\frac{a_i(a_i-1)}{2}\)的贡献为0，即无任何影响，而偶数情况则比较复杂。接下来我们抛开奇数的情况。
进一步地，我们知道任意整数\(a\)都能表示成\(2^b\cdot c\)的形式，其中\(b\)为非负整数，\(c\)为奇整数。因为上面我们抛开了奇数的情况，此时\(b\)总是正整数。此时\(gcd(a_1,a_2,...,a_n)=2^{min\{b_1,b_2,...,b_n\}}\cdot gcd(c_1,c_2,...,c_n)\)。因此式X可以表示为\(\sum\limits_{i=1}^n\frac{2^{b_i}c_i(2^{b_i}c_i-1)}{2}\% 2^{min\{b\}}\cdot gcd\{c\}\)。
1.3
单独拿出式X的每一项来看，每一项可以写成\(2^{b_i-1}c_i(2^{b_i}c_i-1)\% 2^{min\{b\}}\cdot gcd\{c\}\)。显然，当\(b_i-1\geq min\{b\}\)时，该式恒为0。
剩下的只有\(b_i=min\{b\}\)的情况了，这时为\(2^{b_i-1}\cdot c_i(2^{b_i}c_i-1)\% 2^{b_i}\cdot gcd\{c\}\)。
抽象一下这个：设\(a\)为正整数，\(b,c\)为正奇数且\(c\mid b\)，则该式为\(b\cdot 2^{a-1}\% c\cdot2^{a}\)。
通过观察（找规律），我们可以发现有\(b\cdot 2^{a-1}\% c\cdot2^{a}=c\cdot 2^{a-1}\)恒成立。接下来我们尝试证明它：
等价于证明\(b\cdot 2^{a-1}\equiv c\cdot 2^{a-1}(\mod c\cdot2^a)\)。设\(b=x\cdot c\)，即证\(x\cdot c\cdot 2^{a-1}\equiv c\cdot 2^{a-1}(\mod c\cdot 2^a)\)。其中\(x\)为正奇数。
还是不够明显，再抽象一下：设\(y=c\cdot 2^{a-1}\)（1.2节提到任意整数\(a\)都能表示成\(2^b\cdot c\)的形式，这反过来也是正确的，即\(a\)与\((b,c)\)构成的这一映射为一一映射，这条定理保证这一设的合理性），即证\(x\cdot y\equiv y(\mod 2y)\)。对正奇数\(x\)，归纳法易证其正确性。
证明完毕之后，我们就知道了当\(b_i=min\{b\}\)时，设模数为\(m\)，该项对和式的贡献为\(\frac{m}{2}\)，也就是说每两个满足\(b_i=min\{b\}\)的项加起来就为0。
以上推导足够我们完成这题了。
2 如何计good子序列数
很显然，枚举\(min\{b\}\)即可，选取的方案要保证：
- 存在\(b_i=min\{b\}\)的项，且项数为偶数；
- 其他项的\(b_i\)需大于\(min\{b\}\)。
注意考虑奇数的情况：\(min\{b\}=0\)时无需保证项数为偶数。