| 题目名称 | 2203. [Codeforces 575 A] Fibonotci |
|---|---|
| 输入输出 | fibonotci.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 000
于2016-04-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：13， 通过率：53.85% | ||||
 kito |
100 | 0.878 s | 4.10 MiB | C++ |
 神利·代目 |
100 | 0.880 s | 20.13 MiB | C++ |
 FoolMike |
100 | 1.137 s | 5.65 MiB | C++ |
 阿狸 |
100 | 1.868 s | 27.40 MiB | C++ |
 zys |
100 | 2.193 s | 15.55 MiB | C++ |
|
zys |
100 | 2.225 s | 13.99 MiB | C++ |
 xinging |
100 | 3.277 s | 61.28 MiB | C++ |
|
kito |
60 | 0.885 s | 4.10 MiB | C++ |
 zhengtn03 |
50 | 0.809 s | 8.52 MiB | C++ |
|
阿狸 |
50 | 1.159 s | 27.40 MiB | C++ |
| 关于 Fibonotci 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
原题中并没有j<=k这一限制，真是害人不浅……
FoolMike
2017-07-01 17:12
3楼
| ||||
|
http://blog.csdn.net/qzh_1430586275/article/details/52332332
本蒟蒻的题解 xinging
2016-08-26 22:45
2楼
| ||||
|
太神辣
 葳棠殇
2016-04-01 06:58
1楼
| ||||
2203. [Codeforces 575 A] Fibonotci
★★★ 输入文件：fibonotci.in
输出文件：fibonotci.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
fibonotci序列定义为下：
F[n]=s[n-1]F[n-1]+s[n-2]F[n-2] (n>=2)
F[0]=0,F[1]=1
其中s是一个循环长度为n的循环数组，即满足s[i]=s[i % n]。
不过，s这个数组被熊孩子修改了几个位置，他把s中的第j个位置修
改为了vj，也就是说，对于位置j，s[j]=v[j](j>=n)。
请你在熊孩子修改之后，求出F[k]对P取模的结果。
【输入格式】
第一行两个整数k，P。
接下来一行一个整数n，接下来一行n个整数，表示s[i]。
再接下来一行一个整数m，表示熊孩子的修改。
接下来m行，每行两个整数j，v[j]，表示熊孩子做的修改，除修改位
置之外的位置i，满足，s[i]=s[i%n](i>=n)
【输出格式】
输出一个整数，表示答案
【样例输入】
10 8
3
1 2 1
2
7 3
5 4
【样例输出】
4
【提示】
对于20%的数据，m=0
对于50%的数据，k<=10^6
对于100%的数据，n,m<=50000,0<=K<=10^18,1<=P<=10^9,
1<=s[i],v[j]<=10^9,n<=j<=10^18，数据保证j互不相同
【来源】
Codeforces 575 A