LibreOJ NOI Round #2 Day1 T1。
题目链接:LOJ 573。
题目
题目描述
数据范围
时空限制
题解
思路
考虑到可以把分数 \(\frac{x}{y}\) 表示成一个矩阵 \(\begin{bmatrix}x\\y\end{bmatrix}\)。
我们从不难发现
\[
\frac{a _r}{1}\Rightarrow\begin{bmatrix}a _ {r-1}&1\\1&0\end{bmatrix}\begin{bmatrix}a _ r\\1\end{bmatrix}=\begin{bmatrix}a _ {r-1}a _ r+1\\a _ r\end{bmatrix}\Rightarrow\frac{a _ {r-1}a _ r+1}{a _ r}=a _ {r-1}+\frac{1}{a _ r}
\]
这后面就很简单了。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=5e5+5; const int MAXM=5e5+5; const int MAXSIZE=2; const int p=998244353; inline int add(reg int a,reg int b){ reg int sum=a+b; return sum>=p?sum-p:sum; } inline int mul(reg int a,reg int b){ return 1ll*a*b%p; } struct Matrix{ int unit[MAXSIZE][MAXSIZE]; inline Matrix(void){ return; } inline Matrix(reg int x){ for(reg int i=0;i<MAXSIZE;++i) for(reg int j=0;j<MAXSIZE;++j) unit[i][j]=(i==j)?x:0; return; } inline Matrix operator*(const Matrix& a){ Matrix res(0); for(reg int i=0;i<MAXSIZE;++i) for(reg int k=0;k<MAXSIZE;++k){ reg int r=unit[i][k]; for(reg int j=0;j<MAXSIZE;++j) res[i][j]=add(res[i][j],mul(r,a.unit[k][j])); } return res; } inline int* operator[](reg int i){ return unit[i]; } inline void print(void){ for(reg int i=0;i<MAXSIZE;++i) for(reg int j=0;j<MAXSIZE;++j) printf("%d%c",unit[i][j],j==MAXSIZE-1?'\n':' '); return; } }; int n,m,type; int a[MAXN+MAXM]; Matrix pre[MAXN+MAXM],inv[MAXN+MAXM]; int main(void){ n=read(),m=read(),type=read(); pre[0]=inv[0]=Matrix(1); for(reg int i=1;i<=n;++i){ a[i]=read(); static Matrix f,invf; f[0][0]=a[i],f[0][1]=f[1][0]=1,f[1][1]=0; invf[0][0]=0,invf[0][1]=invf[1][0]=1,invf[1][1]=add(0,p-a[i]); pre[i]=pre[i-1]*f; inv[i]=invf*inv[i-1]; } reg int lastans=0; while(m--){ static int opt,l,r; opt=read(); switch(opt){ case 1:{ a[++n]=read()^lastans; Matrix f,invf; f[0][0]=a[n],f[0][1]=f[1][0]=1,f[1][1]=0; invf[0][0]=0,invf[0][1]=invf[1][0]=1,invf[1][1]=add(0,p-a[n]); pre[n]=pre[n-1]*f; inv[n]=invf*inv[n-1]; break; } case 2:{ l=read()^lastans,r=read()^lastans; Matrix f,base,ans; f=inv[l-1]*pre[r]; base[0][0]=1,base[0][1]=base[1][0]=base[1][1]=0; ans=f*base; printf("%d %d\n",ans[0][0],ans[1][0]); lastans=type*(ans[0][0]^ans[1][0]); break; } } } return 0; }
近期评论