| 题目名称 | 2725. MikeNOI |
|---|---|
| 输入输出 | MikeNOI.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 FoolMike
于2017-07-04加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：10， 通过率：70% | ||||
 _Itachi |
100 | 2.246 s | 16.29 MiB | C++ |
|
_Itachi |
100 | 2.274 s | 16.29 MiB | C++ |
 kito |
100 | 3.066 s | 10.34 MiB | C++ |
 SliverN |
100 | 3.309 s | 30.83 MiB | C++ |
 AntiLeaf |
100 | 5.764 s | 20.31 MiB | C++ |
 再见 |
100 | 6.996 s | 24.69 MiB | C++ |
 FoolMike |
100 | 7.148 s | 31.59 MiB | C++ |
 Imone NOI2018Au |
85 | 8.316 s | 13.44 MiB | C++ |
|
_Itachi |
60 | 1.965 s | 12.29 MiB | C++ |
|
再见 |
60 | 8.501 s | 16.69 MiB | C++ |
| 关于 MikeNOI 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
大佬真是强啊，，，，
 Go灬Fire
2017-07-26 10:16
7楼
| ||||
|
Mike教我wys。。。
再见
2017-07-12 18:46
6楼
| ||||
|
好可怕，居然不预处理就会渣精度。。
_Itachi
2017-07-12 07:16
5楼
| ||||
|
回复 @Imone NOI2017 Au :
您这个常数啊……我写的矩阵2*2套复数FFT都卡过了…… FoolMike
2017-07-07 21:32
4楼
| ||||
|
常数卡不进。。。
| ||||
|
留下flag。[下正上反]
MikeNOI2017稳进队 再见
2017-07-05 20:26
2楼
| ||||
|
元素是complex的matrix做复数意义下的FFT……
常数居然还能卡进时限…… FoolMike
2017-07-04 21:15
1楼
| ||||
【题目描述】
Mike即将参加NOI2017，由于Mike太菜，每道题只会打暴力……
这场比赛共有n道题，每道题有一个难度系数ai，由于Mike手速太慢，Mike只能选择其中的k道题来写。若Mike选择的题目难度系数之和为s，那么Mike会有f(s)翻车率。f数列满足以下递推式：
f(x)=2*f(x-1)+3*f(x-2)
Mike想要知道这场比赛Mike翻车率的期望，为了方便你计算，你只需要告诉Mike所有合法选题方案的翻车率之和对99991(一个质数)取模之后的结果即可。
【输入格式】
第一行两个整数n,k，分别表示这场比赛的题目数和Mike决定做的题目数。
第二行n个整数ai，分别表示每道题的难度系数。
第三行两个整数f0,f1，分别表示f数列的第0项和第1项。
【输出格式】
一行一个整数，表示答案。
【样例输入】
20 10 125 3162 3261 152 376 238 462 4382 376 4972 16 1872 463 9878 688 308 125 236 3526 543 1223 3412
【样例输出】
32071
【数据范围】
对于20%的数据，n<=20；
对于另外10%的数据，f0=f1=1；
对于另外20%的数据，n<=5000；
对于另外20%的数据，sigma(ai)<=10000，n<=100；
对于100%的数据，1<=n<=100000，1<=ai<=1e9，1<=f0,f1<99991