BZOJ 2875 矩阵乘法 快速幂

题

给出$ m, a, c, X_0, n, g $，对
$$ X_n=(aX_{n-1}+c) \mod m $$
求$ X_n \mod g $

解

我也不知道为什么题面被吃了qwwwwq
就是裸的矩乘快速幂……
注意到转移矩阵恒为 $ \begin{bmatrix} a \& b \\\\ 0 \& 1 \end{bmatrix} $ ，所以只需要存第一行，可以reduce一半的计算量qwq
数学辣鸡表示矩阵不会推啦只能靠mathematica的符号计算啦
我把%m写括号里面了然后调半天没调出错qwqwqwqwqwq

码（820 kb 12 ms）

#include <cstdio>
#include <cstring>
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
long long m, x0, n, g; 
inline long long mul(long long a, long long b)
    {long long ret = 0; for(; b; b >>= 1, a += a, a %= m) if(b & 1) ret += a, ret %= m; return ret;}
struct M{long long a, b;
    M operator*(const M& rhs){return (M){mul(a, rhs.a), (b + mul(a, rhs.b)) % m};}
    M operator^(long long n){M ret; ret = (M){1, 0}; for(; n; n >>= 1, *this = *this * *this) if(n & 1) ret = ret * *this;return ret;}
} A;
int main()
{
    read(m, A.a, A.b); read(x0, n, g);
    A = (A ^ n);
    printf("%lld\n", (mul(A.a, x0) + A.b) % m % g);
    return 0;
}