【wikioi】1281 Xn数列（矩阵乘法）

http://wikioi.com/problem/1281/

矩阵真是个神奇的东西。。

只要搞出一个矩阵乘法，那么递推式可以完美的用上快速幂，然后使复杂度降到log

真是神奇。

在本题中，应该很快能得到下边的矩阵：
┏ a, 0 ┓
[X_n, c] × ┃ ┃ = [X_n+1, c]
┗ 1, 1 ┛

那么我要要乘n次，也就是说要乘n个

┏ a, 0 ┓
┃ ┃
┗ 1, 1 ┛

因为是个方阵，所以可以用快速幂

我们先用快速幂算出n个这个2×2的矩阵，然后再乘上[X0, c]

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

typedef long long matrix[2][2];

typedef long long ll;

matrix ta, tb, f;

inline const ll mul(ll a, ll b, const ll &MOD) {

	ll ret=0;

	while(b) {

		if(b&1) ret=(ret+a)%MOD;

		a=(a<<1)%MOD;

		b>>=1;

	}

	return ret;

}

inline void matrixmul(matrix a, matrix b, matrix c, const int &la, const int &lb, const int &lc, const ll &MOD) {

	matrix t;

	rep(i, la) rep(j, lc) {

		t[i][j]=0;

		rep(k, lb) t[i][j]=(t[i][j]+mul(a[i][k], b[k][j], MOD))%MOD;

	}

	rep(i, la) rep(j, lc)

		c[i][j]=t[i][j];

}

int main() {

	ll m, a, c, x, n, g;

	cin >> m >> a >> c >> x >> n >> g;

	ta[0][0]=a; ta[1][0]=ta[1][1]=1;

	tb[0][0]=tb[1][1]=1;

	f[0][0]=x; f[0][1]=c;

	while(n) {

		if(n&1) matrixmul(ta, tb, tb, 2, 2, 2, m);

		matrixmul(ta, ta, ta, 2, 2, 2, m);

		n>>=1;

	}

	matrixmul(f, tb, f, 1, 2, 2, m);

	cout << f[0][0]%g;

	return 0;

}

题目描述 Description

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

X_n+1 = ( aX_n + c ) mod m，求Xn

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

输入描述 Input Description

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

输出描述 Output Description

输出一个数 X_n mod g

样例输入 Sample Input

11 8 7 1 5 3

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

int64按位相乘可以不要用高精度。

秒客网