oToToT的code收藏區

題目連結: http://poj.org/problem?id=3233 其實看到的時候以為是要用等比級數的公式，可是馬上就發現兩個會慘的點1.不保證有反矩陣, 2.不保證有些東西模m有反元素。後來被提示了才知道原來其實是用DP的想法找的轉移矩陣，然後對他快速冪。稍微列一下式就會得到$ \begin{bmatrix} S_i \\ A_i \end{bmatrix} = \begin{bmatrix} I \cdot S_{i-1}+A \cdot A_{i-1} \\ 0 \cdot S_{i-1}+A \cdot A_{i-1} \end{bmatrix} = \begin{bmatrix} I & A \\ 0 & A \end{bmatrix} \cdot \begin{bmatrix} S_{i-1} \\ A_{i-1} \end{bmatrix} $，所以就照著這個跑就好了。 #include <iostream> using namespace std; const int N = 60 + 2; int (*A)[N] = new int[N][N]; int (*Mtx)[N] = new int[N][N]; int (*Temp)[N] = new int[N][N]; int (*Ans)[N] = new int[N][N]; int (*Res)[N] = new int[N][N]; int n, m, n2; inline void mTimes(int[N][N],int[N][N],int[N][N],int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int k; cin>>n>>k>>m; n2 = n<<1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>A[i][j]; for...

題目連結: http://tioj.infor.org/problems/1331 看一眼大概就可以發現這就是一個經典的矩陣優化DP的題目，稍微算一下後得到轉移矩陣$ \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix} $，所以要求$a_n$其實就是算$ \begin{bmatrix} a_0 & a_1 \\ \end{bmatrix} \times \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix}^n = \begin{bmatrix} a_n & a_{n+1} \\ \end{bmatrix}$ ，然後冪次的部分用快速冪解決。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef unsigned long long llu; const llu mod = 1LL<<32; auto A = new llu[2][2]; auto B = new llu[2][2]; auto C = new llu[2][2]; auto F = new llu[2][2]; void mTimes(llu[2][2],llu[2][2],llu[2][2],int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); lld n, a, b, x, y; while(cin>>n, n>=0){ cin>>a>>b>>x>>y; F[0][0]=a; F[0][1]=b; A[0][0]=0; A[0][1]=x; A[1][0]=1; A[1][1]=y; B[0][0]=...

題目連結: http://tioj.infor.org/problems/1199 枚舉x並且用快速冪加速次方的地方，就可以做到$O(y log n)$了。 #include <bits/stdc++.h> using namespace std; int qPow(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int a, n, y; while(cin>>a>>n>>y, a or n or y){ int ans=0; for(int i=0;i<=y-1;i++){ if(n==0 and i==0) continue; if(qPow(i, n, y)==a) ans++; } cout<<ans<<'\n'; } return 0; } int qPow(int a, int b, int m){ int r=1; while(b){ if(b&1) r=(r*a)%m; b>>=1; a=(a*a)%m; } return r%m; }

題目連結: http://tioj.infor.org/problems/1136 因為我們知道若把圖用鄰接矩陣存下來，他的t次方就是走t步後有幾種走法，所以就可以看下面的做法做了。 本題要求的其實就是從所有a($0 \leq a \leq n$)開始走到x的機率和最後再除以n，但是顯然直接乘再算機率會overflow(除非你寫大數)，所以有個比較方便的技巧就是一開始就算機率，之後做矩陣乘法的時候就不會因此而overflow了，大概這樣就可以AC了吧 #include <bits/stdc++.h> using namespace std; typedef double lf; typedef long long lld; #define N 100 auto m1 = new lf[N+10][N+10]; auto m2 = new lf[N+10][N+10]; auto m3 = new lf[N+10][N+10]; lld mm[N+10][N+10]; inline void mTimes(lf[][N+10],lf[][N+10],lf[][N+10]); int n,t; int main(){ scanf("%d%d",&n,&t); while(n+t!=0){ for(int i=0;i<n;i++)for(int j=0;j<n;j++)m1[i][j]=m2[i][j]=m3[i][j]=mm[i][j]=0; int x; scanf("%d",&x); while(x--){ int s,t; scanf("%d%d",&s,&t); s--,t--; mm[s][t]=1; mm[t][s]=1;...

題目連結: http://tioj.infor.org/problems/1354 因為不確定題目的範圍所以先開個long long壓壓驚(?，這題也是一樣，矩陣乘法快速冪，因為把圖用鄰接矩陣存下來後，其的n次方就是任意點走到任一點走n步的可能方法總數。只是因為也不確定題目給的n是否遞增，所以就把他排個序，然後再做矩陣快速冪，理論上應該會比較快(?，複雜度$O(t log_2 t + log_2 n)$ #include <stdio.h> #include <algorithm> typedef long long lld; inline void gn(lld &_){_=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar();} using std::sort; using std::swap; struct inp{ lld i, val; }; inline void matrixTimes(lld [][4],lld [][4],lld [][4]); bool cmp(inp a,inp b){ return a.val<b.val; } int main(){ lld n; gn(n); auto v = new inp[n]; auto ans = new lld[n]; for(lld i=0;i<n;i++){ v[i].i=i; gn(v[i].val); } sort(v,v+n,cmp); inp k = v[0]; auto matrix = new lld[4][4]; auto ta = new lld[4][4]; ...

題目連結: https://ioj.infor.org/problems/14 由題目可看出這是一個標準的線性遞迴，而居然是線性遞迴的話，那都可以用矩陣乘法搭配快速冪來讓時間複雜度降到$O(m^3 \log_2{(n-m)})$，然後不難發現其要用的$1 \times m$橫矩陣是$\left( \begin{array}{clr} 1 & 1 & \cdots & 1 \end{array} \right)$，而$m \times m$正方形矩陣則是$\left( \begin{array}{clr} k_{1} & 1 & 0 & 0 & \cdots \\ k_{2} & 0 & 1 & 0 & \cdots \\ k_{3} & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ k_{m} & 0 & 0 & 0 & \cdots \end{array} \right)$至於會溢位的部分則按照題敘，每次在做加法乘法之類的時候都模一次$10^9+7$，因為可以證明先算再模跟先模再算再模都會得到相同的結果的。 #include <stdio.h> #include <algorithm> typedef long long lld; const lld mmdd = 1000000007; lld m1[110][110]={0}; auto aas = new lld [110][110]; lld n,m; void qPow(lld); void matrixTimes(lld[][110],lld[][110],lld[][110]); int main(){ scanf("%lld %lld",&n,&m); for(lld i=0;i<m;i++){ scanf("%lld",&m1[i][0]); if(i+1<m) m1[i][i+1] = 1;...