[NOI 2012] 随机数生成器

知识点

矩阵快速幂、仿射变换、模运算

解题思路

一次变换为f(x)=ax+c(mod m)。把复合变换表示为乘数A与常数C，函数平方得到(A²,AC+C)。二进制拆分n，将相应变换作用到当前x；全部乘加使用128位再模m，最后输出x%g。

正确性说明

仿射函数复合仍为仿射函数，平方公式由直接代入得到。快速幂维护已应用变换和剩余幂的等价关系，处理完n的所有二进制位后恰应用f的n次复合。每次模m不改变同余结果。

易错点

m可为1；n≥1；a、c、X0可大于m，先取模；两个十的十八次量级数相乘不能用64位；最后才对g取模。

复杂度

时间O(log n)，空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
using I=__int128_t;int main(){long long m,a,c,x,n,g;cin>>m>>a>>c>>x>>n>>g;a%=m;c%=m;x%=m;while(n){if(n&1)x=(I(a)*x+c)%m;c=(I(a)*c+c)%m;a=I(a)*a%m;n>>=1;}cout<<x%g<<'\n';}