前言
没看题解把未来程序切了，很高兴，来写篇题解！
这篇题解在博客园里观看，效果明显更佳，请前往博客园。
Program1
简单的。显然答案为 \((a\times b) \bmod c\)，转成 __int128 后暴力乘即可。
代码有手就行。
Program2
简单的。给定 \(n\) 与 \(mod\)，有递推式
\[a_0 = 1, b_0 = 0, c_0 = 0
\]
\[\begin{cases}
a_i = 2\times b_i-a_{i-1}+c_{i-1}=a_{i-1}+2\times b_{i-1}+c_{i-1} \\
b_i = a_{i-1} + b_{i-1} \\
c_i = 2\times b_i-a_i+c_{i-1}=a_{i-1}\\
\end{cases}
\]
答案为 \(a_n - 2 \times b_n + c_n\)。但是 \(n\) 为 long long 级别，矩阵快速幂即可。具体地：
- 矩阵定义为 \(\begin{bmatrix}a_i, b_i, c_i\end{bmatrix}\)。
- 转移：\(\begin{bmatrix}a_{i-1}, b_{i-1}, c_{i-1}\end{bmatrix}\times \begin{bmatrix} 1 & 1 & 1 \\ 2 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}=\begin{bmatrix}a_i, b_i, c_i\end{bmatrix} \)
代码有手就行。依然是使用 __int128。