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

\n

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

\n

输入一个长度为 $n$ 的数列 $a_1, a_2, \\ldots, a_n$

\n

问有多少个长度大于等于 $2$ 的不上升的子序列 $a_{b_1}, a_{b_2}, \\ldots ,a_{b_k}$ 满足

\n

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

\n

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

\n

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

\n

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

\n

$$1 \\leq b_1 < b_2 < \\cdots < b_{k-1} < b_{k} \\leq n$$

\n

我们称 $a_{b_1}, a_{b_2}, \\ldots ,a_{b_k}$ 是 $a$ 的一个子序列。

\n

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

\n

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

\n

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

\n

组合数 $\\binom{n}{m}$ 是从 $n$ 个互不相同的元素中取 $m$ 个元素的方案数，具体计算方法如下：

\n

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

\n

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

\n

我们在这里强调取模 $x \\bmod y$ 的定义：

\n

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

\n

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

\n

$x \\bmod 2 > 0$，就是在说$x$是奇数。

\n

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

\n

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

\n

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

\n

\

统计

递交统计

【CTSC2017】吉夫特

信息

状态

支持

关于

还没有账户？

登录