刷题比赛(Problem Solving Contest)

题目描述

nodgd 是一个喜欢写程序的同学，前不久洛谷 OJ 横空出世，nodgd 同学当然第一时间来到洛谷 OJ 刷题。
于是发生了一系列有趣的事情，他就打算用这些事情来出题恶心大家……

洛谷OJ当然算是好地方，nodgd 同学打算和朋友分享一下。于是他就拉上了他的朋友 Ciocio 和 Nicole 两位同学一起刷题。喜欢比赛的他们当然不放过这样一次刷题比赛的机会！

在第 $1$ 天 nodgd,Ciocio,Nicole 都只做了 $1$ 道题。

在第 $2$ 天 nodgd,Ciocio,Nicole 都只做了 $3$ 道题。

他们都有着严格的刷题规则，并且会在每一天都很遵守规则的刷一定量的题。

1、nodgd 同学第 $k+2$ 天刷题数量

$$a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1$$

2、Ciocio 同学第 $k+2$ 天刷题数量

$$b_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k$$

3、Nicole 同学第 $k+2$ 天刷题数量

$$c_{k+2} = xc_{k+1}+yc_k + a_{k+1} + b_{k+1} + z^k+k+2$$

（以上的字母 $p,q,r,t,u,v,w,x,y,z$ 都是给定的常数，并保证是正整数）

于是他们开始了长时间的刷题比赛！一共进行了 $n$ 天

但是时间是可贵的，nodgd 想快速知道第 $n$ 天每个人的刷题数量。
不过 nodgd 同学还有大量的数学竞赛题、物理竞赛题、英语竞赛题、美术竞赛题、体育竞赛题…… 要做，就拜托你来帮他算算了。

由于结果很大，输出结果 $\bmod \space m$ 的值即可。

输入格式

第一行两个正整数 $n,m$。

第二行四个正整数 $p,q,r,t$。

第三行三个正整数 $u,v,w$。

第四行三个正整数 $x,y,z$。

输出格式

共三行，每行一个名字 + 一个空格 + 一个整数。
依次是 nodgd,Ciocio,Nicole 和他们在第 $n$ 天刷题数量 $\bmod \space m$ 的值。

样例输入 #1

4 10007
2 1 1 1
2 2 3
1 1 2

样例输出 #1

nodgd 74
Ciocio 80
Nicole 59

数据范围

对于 $100\%$ 的数据，$4\le n \le 10^{16}$，$2\le m \le 10^{16}$，$1\le p,q,r,t,u,v,w,x,y,z \le 100$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

---

测试点分布

Subtask	分值	测试点编号	说明
0	10	1	样例
1	20	2~8	小规模 n≤20,m≤1e6 / 特殊: 系数全为1 / 特殊: w=z=1退化底数
2	15	9~11	Hack: m=2 最小模数取模边界 / Hack: m=1e16 大模数64位乘法溢出 / Hack: n=1e16,m=1e16 双极限
3	30	12~20	中规模 n≤1e9,m≤1e9 / 大规模 n,m≈1e16 11维矩阵快速幂压力
4	25	21~25	随机 4≤n≤1e16,2≤m≤1e16 回归

---

出处：原题链接