式子_矩阵快速幂EOJEOJMonthly2021.9SponsoredbyTuSimpleA.AmazingDiscovery

篇首语：本文由编程笔记#小编为大家整理，主要介绍了矩阵快速幂EOJ EOJ Monthly 2021.9 Sponsored by TuSimple A. Amazing Discovery相关的知识，希望对你有一定的参考价值。

Problem A: Amazing Discovery

评测传送门
蒟蒻赛时就开了这么一个题&＃xff0c;推了好久也还是推不出来&＃x1f623;
看了人家官方题解后&＃xff0c;顺利AC。但是&＃xff0c;这个推导过程有点搞怪啊&＃xff0c;不是看了题解&＃xff0c;我还真推不出来这个递推关系。

官方题解&＃xff1a;
题解传送门

下面我提供一些推导过程中的式子&＃xff0c;可自行代入验证一波。
这里提供一个可以进行数学计算的超强&＃x1f449;代数计算工具网站






S


1



&＃61;


2


a



S_1 &＃61;2a


S1​&＃61;2a






S


2



&＃61;


2



a


2



&＃43;


2


b



S_2 &＃61; 2a^2&＃43;2b


S2​&＃61;2a2&＃43;2b






S


3



&＃61;


2



a


3



&＃43;


6


a


b



S_3 &＃61; 2a^3&＃43;6ab


S3​&＃61;2a3&＃43;6ab






S


4



&＃61;


2



a


4



&＃43;


2



b


2



&＃43;


12



a


2



b



S_4 &＃61; 2a^4&＃43;2b^2&＃43;12a^2b


S4​&＃61;2a4&＃43;2b2&＃43;12a2b






S


5



&＃61;


2



a


5



&＃43;


10


a



b


2



&＃43;


20



a


3



b



S_5 &＃61; 2a^5&＃43;10ab^2&＃43;20a^3b


S5​&＃61;2a5&＃43;10ab2&＃43;20a3b






S


5



&＃61;


2


a


∗



S


4



−


(



a


2



−


b


)



S


3




S_5 &＃61; 2a * S_4 - (a^2-b)S_3


S5​&＃61;2a∗S4​−(a2−b)S3​
矩阵快速幂中A矩阵的构造&＃xff1a;





[



S


n



,



S



n


&＃43;


1




]



[S_n,S_n&＃43;1]


[Sn​,Sn&＃43;1​] × $A$ &＃61;




[



S



n


&＃43;


1




,



S



n


&＃43;


2




]



[S_n&＃43;1,S_n&＃43;2]


[Sn&＃43;1​,Sn&＃43;2​]

A


&＃61;







[






0







b


−



a


2










1







2


a







]








A&＃61; \\begingathered \\beginbmatrix 0 & b-a^2 \\\\ 1 & 2a \\endbmatrix \\endgathered


A&＃61;[01​b−a22a​]​
初始矩阵为&＃xff1a;$F0\&＃61;[2,2a]$
之后直接矩阵快速幂计算即可。
AcCoding:

#include
#include
#include <iostream>
#include
using namespace std;
typedef long long ll;
const int mod &＃61; 998244353;
const int N &＃61; 2;
/*
2a * S[n-1] - S[n] &＃61; (a - b * b) * S[n - 2]
f0[2] &＃61; S[n],S[n&＃43;1]
A &＃61;
0,2a,
1,b * b - a
*/
void mul(ll c[][N], ll a[][N], ll b[][N])
static ll tmp[N][N];
memset(tmp, 0, sizeof tmp);
for (int i &＃61; 0;i < N;i&＃43;&＃43;)
for (int j &＃61; 0;j < N;j&＃43;&＃43;)
for (int k &＃61; 0;k < N;k&＃43;&＃43;)
(tmp[i][j] &＃43;&＃61; a[i][k] % mod * b[k][j] % mod) %&＃61; mod;



memcpy(c, tmp, sizeof tmp);

int main()
ll a, b, n; scanf("%lld%lld%lld", &a, &b, &n);
ll f[N][N] &＃61; 2 * a, 2ll * a * a &＃43; 2ll* b ;//n &＃61; 1
ll A[N][N] &＃61;
0,((b - a * a) % mod &＃43; mod) % mod,
1,2ll * a % mod
;
n--;
while (n)
if (n & 1) mul(f, f, A);
mul(A, A, A);
n >>&＃61; 1;

ll res &＃61; (f[0][0] % mod &＃43; mod) % mod;
printf("%lld", res);
return 0;