P3773 [CTSC2017]吉夫特

    • 363通过
    • 557提交
  • 题目提供者 __stdcall
  • 评测方式 云端评测
  • 标签 枚举,暴力 进制 递归 WC/CTSC/集训队 2017 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 500MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    输入一个长度为 $n$ 的数列 $a_1, a_2, \cdots , a_n$ 问有多少个长度大于等于 $2$ 的不上升的子序列满足:

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

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

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

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

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

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

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

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

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

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

    $$\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)}$$

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

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

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

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

    $x \mod 2 > 0$ ,就是在说 $x$ 是奇数。

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

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

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

    “Vorsicht, Gift!”

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

    输入输出格式

    输入格式:

    第一行一个整数 n。

    接下来 n 行,每行一个整数,这 n 行中的第 i 行,表示 ai。

    输出格式:

    一行一个整数表示答案。

    输入输出样例

    输入样例#1: 复制
    4
    15
    7
    3
    1
    输出样例#1: 复制
    11

    说明

    • 对于前 10% 的测试点, n ≤ 9, 1 ≤ ai ≤ 13;

    • 对于前 20% 的测试点, n ≤ 17, 1 ≤ ai ≤ 20;

    • 对于前 40% 的测试点, n ≤ 1911, 1 ≤ ai ≤ 4000;

    • 对于前 70% 的测试点, n ≤ 2017;

    • 对于前 85% 的测试点, n ≤ 100084;

    • 对于 100% 的测试点, 1 ≤ n ≤ 211985, 1 ≤ ai ≤ 233333。所有的 ai 互不相同,也就是说不存在 i, j 同时满足 1 ≤ i < j ≤ n 和 ai = aj。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。