[NOI2012]随机数生成器
给定一个数列的首项及其递推式,求第 $n$ 项模 $g$ 的结果.
显然矩阵加速递推.
那么我们看一下递推式 $:$
$$f_i = ( a\times f_{i-1} + c ) \% m$$
带有模是无所谓的,直接取模就好了.
构造矩阵 $:$
初始矩阵为 $:$
$$\left[\begin{array}{llll} f_{n} & c \end{array}\right]$$
目标矩阵为 $:$
$$\left[\begin{array}{llll} f_{n+1} & c \end{array}\right]$$
所以转移矩阵应满足 $:$
$$\left[\begin{array}{llll} f_{n} & c \end{array}\right] \times \left[\begin{array}{llll} ? & ? \ ? & ? \end{array}\right] = \left[\begin{array}{llll} f_{n+1} & c \end{array}\right]$$
根据递推式,可以得到转移矩阵是 $:$
$$\left[\begin{array}{llll} a & 0 \ 1 & 1 \end{array}\right]$$
然后我就直接一发矩阵快速幂莽了上去,然鹅,它 $WA$ 了,只有 $50pts$.
经过思考后发现,它中间溢出 $long\: long$ 了.怎么办?
难道使用龟速乘嘛?不!我们用 $__int128!$.然后它就 $AC$ 了.
1 |
|