UOJ Logo hszxoizjn的博客

博客

Problem B

2018-08-09 20:12:07 By hszxoizjn

变系数非波那契序列的定义如下:

$F_n~=~s_{n~-~1}\times F_{n~-~1}~+~s_{n~-~2}\times F_{n~-~2}$

其中

$F_0~=~0,~F_1~=~1$

序列s是一个无限的近似于循环长度为n的周期序列。也就是说对于大部分 $i\ge N$ , $s_i=s_{i~mod~N}$ 是成立的。

比如下面这个循环长度为4的近周期序列:

s = (5,3,8,11,5,3,7,11,5,3,8,11,…)

可以发现i=6的时候, $s_i=s_{i~mod~4}$ 并不成立 ( $s_6~=~7$ 而 $s_2~=~8$ )。

输入中会给出 $s_0,~s_1,~...,~s_{N~-~1}$ ,还有若干个 $s_i\ne s_{i~mod~N}$ 的位置及其具体值。

请计算 $F_K~mod~P$

Input

单组测试数据。

第一行有两个整数K和P(0≤K≤10^18,1≤P≤10^9)

第二行有一个整数N。(1≤N≤50000)

第三行有N个以空格分开的整数表示s序列的前N项。(1≤si≤10^9, i=0,1,...N-1)

第四行有一个整数M。(1≤M≤50000)

接下来M行每行有两个整数 j 和 v,表示 s[j]≠s[j mod N],并且s[j]=v。保证所有输入的j都是不一样的。(N≤j≤10^18, 1≤v≤10^9)

所有输入均为整数。

Output

输出F(K)对P取余的结果。

Sample Input

样例输入1

10 8

3

1 2 1

2

7 3

5 4

Sample Output

样例输出1

4

评论

