[NOI2013] 矩阵游戏

求, 递推式如下: 在看到n,m的范围之前, 我们意识到可以用矩阵快速幂加速计算.

在看到n,m的范围之后......

难道可以取模吗? 联想到费马小定理和欧拉定理, 但这里是矩阵乘法啊 (虽然置换群也有类似的性质).

快速幂可以看成二进制拆分. 我的做法是, 换做十进制拆分, 这样就可以直接根据十进制数的字符串来计算了.

还是有点虚......观察到

所以只用保存矩阵的第一列, 常数减小.

然后就可以AC了.

看了其他人的题解, 发现指数真的可以取模.

当,

指数可以对取模.

当,

指数可以对取模.

const int N = 1e6 + 2, MOD = 1e9 + 7;
typedef unsigned long long ull;

struct Matrix {
	ull a, b;
	Matrix(ull a, ull b): a(a), b(b) {}
	Matrix operator*(const Matrix& o) const
	{
		return Matrix(a * o.a % MOD, (b * o.a + o.b) % MOD);
	}
};

char n[N], m[N];

Matrix power(Matrix A, char s[], int n)
{
	Matrix X(1, 0);
	
	per (i, n-1, 0) {
		Matrix t = A;
		int j = 2;
		if (s[i] != '0') {
			for (; j <= s[i]-'0'; ++j) A = A * t;
			X = X * A;
		}
		for (; j <= 10; ++j) A = A * t;
	}
	return X;
}

int decrease(char s[])
{
	int n = strlen(s), i;
	for (i = n-1; s[i] == '0'; --i) s[i] = '9';
	--s[i];
	return n;
}

int main()
{
	int a, b, c, d;
	scanf("%s%s%d%d%d%d", n, m, &a, &b, &c, &d);
	
	int len_n = decrease(n), len_m = decrease(m);
	
	Matrix A(a, b), B(c, d), X(power(A, m, len_m)), Y(power(X * B, n, len_n)), Z = Y*X;

	printf("%llu\n", (Z.a + Z.b) % MOD);

	return 0;
}