通过这道题成功发现我不会矩乘

答案是一个连分数，看起来不像是一般的数据结构能做的样子，设\(x_{l,r},y_{l,r}\)分别表示\([l,r]\)询问的分子和分母

于是有

\[\frac{x_{l,r}}{y_{l,r}}=a_{l}+\frac{y_{l+1,r}}{x_{l+1,r}}=\frac{y_{l+1,r}+a_l\times x_{l+1,r}}{x_{l+1,r}}\]

这么鬼畜的东西就应该写成矩阵的形式

于是

\[ \begin{bmatrix} a_l& 1\\ 1&0 \end{bmatrix}\times \begin{bmatrix} x_{l+1,r}\\ y_{l+1,r} \end{bmatrix}=\begin{bmatrix} y_{l+1,r}+a_l\times x_{l+1,r}\\ x_{l+1,r} \end{bmatrix}= \begin{bmatrix} x_{l,r}\\ y_{l,r} \end{bmatrix} \]

这是一个\(2\times 2\)的矩阵乘一个\(2\times 1\)的向量，所以必须是矩阵在前去乘向量其实我之前一直把向量写前面

于是对于\(l,r\)这样的一组询问我们要求的就是\(\begin{bmatrix} a_r\\ 1 \end{bmatrix}\)这样一个向量，去乘\(r-1\)到\(l\)这些矩阵，而且必须是从\(r-1\)乘到\(l\)，由于乘完一个矩阵得到的还是一个向量，所以向量还是放在后面，于是根据结合律前面就是从\(l\)乘到\(r-1\)

就是

\[ \begin{bmatrix} a_l& 1\\ 1&0 \end{bmatrix}\times \begin{bmatrix} a_{l+1}& 1\\ 1&0 \end{bmatrix}\times \begin{bmatrix} a_{l+2}& 1\\ 1&0 \end{bmatrix}\times ...\times \begin{bmatrix} a_{r-1}& 1\\ 1&0 \end{bmatrix}\times \begin{bmatrix} a_r\\ 1 \end{bmatrix} \]

于是我们需要查询一个区间内矩阵的乘积，数据范围\(10^6\)，看起来不太好用带\(\log\)的东西维护，于是考虑强行求逆

\(2\times 2\)的逆矩阵手推一下就推出来了，就是\(\begin{bmatrix} 0& 1\\ 1&-a_{l} \end{bmatrix}\)，于是我们再维护一个逆矩阵的前缀积就可以快速查询一个区间了

但是逆矩阵的前缀积需要维护从\(i\)乘到\(1\)的积，矩阵的前缀积需要维护从\(1\)到\(i\)的积，查询的时候也是那逆矩阵的前缀积乘上矩阵前缀积，这样前面才能两两消掉

代码

#include
    
     #define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int maxn=1e6+5;const int mod=998244353;struct mat{int a[2][2];};inline int qm(int x) {return x>=mod?x-mod:x;}inline mat operator*(mat a,mat b) {    mat c;    c.a[0][0]=qm(1ll*a.a[0][0]*b.a[0][0]%mod+1ll*a.a[0][1]*b.a[1][0]%mod);        c.a[0][1]=qm(1ll*a.a[0][0]*b.a[0][1]%mod+1ll*a.a[0][1]*b.a[1][1]%mod);        c.a[1][0]=qm(1ll*a.a[1][0]*b.a[0][0]%mod+1ll*a.a[1][1]*b.a[1][0]%mod);        c.a[1][1]=qm(1ll*a.a[1][0]*b.a[0][1]%mod+1ll*a.a[1][1]*b.a[1][1]%mod);        return c;} inline void out(mat c) {    printf("%d %d\n",c.a[0][0],c.a[0][1]);    printf("%d %d\n",c.a[1][0],c.a[1][1]);    puts("");}mat pre[maxn],inv[maxn];int n,m,type,a[maxn];int main() {    n=read(),m=read(),type=read();    pre[0].a[0][0]=pre[0].a[1][1]=inv[0].a[0][0]=inv[0].a[1][1]=1;    for(re int i=1;i<=n;i++) pre[i].a[0][1]=pre[i].a[1][0]=1;    for(re int i=1;i<=n;i++) inv[i].a[0][1]=inv[i].a[1][0]=1;    for(re int i=1;i<=n;i++) pre[i].a[0][0]=a[i]=read(),inv[i].a[1][1]=qm(mod-a[i]);    for(re int i=1;i<=n;i++) pre[i]=pre[i-1]*pre[i],inv[i]=inv[i]*inv[i-1];    int lstx=0,lsty=0,op,x,l,r;    while(m--) {        op=read();        if(op==1) {            x=read();            if(type) x^=(lstx^lsty);a[++n]=x;            pre[n].a[0][1]=pre[n].a[1][0]=inv[n].a[0][1]=inv[n].a[1][0]=1;            pre[n].a[0][0]=x,inv[n].a[1][1]=qm(mod-x);            pre[n]=pre[n-1]*pre[n],inv[n]=inv[n]*inv[n-1];        }        if(op==2) {            l=read(),r=read();            if(type) l^=(lstx^lsty),r^=(lstx^lsty);            if(l==r) lstx=a[l],lsty=1;            else {                mat c=inv[l-1]*pre[r-1];                lstx=qm(1ll*a[r]*c.a[0][0]%mod+c.a[0][1]);                lsty=qm(1ll*a[r]*c.a[1][0]%mod+c.a[1][1]);            }            printf("%d %d\n",lstx,lsty);        }    }    return 0;}