ZROI#1119
看起来非常怪异...因为之前知道 (Fibonacii) 数列有通项公式,所以就一直以为这题是 (F) 的递推转通项...
万万没想到,这竟然是个矩阵加速递推...
(⑧) 说了,伤心,直接上式子:
[egin{aligned} F_{n} &=sum_{i=0}^{n} f_{i} f_{n-i} \ &=sum_{i=0}^{n}left(f_{i-1}+f_{i-2}
ight) f_{n-i}+f_{1} f_{n-1}+f_{0} f_{n} \ &=sum_{i=0}^{n-1} f_{i} f_{n-i-1}-f_{0} f_{n-1}+sum_{i=0}^{n-2} f_{i} f_{n-i-2}+f_{1} f_{n-1}+f_{0} f_{n} \ &=F_{n-1}+F_{n-2}+f_{1} f_{n-1}-f_{0} f_{n-1}+f_{0} f_{n} \ &=F_{n-1}+F_{n-2}+f_{n} end{aligned}
]
所以我们有了递推公式,我们发现这个递推公式是和 (F) 以及 (f) 的相邻两项相关的,所以我们的初始矩阵和目标矩阵应保留至少四维状态.
而因为答案要求的是 (F) 的前缀和,所以要多加一维用以辅助递推,于是我们的转移矩阵应该是 (5 imes 5) 的.
我们发现这个初始矩阵和目标矩阵应该是这个亚子:
[left[egin{array}{lllll}{?} & {?} & {?} & {?} & {?} \ {?} & {?} & {?} & {?} & {?} \ {?} & {?} & {?} & {?} & {?} \ {?} & {?} & {?} & {?} & {?} \ {?} & {?} & {?} & {?} & {?}end{array}
ight]left[egin{array}{c}{F_{i}} \ {F_{i-1}} \ {f_{i}} \ {f_{i-1}} \ {a n s_{i}}end{array}
ight]=left[egin{array}{c}{F_{i+1}} \ {F_{i}} \ {f_{i+1}} \ {f_{i}} \ {a n s_{i+1}}end{array}
ight]
]
问号矩阵是我们要推导的转移矩阵.
经过推导,可以得到转移矩阵是这样的:
[left[egin{array}{lllll}{1} & {1} & {0} & {0} & {1} \ {1} & {0} & {0} & {0} & {1} \ {1} & {0} & {1} & {1} & {1} \ {1} & {0} & {1} & {0} & {1} \ {0} & {0} & {0} & {0} & {1}end{array}
ight]left[egin{array}{c}{F_{i}} \ {F_{i-1}} \ {f_{i}} \ {f_{i-1}} \ {a n s_{i}}end{array}
ight]=left[egin{array}{c}{F_{i+1}} \ {F_{i}} \ {f_{i+1}} \ {f_{i}} \ {a n s_{i+1}}end{array}
ight]
]
至于如何推导,我还会有一篇博文专门讲解如何推导一个矩阵,在此不再赘述.
直接快乐地上一个矩阵快速幂即可.
初始矩阵是 (1 imes 5) 的 (:{2,1,1,1,3}.)
需要注意的是,因为初始矩阵是从第一项开始的,每乘一次转移矩阵向后递推一次,所以我们需要的转移次数是 (n-1) 的.
愉快(AC!).
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define rll read<LL>
#define LL long long
#define pb push_back
#define db double
#define mid ( ( l + r ) >> 1 )
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int mod = 998244353 ;
struct Matrix {
LL e[5][5] , line , row ;
inline void clear () { line = row = 0 ; MEM ( e , 0 ) ; return ; }
friend Matrix operator * (Matrix a , Matrix b) {
Matrix c ; c.clear () ; c.line = a.line ; c.row = b.row ;
rep ( k , 0 , a.row - 1 ) rep ( i , 0 , a.line - 1 ) rep ( j , 0 , b.row - 1 )
c.e[i][j] = ( c.e[i][j] + a.e[i][k] * b.e[k][j] % mod ) % mod ;
return c ;
}
} ;
inline Matrix quick (Matrix a , LL p) {
Matrix c ; c.clear () ; c.line = a.line ; c.row = a.row ;
rep ( i , 0 , c.line - 1 ) c.e[i][i] = 1 ;
while ( p ) {
if ( p & 1 ) c = c * a ;
a = a * a ; p >>= 1 ;
}
return c ;
}
LL n , k ; Matrix p ;
int main(){
n = rll () ; p.clear () ;
p.e[0][0] = p.e[1][0] = p.e[2][0] = 1 ;
p.e[3][0] = p.e[0][1] = p.e[2][2] = 1 ;
p.e[3][2] = p.e[0][4] = p.e[1][4] = 1 ;
p.e[2][4] = p.e[3][4] = p.e[4][4] = 1 ;
p.e[2][3] = 1 ; p.line = 5 ; p.row = 5 ;
Matrix ans = quick ( p , n - 1ll ) ; ;
Matrix pri ; pri.clear () ;
pri.line = 1 ; pri.row = 5 ;
pri.e[0][0] = 2 ; pri.e[0][1] = 1 ;
pri.e[0][2] = 1 ; pri.e[0][3] = 1 ;
pri.e[0][4] = 3 ; ans = pri * ans ;
printf ("%lld
" , ans.e[0][4] ) ;
system ("pause") ; return 0 ;
}