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/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]; ...

題目連結: http://tioj.infor.org/problems/1146 這題其實跟 [TIOJ]1428 很像，只是他不能快速冪，而是要$O(n)$做矩陣乘法，然後每次做完後就把答案加起來 #include <stdio.h> #include <algorithm> int size; auto graph = new int[35][35]; auto temp = new int[35][35]; inline void matrixTimes(int [][35], int[][35], int[][35]); int main(){ scanf("%d",&size); for(int i=0;i<size;i++){ char inp[35]; scanf("%s",inp); for(int j=0;j<size;j++){ temp[i][j]=i==j; graph[i][j]=inp[j]-'0'; } } int x,y,n,ans=0; scanf("%d\n%d\n%d",&x,&y,&n); while(n){ auto tp = new int[35][35]; matrixTimes(graph,temp,tp); std::swap(tp,temp); ans+=temp[x-1][y-1]; n--; } printf("%d",ans); return 0; } inline void matrixTimes(int a[][35], int b[][35], int...

題目連結: http://tioj.infor.org/problems/1428 其實鄰接矩陣除了MLE外其實還有個功能，那就是你可以直接把他n次方，得到的就是任意兩點走n步有幾種走法的答案，然後n次方都可以用快速冪，所以這題其實就把圖用鄰接矩陣存起來，然後快速冪，複雜度$O(N^3 \log_2{L})$ #include <stdio.h> #include <algorithm> typedef long long lld; int n,m,q,l; auto graph = new lld[160][160]; auto temp0 = new lld[160][160]; auto temp1 = new lld[160][160]; inline void matrixTime(lld [][160],lld [][160],lld [][160]); int main(){ scanf("%d %d %d %d",&n,&m,&q,&l); for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ graph[j][k]=(j==k)?1:0; } } for(int i=0;i<m;i++){ int s,e; scanf("%d %d",&s,&e); temp0[s][e]++; } bool which=0; while(l){ if(l&1){ auto tp = new lld[160][160]; matrixTime(graph,which?temp1:temp0,tp); std::swap(t...

題目連結: 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;...