首页 > 代码库 > HDOJ 6030 矩阵快速幂

HDOJ 6030 矩阵快速幂

2024-11-01 09:54:39   209人阅读

链接：

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 矩阵快速幂


联系
我们