UVA 10689 - Yet another Number Sequence

题目链接

题意：斐波那契给前两项，求出第n项，并保留m位

思路：挺裸的矩阵快速幂，就是取模的值是10^m

代码：

#include 
  
   
#include 
   
     const int mod[5] = {0, 10, 100, 1000, 10000}; int t, a, b, n, m; struct mat { int v[2][2]; mat() {memset(v, 0, sizeof(v));} mat operator * (mat c) { mat ans; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { ans.v[i][j] = (ans.v[i][j] + v[i][k] * c.v[k][j]) % mod[m]; } } } return ans; } }; mat pow_mod(mat x, int k) { mat ans; ans.v[0][0] = ans.v[1][1] = 1; while (k) { if (k&1) ans = ans * x; x = x * x; k >>= 1; } return ans; } int solve() { if (n == 0) return a; if (n == 1) return b; mat ans; ans.v[0][0] = ans.v[0][1] = ans.v[1][0] = 1; ans = pow_mod(ans, n - 1); return (ans.v[0][0] * b + ans.v[0][1] * a); } int main() { scanf("%d", &t); while (t--) { scanf("%d%d%d%d", &a, &b, &n, &m); printf("%d\n", solve() % mod[m]); } return 0; }