F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5298. -- [Cqoi2018]交错序列

5298: [Cqoi2018]交错序列

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 396  Solved: 144
[Submit][Status][Discuss]

Description

我们称一个仅由0、1构成的序列为"交错序列",当且仅当序列中没有相邻的1(可以有相邻的0)。例如,000,001
,101,都是交错序列,而110则不是。对于一个长度为n的交错序列,统计其中0和1出现的次数,分别记为x和y。
给定参数a、b,定义一个交错序列的特征值为x^ay^b。注意这里规定任何整数的0次幂都等于1(包括0^0=1)。
显然长度为n的交错序列可能有多个。我们想要知道,所有长度为n的交错序列的特征值的和,除以m的余数。(m是
一个给定的质数)例如,全部长度为3的交错串为:000、001、010、100、101。
当a=1,b=2时,可计算31x02+21x12+21x12+21x12+11x22=10

Input

输入文件共一行,包含三个空格分开的整数n,a,b和m。
1≤n≤10000000,0≤a,b≤45,m<100000000

Output

输出文件共一行,为计算结果。

Sample Input

3 1 2 1009

Sample Output

10

HINT

Source

鸣谢Amphetamine整理题面

[Submit][Status][Discuss]

HOME Back