uva 10698 矩阵快速幂

2019-04-14 18:52发布

站内文章 / 模拟电子
10970 0 1580
题意：类似于fibonacci数列的求法，值得注意的是题目并不是让求简单的F（n）,而是求f(n)模一个数
直接矩阵快速幂就行，顺便模就行 #include #include #include #include #define rep(i, j, k) for(int i = j; i <= k; i++) using namespace std; const int N = 2; int MOD = 1; struct Matrix { int ary[N][N]; Matrix() { memset (ary, 0, sizeof (ary)); } }; const Matrix operator*(const Matrix & A, const Matrix & B) { Matrix t; rep (i, 0, N - 1) rep (j, 0, N - 1) rep (k, 0, N - 1) t.ary[i][j] += A.ary[i][k] * B.ary[k][j], t.ary[i][j] %= MOD; return t; } int quick_pow(int a, int b, int n) { if (n == 0) return a % MOD; if (n == 1) return b % MOD; Matrix ans, tmp; tmp.ary[0][0] = 1; ans.ary[0][0] = (a + b) % MOD; rep (i, 0, N - 1) tmp.ary[i][1 - i] = 1, ans.ary[i][1 - i] = b % MOD; n -= 2; while (n) { if (n & 1) ans = ans * tmp; n >>= 1; tmp = tmp * tmp; } return ans.ary[0][0]; } int a, b, n, m; int main() { int ti; cin >> ti; while (ti--) { scanf("%d%d%d%d", &a, &b, &n, &m); MOD = 1; while (m--) MOD *= 10; printf("%d ", quick_pow(a, b, n)); } return 0; }

热门文章