[CODEVS 1281] Xn数列

描述

给你6个数，m, a, c, x0, n, g Xn+1 = ( aXn + c ) mod m，，求Xn

分析

比较裸的矩阵乘法题, 好久没做了, 写写思路

假设矩阵 A = { {a1, a2}, {a3, a4} }, B = { {b1, b2}, {b3, b4} }. 根据矩阵乘法的计算方法, 有 : A×B = { {a1b1+a2b2, a1b2+a2b4}, {a3b1+a4b3, a3b2+a4b4} }. 那么我们想得到的是 a*Xn + c = Xn+1 假设 X 存在a1里, 那么应有 Xn * b1 + a2 * b2 = Xn+1 那么就可以得到 a2 = 1, b1 = a, b2 = c. (为什么不能 a2 = c, b2 = 1 ? 因为乘完一次 a2 就变了, 下个加的就不是 c 了).

这样矩阵就建好了, 接下来就是按部就班的矩阵乘法了. 不过, 这里数据太大, 不使用特殊技巧用 unsigned long long 都会溢出. 高精度 ? 其实不用, 因为最后都要模一下.

特殊技巧

用类似快速幂的方法写一个快速加, 加一下模一下, 用来避免直接乘的溢出.

代码

20ms 256kB 额… 难道 mod 和 sum 都是保留字 ? 为啥都有高亮 ?

#include<cstdio>using namespace std;typedef long long LL;LL mod, a, c, x0, n, g;struct Matrix {LL m[2][2];} base, X0;// return a * bLL quickadd(LL a, LL b) {LL ans = 0;a %= mod; b %= mod;while(b > 0) {if(b & 1) ans = (ans + a) % mod;a = (a + a) % mod;b >>= 1;}return ans;}Matrix mul(Matrix a, Matrix b) {Matrix ans;for(int i = 0; i < 2; i++)for(int j = 0; j < 2; j++) {LL sum = 0;for(int k = 0; k < 2; k++)sum = (sum + quickadd(a.m[i][k], b.m[k][j])) % mod;ans.m[i][j] = sum;}return ans;}Matrix pow(Matrix a, LL n) {Matrix p = {{1, 0, 0, 1}};while(n > 0) {if(n & 1) p = mul(p, a);a = mul(a, a);n /= 2;}return p;}int main() {scanf(“%lld%lld%lld%lld%lld%lld”, &mod, &a, &c, &x0, &n, &g);base = (Matrix) {{a, 0, 1, 1}};X0 = (Matrix){{x0, c, 0, 0}};Matrix ans = mul(X0, pow(base, n));printf(“%lld\n”, ans.m[0][0] % g);return 0;}

没有什么可留恋，只有抑制不住的梦想，