生活随笔
收集整理的這篇文章主要介紹了
Happy Necklace dp 递推 矩阵快速幂
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
- 當滿足素數2和素數3的條件后，下一個素數區間5乃至之后的都會被滿足。
- 考慮能否從f[n - 1]轉換到f[n]，考慮第i - 1位，如果后面加紅色一定滿足條件，所以f[n]先是加上f[n - 1]
- 如果最后加藍色，上一位一定是紅色，且上上位也得是紅色
- 所以f[n] = f[n - 1] + f[n - 3]
- n的范圍太大，所以無法將遞推的結果保存起來，所以矩陣快速冪
#include <iostream>
#include <cstring>using namespace std
;typedef long long ll
;const int N
= 3;
const ll mod
= 1e9 + 7;ll n
;void mul(ll c
[], ll a
[], ll b
[][N
])
{ll temp
[N
] = {0};for (int i
= 0; i
< N
; i
++ )for (int j
= 0; j
< N
; j
++ )temp
[i
] = (temp
[i
] + a
[j
] * b
[j
][i
] % mod
) % mod
;memcpy(c
, temp
, sizeof temp
);
}void mul(ll c
[][N
], ll a
[][N
], ll b
[][N
])
{ll temp
[N
][N
] = {0};for (int i
= 0; i
< N
; i
++ )for (int j
= 0; j
< N
; j
++ )for (int k
= 0; k
< N
; k
++ )temp
[i
][j
] = (temp
[i
][j
] + a
[i
][k
] * b
[k
][j
] % mod
) % mod
;memcpy(c
, temp
, sizeof temp
);
}int main()
{ios
::sync_with_stdio(false); cin
.tie(0); cout
.tie(0);int _
;cin
>> _
;while (_
-- ){cin
>> n
;if (n
== 2){cout
<< 3 << endl
;continue;}if (n
== 3){cout
<< 4 << endl
;continue;}n
-= 3;ll f1
[N
] = {4, 3, 2};ll a
[N
][N
] = {{1, 1, 0},{0, 0, 1},{1, 0, 0}};
while (n
){if (n
& 1) mul(f1
, f1
, a
);mul(a
, a
, a
);n
>>= 1;}cout
<< f1
[0] % mod
<< endl
;}return 0;
}
總結
以上是生活随笔為你收集整理的Happy Necklace dp 递推 矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
