首页 > 代码库 > HDOJ 6030 矩阵快速幂
HDOJ 6030 矩阵快速幂
链接:
http://acm.hdu.edu.cn/showproblem.php?pid=6030
题意:
给一个手链染色,每连续素数个数的珠子中红色不能比蓝的多,问有多少种情况
题解:
公式为f[i]=f[i-1]+f[i-3],类似菲波那切数列,使用矩阵快速幂即可
代码:
31 typedef vector<ll> vec;32 typedef vector<vec> mat;33 34 mat mul(mat &A, mat &B) {35 mat C(A.size(), vec(B[0].size()));36 rep(i, 0, A.size()) rep(k, 0, B.size()) rep(j, 0, B[0].size())37 C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;38 return C;39 }40 41 mat pow(mat A, ll n) {42 mat B(A.size(), vec(A.size()));43 rep(i, 0, A.size()) B[i][i] = 1;44 while (n>0) {45 if (n & 1) B = mul(B, A);46 A = mul(A, A);47 n >>= 1;48 }49 return B;50 }51 52 int main() {53 int T;54 cin >> T;55 while (T--) {56 mat A(3, vec(3));57 A[0][0] = 1, A[0][1] = 0, A[0][2] = 1;58 A[1][0] = 1, A[1][1] = 0, A[2][2] = 0;59 A[2][0] = 0, A[2][1] = 1, A[2][2] = 0;60 ll n;61 cin >> n;62 A = pow(A, n - 2);63 ll ans = (A[2][0] * 6 + A[2][1] * 4 + A[2][2] * 3) % MOD;64 cout << ans << endl;65 }66 return 0;67 }
HDOJ 6030 矩阵快速幂
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。