傳送門

題目

$$\begin{array}{rlr}& f_n=c^{2?n?6}{f}_{n?1}{f}_{n?2}{f}_{n?3}& \end{array}$$

思路

我們通過迭代發現$f_n$其實就是由$c^{t_1},f_1^{t_2},f_2^{t_3},f_3^{t_4}$相乘得到，因此我們可以分別用矩陣快速冪求出$t_1,t_2,t_3,t_4$，最后用快速冪求得答案。
對于$n<=3$的我們直接輸出即可，$n>3$的我們先將$n$減去$3$，然后進行求解。
對$f_1,f_2,f_3$的指數，我們可以推出$x_n=x_{n?1}+x_{n?2}+x_{n?3}$：
$$\begin{array}{rlrlrlrlr}(x_n& & x_{n?1}& & x_{n?2})=(x_{n?1}& & x_{n?2}& & x_{n?3})?\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\end{array}?\end{array}$$
對$c$的指數，我們可以推出$x_n=x_{n?1}+x_{n?2}+x_{n?3}+2n=x_{n?1}+x_{n?2}+x_{n?3}+2(n?1)+2$:
$$\begin{array}{rlrlrlrlrlrlrlrlr}(x_n& & x_{n?1}& & x_{n?2}& & n& & 1)=(x_{n?1}& & x_{n?2}& & x_{n?3}& & n?1& & 1)?\begin{array}{ccccc}1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0\\ 1& 0& 0& 0& 0\\ 2& 0& 0& 1& 0\\ 2& 0& 0& 1& 1\end{array}?\end{array}$$
注意，由于我們處理出來的$x_1,x_2,x_3,x_4$都是指數部分，這里如果膜$1e9+7$的話是不對的，我們還需要對其進行歐拉降冪。

代碼實現

#include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std;typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL;#define lson rt<<1 #define rson rt<<1|1 #define lowbit(x) x&(-x) #define name2str(name) (#name) #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl #define FIN freopen("D://code//in.txt","r",stdin) #define IO ios::sync_with_stdio(false),cin.tie(0)const double eps = 1e-8; const int mod = 1000000007; const int maxn = 2e5 + 7; const double pi = acos(-1); const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3fLL;int f[10], a[10][10];void mulself(int a[10][10]) {int c[10][10];memset(c, 0, sizeof(c));for(int i = 0; i < 3; i++) {for(int j = 0; j < 3; j++) {for(int k = 0; k < 3; k++) {c[i][j] = (c[i][j] + (long long)a[i][k] * a[k][j] % (mod - 1)) % (mod - 1);}}}memcpy(a, c, sizeof(c)); }void mul(int f[10], int a[10][10]) {int c[10];memset(c, 0, sizeof(c));for(int i = 0; i < 3; i++) {for(int j = 0; j < 3; j++) {c[i] = (c[i] + (long long)f[j] * a[j][i] % (mod - 1)) % (mod - 1);}}memcpy(f, c, sizeof(c)); }void mulself1(int a[10][10]) {int c[10][10];memset(c, 0, sizeof(c));for(int i = 0; i < 5; i++) {for(int j = 0; j < 5; j++) {for(int k = 0; k < 5; k++) {c[i][j] = (c[i][j] + (long long)a[i][k] * a[k][j] % (mod - 1)) % (mod - 1);}}}memcpy(a, c, sizeof(c)); }void mul1(int f[10], int a[10][10]) {int c[10];memset(c, 0, sizeof(c));for(int i = 0; i < 5; i++) {for(int j = 0; j < 5; j++) {c[i] = (c[i] + (long long)f[j] * a[j][i] % (mod - 1)) % (mod - 1);}}memcpy(f, c, sizeof(c)); }int qpow(int x, int n) {int res = 1;while(n) {if(n & 1) res = 1LL * res * x % mod;x = 1LL * x * x % mod;n >>= 1;}return res; }LL n; int f1, f2, f3, c;int main(){scanf("%lld%d%d%d%d", &n, &f1, &f2, &f3, &c);if(n == 1) return printf("%d\n", f1) * 0;if(n == 2) return printf("%d\n", f2) * 0;if(n == 3) return printf("%d\n", f3) * 0;n -= 3;LL ans = 1;f[0] = 1, f[1] = 0, f[2] = 0;a[0][0] = 1, a[0][1] = 1, a[0][2] = 0;a[1][0] = 1, a[1][1] = 0, a[1][2] = 1;a[2][0] = 1, a[2][1] = 0, a[2][2] = 0;LL x = n;while(x) {if(x & 1) mul(f, a);mulself(a);x >>= 1;}ans = ans * qpow(f3, f[0]) % mod;f[0] = 0, f[1] = 1, f[2] = 0;a[0][0] = 1, a[0][1] = 1, a[0][2] = 0;a[1][0] = 1, a[1][1] = 0, a[1][2] = 1;a[2][0] = 1, a[2][1] = 0, a[2][2] = 0;x = n;while(x) {if(x & 1) mul(f, a);mulself(a);x >>= 1;}ans = ans * qpow(f2, f[0]) % mod;f[0] = 0, f[1] = 0, f[2] = 1;a[0][0] = 1, a[0][1] = 1, a[0][2] = 0;a[1][0] = 1, a[1][1] = 0, a[1][2] = 1;a[2][0] = 1, a[2][1] = 0, a[2][2] = 0;x = n;while(x) {if(x & 1) mul(f, a);mulself(a);x >>= 1;}ans = ans * qpow(f1, f[0]) % mod;if(n == 1) f[0] = 2;if(n == 2) f[0] = 6;if(n == 3) f[0] = 14;if(n > 3) {n -= 3;f[0] = 14, f[1] = 6, f[2] = 2, f[3] = 3, f[4] = 1;memset(a, 0, sizeof(a));a[0][0] = a[0][1] = 1;a[1][0] = a[1][2] = 1;a[2][0] = 1;a[3][0] = 2, a[3][3] = 1;a[4][0] = 2, a[4][3] = a[4][4] = 1;while(n) {if(n & 1) mul1(f, a);mulself1(a);n >>= 1;}}ans = ans * qpow(c, f[0]) % mod;printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的Product Oriented Recurrence(Codeforces Round #566 (Div. 2)E+矩阵快速幂+欧拉降幂)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。