Acceptor
@hszxoizjn 您是怎么搞出来滴啊
15632869526
变系数非波那契序列的定义如下: $F_n~=~s_{n~-~1}\times F_{n~-~1}~+~s_{n~-~2}\times F_{n~-~2}$ 其中 $F_0~=~0,~F_1~=~1$ 序列s是一个无限的近似于循环长度为n的周期序列。也就是说对于大部分 $i\ge N$ , $s_i=s_{i~mod~N}$ 是成立的。 比如下面这个循环长度为4的近周期序列: s = (5,3,8,11,5,3,7,11,5,3,8,11,…) 可以发现i=6的时候, $s_i=s_{i~mod~4}$ 并不成立 ( $s_6~=~7$ 而 $s_2~=~8$ )。 输入中会给出 $s_0,~s_1,~...,~s_{N~-~1}$ ,还有若干个 $s_i\ne s_{i~mod~N}$ 的位置及其具体值。 请计算 $F_K~mod~P$
hzoi2017_djw
In the first line there is two numbers $N$ and $Q$. Then in the second line there are $N$ numbers:$a[1]..a[N]$ In the next $Q$ lines,there are two numbers $L,R$ in each line. $N \leq 1000, Q \leq 100000, L \leq R, 1 \leq a[i] \leq 2^{31}-1$
hzoi2017_djw
Dylans is given $N$ numbers $a[1]....a[N]$ And there are $Q$ questions. Each question is like this $(L,R)$ his goal is to find the “inversions” from number $L$ to number $R$. more formally,his needs to find the numbers of pair($x,y$), that $L \leq x,y \leq R$ and $x < y$ and $a[x] > a[y]$
VivianWhite
有一个算术表达式 $x_1~\Delta~x_2~\Delta~x_3~\Delta~,...,~\Delta~x_n$, $x_1,x_2,x_3,...,x_n$ 是1到 9的数字, $\Delta$是'+'或者'*'。 现在要求你在这个表达式中加一对括号,使得这个式子的值最大。 样例解释:3 + 5 * (7 + 8) * 4 = 303。 Input 单组测试数据。 第一给出表达式s(1 ≤ |s| ≤ 5001, |s| 是奇数),它的奇数位是1到9的数字字符,偶数位是'+'或'*'。 '*'的数目不超过15。 Output 输出最大的值。 Sample Input 3+5*7+8*4 Sample Output 303
Jumbo
$1\leq i\leq j<k\leq length(S)$
VivianWhite
给定一系列数字$ A = a_1,a_2,...,a_N $,如果$ b_1 <b_2 <... <b_k $,则$ A $的子序列$ b_1,b_2,...,b_k $被称为增加。LY刚刚学会了如何找到增长最快的子序列(LIS)。 现在他必须选择$ L $连续数字并将其从$ A $中删除,原因有些神秘。他可以选择所选间隔的任意起始位置,以便最大化剩余数字的LIS长度。你能帮他解决这个问题吗? 输入 第一行输入包含一个数字$ T $,表示测试用例的数量($T≤100$)。 对于每个测试用例,第一行包含两个数字$ N $和$ L $,如上所述($1≤N≤100000,0≤L≤N$)。第二行由$ N $整数组成,表示序列。数字的绝对值不超过$ 10 ^ 9 $。 所有测试用例的N总和不会超过500000。 产量 对于每个测试用例,输出由“Case #X:Y”组成的单行。$ X $是从1开始的测试用例编号。$ Y $是删除间隔后LIS的最大长度。
VivianWhite
这个游戏是这样的,首先度度熊拥有一个公差集合$\{D\}$,然后它依次写下$N$个数字排成一行。游戏规则很简单: 1. 在当前剩下的有序数组中选择$X (X \geq 2)$ 个连续数字; 2. 检查$1$选择的$X$个数字是否构成等差数列,且公差 $d\in \{D\}$; 3. 如果$2$满足,可以在数组中删除这$X$个数字; 4. 重复 $1 - 3$ 步,直到无法删除更多数字。 度度熊最多能删掉多少个数字,如果它足够聪明的话? Input 第一行一个整数$T$,表示$T(1 \leq T \leq 100)$ 组数据。 每组数据以两个整数 $N$,$M$ 开始 。接着的一行包括 $N$ 个整数,表示排成一行的有序数组 $A_{i}$。接下来的一行是 $M$ 个整数,即给定的公差集合 $D_{i}$。 $1 \leq N, M \leq 300$ $-1\ 000\ 000\ 000 \leq A_{i}, D_{i} \leq 1\ 000\ 000\ 000$
Jumbo
Dylans is given $N$ numbers $a[1]....a[N]$ And there are $Q$ questions. Each question is like this $(L,R)$ his goal is to find the “inversions” from number $L$ to number $R$. more formally,his needs to find the numbers of pair($x,y$), that $L \leq x,y \leq R$ and $x < y$ and $a[x] > a[y]$ Input In the first line there is two numbers $N$ and $Q$. Then in the second line there are $N$ numbers:$a[1]..a[N]$ In the next $Q$ lines,there are two numbers $L,R$ in each line. $N \leq 1000, Q \leq 100000, L \leq R, 1 \leq a[i] \leq 2^{31}-1$ Output For each query,print the numbers of "inversions” Sample Input 3 2 3 2 1 1 2 1 3 Sample Output 1 3 Hint You shouldn't print any space in each end of the line in the hack data.
hzoi2017_djw
You know that you have $$$n$$$ bacteria in the Petri dish and size of the $$$i$$$-th bacteria is $$$a_i$$$. Also you know intergalactic positive integer constant $$$K$$$. The $$$i$$$-th bacteria can swallow the $$$j$$$-th bacteria if and only if $$$a_i > a_j$$$ and $$$a_i \le a_j + K$$$. The $$$j$$$-th bacteria disappear, but the $$$i$$$-th bacteria doesn't change its size. The bacteria can perform multiple swallows. On each swallow operation any bacteria $$$i$$$ can swallow any bacteria $$$j$$$ if $$$a_i > a_j$$$ and $$$a_i \le a_j + K$$$. The swallow operations go one after another.

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。