#P3773. [CTSC2017] 吉夫特

    ID: 1009 远端评测题 2000ms 489MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2017WC/CTSC/集训队递归O2优化枚举暴力进制组合数学

[CTSC2017] 吉夫特

题目描述

简单的题目,既是礼物,也是毒药。

B 君设计了一道简单的题目,准备作为 gift 送给大家。

输入一个长度为 nn 的数列 a1,a2,,ana_1, a_2, \cdots , a_n 问有多少个长度大于等于 22 的不上升的子序列满足:

$$\prod _{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \mod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \binom{a_{b_{k-1}}}{a_{b_k}} \mod 2 > 0 $$

输出这个个数对 10000000071000000007 取模的结果。

G 君看到题目后,为大家解释了一些基本概念。

我们选择任意多个整数 bib_i 满足

1b1<b2<<bk1<bkn1 \leq b_1 < b_2 < \dots < b_{k-1} < b_k \leq n

我们称 ab1,ab2,,abka_{b_1}, a_{b_2}, \cdots, a_{b_k} aa 的一个子序列。

如果这个子序列同时还满足

$$a_{b_1} \geq a_{b_2} \geq \cdots \geq a_{b_{k-1}}\geq a_{b_k} $$

我们称这个子序列是不上升的。

组合数 (nm)\binom {n} {m} 是从 nn 个互不相同的元素中取 mm 个元素的方案数,具体计算方案如下:

$$\binom {n}{m}=\frac{n!}{m!(n-m)!}=\frac{n \times (n-1) \times \cdots \times 2 \times 1}{(m \times (m-1) \cdots \times 2 \times 1)((n-m)\times(n-m-1)\times \cdots \times 2 \times 1)} $$

这里要特别注意,因为我们只考虑不上升子序列,所以在求组合数的过程中,一定满足 nmn \geq m ,也就是 (abi1abi)\binom {a_{b_{i-1}}}{a_{b_i}} 中一定有 abi1abia_{b_{i-1}} \geq a_{b_i}

我们在这里强调取模 xmodyx \mod y 的定义:

$x \bmod y = x -\left \lfloor \frac{x}{y} \right \rfloor \times y$

其中 n\left \lfloor n \right \rfloor 表示小于等于 nn 的最大整数。

xmod2>0x \bmod 2 > 0 ,就是在说 xx 是奇数。

与此同时,经验告诉我们一个长度为 nn 的序列,子序列个数有 O(2n)O(2^n) 个,所以我们通过对答案取模来避免输出过大。

B 君觉得 G 君说的十分有道理,于是再次强调了这些基本概念。

最后, G 君听说这个题是作为 gift 送给大家,她有一句忠告。

“Vorsicht, Gift!”

“小心. . . . . .剧毒! ”

输入格式

第一行一个整数 nn

接下来 nn 行,每行一个整数,这 nn 行中的第 ii 行,表示 aia_i

输出格式

一行一个整数表示答案。

4
15
7
3
1
11

提示

对于前 10%10\% 的测试点,n9n \leq 91ai131\leq a_i\leq 13

对于前 20%20\% 的测试点,n17n\leq 171ai201\leq a_i\leq 20

对于前 40%40\% 的测试点,n1911n\leq 19111ai40001\leq a_i\leq 4000

对于前 70%70\% 的测试点,n2017n\leq 2017

对于前 85%85\% 的测试点,n100084n\leq 100084

对于 100%100\% 的测试点,1n2119851\leq n\leq 2119851ai2333331\leq a_i\leq 233333。所有的 aia_i 互不相同,也就是说不存在 i,ji, j 同时满足 1i<jn1\leq i < j\leq nai=aja_i = a_j