[NOI2012] 随机数生成器 [CodeVS1281] Xn数列

本文主要是介绍[NOI2012] 随机数生成器 [CodeVS1281] Xn数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述 Description

给你6个数，m, a, c, x0, n, g

Xn+1 = ( aXn + c ) mod m，求Xn

m, a, c, x0, n, g<=10^18

输入描述 Input Description

一行六个数 m, a, c, x0, n, g

输出描述 Output Description

输出一个数 Xn mod g

样例输入 Sample Input

11 8 7 1 5 3

样例输出 Sample Output

题解

$\begin{bmatrix} x_n&c\end{bmatrix}=\begin{bmatrix} x_{n-1}&c\end{bmatrix}\cdot \begin{bmatrix} a&0\\1&1 \end{bmatrix}$
甭管什么直接矩阵乘法都会爆炸QAQ
所以模仿快速幂写个快速加（a*b=a+a+a+…..+a）
其实你想更快的话，，你会发现那个2X2的矩阵的第2列是不变的，，

varm,a,c,x0,n,s,ans:int64;d,e,f,g:qword;t,y:array[1..2,1..2]of qword;i,j,k:longint;
function mmod(a,b:int64):qword;
var len:int64;
beginlen:=0;while b<>0 dobeginif (b and 1)=1then len:=(len+a)mod m;a:=(a*2)mod m;b:=b div 2;end;exit(len);
end;beginreadln(m,a,c,x0,n,s);t[1,1]:=1; t[1,2]:=0; t[2,1]:=0; t[2,2]:=1;y[1,1]:=a; y[1,2]:=0; y[2,1]:=1; y[2,2]:=1;while n<>0 dobeginif (n and 1)=1then begin {t=t*y}d:=(mmod(t[1,1],y[1,1])+mmod(t[1,2],y[2,1]))mod m;e:=(mmod(t[1,1],y[1,2])+mmod(t[1,2],y[2,2]))mod m;f:=(mmod(t[2,1],y[1,1])+mmod(t[2,2],y[2,1]))mod m;g:=(mmod(t[2,1],y[1,2])+mmod(t[2,2],y[2,2]))mod m;t[1,1]:=d; t[1,2]:=e; t[2,1]:=f; t[2,2]:=g;end;{y=y*y}d:=(mmod(y[1,1],y[1,1])+mmod(y[1,2],y[2,1]))mod m;e:=(mmod(y[1,1],y[1,2])+mmod(y[1,2],y[2,2]))mod m;f:=(mmod(y[2,1],y[1,1])+mmod(y[2,2],y[2,1]))mod m;g:=(mmod(y[2,1],y[1,2])+mmod(y[2,2],y[2,2]))mod m;y[1,1]:=d; y[1,2]:=e; y[2,1]:=f; y[2,2]:=g;n:=n div 2;end;ans:=(((mmod(x0,t[1,1])+mmod(c,t[2,1])+m)mod m)+s)mod s;writeln(ans);
end.