← 返回题目

题库练习「CQOI2018」交错序列

← 上一题下一题 →

A6072 | $「CQOI2018」交错序列$

时间限制500ms

内存限制512MB

通过 / 提交0/0

题目描述

我们称一个仅由 $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$ 时，可计算：$3^1\times0^2+2^1\times1^2+2^1\times1^2+2^1\times1^2+1^1\times2^2=10$。

输入格式

共一行，包含三个空格分开的整数 $n,a,b$ 和 $m$。

输出格式

共一行，为计算结果。

输入输出样例

输入 #1

3 1 2 1009

输出 #1

输入 #2

4 3 2 1009

输出 #2

C++ 编辑器

输入

输出