求助矩阵加速！WA 8个点只有20pts
查看原帖
求助矩阵加速！WA 8个点只有20pts
167101
zhouj2006楼主2020/5/11 09:16

这题我构造的初始矩阵是

p&q \\1&0 \end{bmatrix}$$ 然后对这个初始矩阵快速幂(n-2)，最后乘上 $$\begin{bmatrix} a_2 \\a_1 \end{bmatrix}$$ 然后输出结果矩阵的`a[1][1]`。 似乎没什么问题吧…… 但是只有20分，WA 8个点QAQ 代码如下，求大佬帮忙调一下 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=40; inline ll read() { char c;ll res=0; for(;!isdigit(c);c=getchar()); for(;isdigit(c);c=getchar())res=(res<<3)+(res<<1)+(c^48); return res; } ll p,q,a1,a2,n,MOD; struct Mat { ll a[N][N]; int n,m; Mat() { n=m=0; memset(a,0,sizeof a); } Mat(int x) { n=m=x; memset(a,0,sizeof a); for(int i=1;i<=n;i++) a[i][i]=1; } Mat(int x,int y) { n=x,m=y; memset(a,0,sizeof a); } Mat operator *(Mat b) { Mat c(n,b.m); for(int i=1;i<=c.n;i++) { for(int j=1;j<=c.m;j++) { for(int k=1;k<=m;k++) { c.a[i][j]=(c.a[i][j]+(a[i][k]*b.a[k][j])%MOD)%MOD; } } } return c; } Mat operator *=(Mat c) { return *this=*this*c; } Mat operator ^(ll c) { Mat t=*this; Mat ans(m); while(c) { if(c&1) ans*=t; t*=t; c>>=1; } return ans; } Mat operator ^=(ll c) { return *this=*this^c; } }; int main() { p=read(),q=read(),a1=read(),a2=read(),n=read(),MOD=read(); if(n==1)return printf("%d\n",a1%MOD)&0; if(n==2)return printf("%d\n",a2%MOD)&0; Mat res(2,2); res.a[1][1]=p,res.a[1][2]=q,res.a[2][1]=1; Mat p(2,1); p.a[1][1]=a2,p.a[2][1]=a1; res^=(n-2); p*=res; cout<<p.a[1][1]<<endl; return 0; } ```
2020/5/11 09:16