#2129. 吉夫特
吉夫特
吉夫特
题目描述
第二试吉夫特(gift) IOI 2017 中国代表队选拔赛暨全国青少年信息学奥林匹克精英赛 吉夫特(gift) 【问题描述】 简单的题目,既是礼物,也是毒药。 B 君设计了一道简单的题目,准备作为gift 送给大家。 输入一个长度为n 的数列a1, a2, . . . , an 问有多少个长度大于等于2 的不上升的子 序列ab1, ab2, . . . , abk 满足 (abi−1 ) (ab1 ) (ab2 ) (abk−1 ) ∏ k mod 2 = mod 2 > 0 × × · · · × abi ab2 ab3 abk i=2 输出这个个数对1000000007 取模的结果。 G 君看到题目后,为大家解释了一些基本概念。 我们选择任意多个整数bi 满足 1 ≤b1 < b2 < · · · < bk−1 < bk ≤n 我们称ab1, ab2, . . . , abk 是a 的一个子序列。 如果这个子序列同时还满足 ab1 ≥ab2 ≥· · · ≥abk−1 ≥abk 我们称这个子序列是不上升的。 组合数(n m) 是从n 个互不相同的元素中取m 个元素的方案数,具体计算方法如下: (n ) n × (n −1) × · · · × 2 × 1 n!
m!(n −m)! = (m × (m −1) × · · · × 2 × 1)((n −m) × (n −m −1) × · · · × 2 × 1) m 这里要特别注意,因为我们只考虑不上升子序列,所以在求组合数的过程中,一定 满足n ≥m,也就是(abi−1 abi ) 中一定有abi−1 ≥abi。 我们在这里强调取模x mod y 的定义: ⌊x ⌋ x mod y = x − × y y 其中⌊n⌋表示小于等于n 的最大整数。 x mod 2 > 0,就是在说x 是奇数。 与此同时,经验告诉我们一个长度为n 的序列,子序列个数有O(2n) 个,所以我们 通过对答案取模来避免输出过大。 B 君觉得G 君说的十分有道理,于是再次强调了这些基本概念。 最后,G 君听说这个题是作为gift 送给大家,她有一句忠告。 “Vorsicht, Gift!” ‘‘小心. . . . . . 剧毒!” 第2 页 共8 页 第二试吉夫特(gift) IOI 2017 中国代表队选拔赛暨全国青少年信息学奥林匹克精英赛 【输入格式】 从文件gift.in 中读入数据。 第一行一个整数n。 接下来n 行,每行一个整数,这n 行中的第i 行,表示ai。 【输出格式】 输出到文件gift.out 中。 一行一个整数表示答案。 【样例1 输入】 4 15 7 3 1 【样例1 输出】 11 【样例2~9】 见选手目录下的gift/gift2~9.in 与gift/gift2~9.ans。 【数据范围与约定】 • 对于前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。 第3 页 共8 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4
15
7
3
1
11
样例 2
9
11
6
2
3
5
8
4
7
9
7