2.7
闲话
做题纪要
SP26368 PWRANDMOD - Power and Mod
-
龟速乘板子。
点击查看代码
#define ll __int128_t ll read() { ll x=0,f=1; char c=getchar(); while(c>'9'||c<'0') { if(c=='-') { f=-1; } c=getchar(); } while('0'<=c&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } void write(ll x) { if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar((x%10)+'0'); } ll smul(ll a,ll b,ll p) { ll ans=0; while(b>0) { if(b&1) { ans=(ans+a)%p; } b>>=1; a=(a+a)%p; } return ans; } ll qpow(ll a,ll b,ll p) { ll ans=1; while(b>0) { if(b&1) { ans=smul(ans,a,p); } b>>=1; a=smul(a,a,p); } return ans; } int main() { ll t,a,b,p,i; t=read(); for(i=1;i<=t;i++) { a=read(); b=read(); p=read(); write(qpow(a,b,p)); cout<<endl; } return 0; }
SP277 CTGAME - City Game
2.8
闲话
做题纪要
2.9
闲话
做题纪要
luogu P2440 木材加工
-
简单的二分答案，为什么我考场上没有看出来醉了。
-
注意可能会出现除数为 \(0\) 的情况，即 \(mid=\left\lfloor\dfrac{0+1}{2}\right\rfloor=0\) 时。将二分左端点初始化为 \(1\) 或对 \(mid=0\) 进行特判即可。
点击查看代码
int a[1000001]; bool check(int mid,int n,int m) { int sum=0,i; for(i=1;i<=n;i++) { sum+=a[i]/mid; } return sum>=m; } int main() { int n,m,ans,l=1,r=0,mid,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; r=max(r,a[i]); } while(l<=r) { mid=(l+r)/2; if(check(mid,n,m)==true) { ans=mid; l=mid+1; } else { r=mid-1; } } cout<<ans<<endl; return 0; }
CF1331G Lingua Romana
-
愚人节的题，建议去看官方题解要简化题意。
点击查看代码
double a[1001]; int main() { int i; for(i=1;i<=11;i++) { cin>>a[i]; } for(i=11;i>=1;i--) { if(a[i]<5) { printf("f(%.0lf) = %.2lf\n",a[i],5*a[i]*a[i]*a[i]+sqrt(abs(a[i]))); } else { printf("f(%.0lf) = MAGNA NIMIS!\n",a[i]); } } return 0; }
2.10
闲话
做题纪要
HZOJ 863. 金牌
- 详见 2024初三年前集训测试2 T4 金牌 。
luogu P8670 [蓝桥杯 2018 国 B] 矩阵求和
2.11
闲话
做题纪要
luogu P4783 【模板】矩阵求逆
-
矩阵求逆板子。
-
若对于矩阵 \(A\) 存在一个矩阵 \(A^{-1}\) 使得 \(A \times A^{-1}=I\) 且 \(A^{-1} \times A =I\) ，其中 \(I\) 为单位矩阵 \(I= \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}\) ，则称 \(A\) 是可逆的且逆是唯一的， \(A^{-1}\) 为 \(A\) 的逆矩阵。
-
已知 \(\begin{bmatrix} A & I \end{bmatrix}\) ，考虑将其变成 \(\begin{bmatrix} I & A^{-1} \end{bmatrix}\) 。第一种方法是 \(\begin{bmatrix} A & I \end{bmatrix} \times A^{-1}= \begin{bmatrix} I & A^{-1} \end{bmatrix}\) ；另一种方法是对 \(A\) 进行高斯消元，使其变成系数为 \(1\) 的对角矩阵，变成 \(\begin{bmatrix} I & A^{-1} \end{bmatrix}\) 。
点击查看代码
ll a[1001][1001]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b>0) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int main() { ll n,inv,val=0,flag=0,i,j,k,p=1000000007; cin>>n; for(i=1;i<=n;i++) { a[i][i+n]=1; for(j=1;j<=n;j++) { cin>>a[i][j]; } } for(i=1;i<=n;i++) { val=i; for(j=i+1;j<=n;j++) { if(abs(a[j][i])-abs(a[val][i])>0) { val=j; } } for(j=1;j<=2*n;j++) { swap(a[i][j],a[val][j]); } if(a[i][i]==0) { flag=1; cout<<"No Solution"<<endl; break; } else { inv=qpow(a[i][i],p-2,p); for(j=1;j<=n;j++) { if(j!=i) { for(k=i+1;k<=2*n;k++) { a[j][k]=(a[j][k]-a[i][k]*(a[j][i]*inv%p)%p+p)%p; } } } for(j=1;j<=2*n;j++) { a[i][j]=a[i][j]*inv%p; } } } if(flag==0) { for(i=1;i<=n;i++) { for(j=n+1;j<=2*n;j++) { cout<<a[i][j]<<" "; } cout<<endl; } } return 0; }
2.12
闲话
做题纪要
luogu P2044 [NOI2012] 随机数生成器
-
令 \(F_{n}=\begin{bmatrix} x_{n} & c \end{bmatrix}\) ，容易有 \(\begin{aligned} F_{n} &=\begin{bmatrix} x_{n} & c \end{bmatrix} \\ &=\begin{bmatrix} x_{n-1} & c \end{bmatrix} \times \begin{bmatrix} a & 0 \\ 1 & 1 \end{bmatrix} \\ &=\begin{bmatrix} x_{n-2} & c \end{bmatrix} \times \begin{bmatrix} a & 0 \\ 1 & 1 \end{bmatrix}^{2} \\ &=\begin{bmatrix} x_{n-3} & c \end{bmatrix} \times \begin{bmatrix} a & 0 \\ 1 & 1 \end{bmatrix}^{3} \\ &=\dots \\ &=\begin{bmatrix} x_{0} & c \end{bmatrix} \times \begin{bmatrix} a & 0 \\ 1 & 1 \end{bmatrix}^{n} \\ &=F_{0} \times \begin{bmatrix} a & 0 \\ 1 & 1 \end{bmatrix}^{n} \end{aligned}\) 。
点击查看代码
struct Matrix { ll ma[5][5]; Matrix() { memset(ma,0,sizeof(ma)); } }f,a; ll read() { ll x=0,f=1; char c=getchar(); while(c>'9'||c<'0') { if(c=='-') { f=-1; } c=getchar(); } while('0'<=c&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } void write(ll x) { if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar((x%10)+'0'); } Matrix mul(Matrix a,Matrix b,ll n,ll m,ll k,ll p) { Matrix c; for(ll i=1;i<=n;i++) { for(ll j=1;j<=k;j++) { for(ll h=1;h<=m;h++) { c.ma[i][j]=(c.ma[i][j]+(a.ma[i][h]%p)*(b.ma[h][j]%p)%p)%p; } } } return c; } Matrix qpow(Matrix a,ll b,ll p,ll n) { Matrix ans; for(ll i=1;i<=n;i++) { ans.ma[i][i]=1; } while(b>0) { if(b&1) { ans=mul(ans,a,n,n,n,p); } b>>=1; a=mul(a,a,n,n,n,p); } return ans; } int main() { ll p,b,g,n=1,m=2,k=2; p=read(); a.ma[1][1]=read(); f.ma[1][2]=read(); f.ma[1][1]=read(); b=read(); g=read(); a.ma[1][2]=0; a.ma[2][1]=a.ma[2][2]=1; write(mul(f,qpow(a,b,p,m),n,m,k,p).ma[1][1]%g); return 0; }
BZOJ4128 Matrix
-
用
map重载运算符即可。 -
因常数巨大，故尽可能减少 \(BSGS\) 中多次矩阵快速幂的使用。
点击查看代码
ll n; struct Matrix { ll ma[80][80]; Matrix() { memset(ma,0,sizeof(ma)); } bool operator < (Matrix another) const { for(ll i=1;i<=n;i++) { for(ll j=1;j<=n;j++) { if(ma[i][j]<another.ma[i][j]) { return true; } if(ma[i][j]>another.ma[i][j]) { return false; } } } return false; } }a,b; Matrix mul(Matrix a,Matrix b,ll n,ll m,ll k,ll p) { Matrix c; for(ll i=1;i<=n;i++) { for(ll j=1;j<=k;j++) { for(ll h=1;h<=m;h++) { c.ma[i][j]=(c.ma[i][j]+a.ma[i][h]*b.ma[h][j]%p)%p; } } } return c; } Matrix qpow(Matrix a,ll b,ll p,ll n) { Matrix ans; for(ll i=1;i<=n;i++) { ans.ma[i][i]=1; } while(b>0) { if(b&1) { ans=mul(ans,a,n,n,n,p); } b>>=1; a=mul(a,a,n,n,n,p); } return ans; } ll bsgs(Matrix a,Matrix b,ll p,ll n) { map<Matrix,ll>vis; ll k=sqrt(p)+1,i; Matrix sum; for(i=0;i<=k-1;i++) { b=(i==0)?b:mul(b,a,n,n,n,p); vis[b]=i; } a=qpow(a,k,p,n); for(i=1;i<=n;i++) { sum.ma[i][i]=1; } for(i=0;i<=k;i++) { sum=(i==0)?sum:mul(sum,a,n,n,n,p); if(vis.find(sum)!=vis.end()) { if(i*k-vis[sum]>=0) { return i*k-vis[sum]; } } } return -1; } int main() { ll p,i,j; cin>>n>>p; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cin>>a.ma[i][j]; a.ma[i][j]%=p; } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cin>>b.ma[i][j]; b.ma[i][j]%=p; } } cout<<bsgs(a,b,p,n)<<endl; return 0; }
luogu P3216 [HNOI2011]数学作业
luogu P4159 [SCOI2009] 迷路
- 令 \(f_{i,j}\) 表示第 \(i\) 时刻走到 \(j\) 的不同路径数量。状态转移方程为 \(f_{i,j}=\sum\limits_{(k,j) \in E}^{}[i-dis_{k,j} \ge 0] \times f_{i-dis_{k,j},k}\) ；特别地，规定 \(f_{0,1}=1\) 。