特殊矩阵の压缩存储
inoichi_lim
2020-04-04 16:09:32
矩阵图像如下所示。
$\begin{vmatrix}a_{11}&a_{12}&...&a_{1n}\\a_{21}&a_{22}&...&a_{2n}\\...\\a_{n1}&a_{n2}&...&a_{nn}\end{vmatrix}$
共$N\times N$个元素。
### 1. 对称矩阵：
- 一个$n$行$n$列对称矩阵图像特点如下所示：
1. $a_{ij}=a_{ji}(i,j\le n)$。
2. 图像可分为上三角和下三角，两个三角图案全等。
下三角（$i\ge j$）：
$\begin{vmatrix}a_{11}\\a_{21}&a_{22}\\a_{31}&a_{32}&a_{33}\\...\\a_{n1}&a_{n2}&a_{n3}&...&a_{nn}\end{vmatrix}$
上三角（$i<j$）的图差不多就不画了。
我们假设存储下三角的一维数组 **（需要$\frac{N\times(N+1)}{2}$的空间，压缩了一半）** 是数组$b$，且数组下标从$1$开始。
那么我们的$a_{ij}$存到$b$数组里的$k$（也是从$1$开始）和$i,j$有以下关系：
$$k=\frac{(i-1)*n}{2}+j$$
第一部分$\frac{(i-1)*n}{2}$指$\begin{vmatrix}a_{11}\\a_{21}&a_{22}\\a_{31}&a_{32}&a_{33}\\...\\a_{i1}&a_{i-1,2}&a_{i-1,3}&...&a_{i-1,j-1}\end{vmatrix}$的元素个数。
第二部分$j$指第$i$行还有第$j$个。
以存储下三角为例，代码：
```cpp
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=0x7f7f7f7f;
int n,q,a,downsj[N*(N+1)/2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
fs(i,1,n,1){
fs(j,1,n,1){
cin>>a;
if(i>=j){
downsj[i*(i-1)/2+j]=a;
}
}
}
fs(i,1,q,1){
int x,y;
cin>>x>>y;
if(x<y) swap(x,y);
cout<<downsj[x*(x-1)/2+y]<<endl;
}
return 0;
}
```
### 2. 三角矩阵
三角矩阵分为上三角矩阵和下三角矩阵，这里以**下三角**为例。
- 一个$n$行$n$列**下三角**矩阵图像特点如下所示：
- 若$i<j,a_{ij}=c(i,j\le n)$（$c$是**常数**）。
$\begin{vmatrix}a_{11}&c&...&c\\a_{21}&a_{22}&...&c\\...\\a_{n1}&a_{n2}&...&a_{nn}\end{vmatrix}$
存储方法：
和对称矩阵相同，存储下三角，在询问时若询问上三角就直接回答上三角即可。
以存储下三角为例，代码：
```cpp
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=0x7f7f7f7f;
int n,q,a,downsj[N*(N+1)/2],c;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
fs(i,1,n,1){
fs(j,1,n,1){
cin>>a;
if(i>=j){
downsj[i*(i-1)/2+j]=a;
}else{
c=a;
}
}
}
fs(i,1,q,1){
int x,y;
cin>>x>>y;
if(x<y) cout<<c<<endl;
else cout<<downsj[x*(x-1)/2+y]<<endl;
}
return 0;
}
```
那么上三角呢？
我们观察这个矩阵。
$\begin{vmatrix}a_{11}&a_{12}&a_{13}&...&a_{1n}\\c&a_{22}&a_{23}&...&a_{2n}\\c&c&a_{33}&...&a_{3n}\\...\\c&c&c&...&a_{nn}\end{vmatrix}$
会发现，若$i>j,$则$a_{ij}=c$。
否则，$i\le j,$则$k$和$i,j$的关系如下所示：
$$k=\frac{(n-i+2+n)\times(i-1)}{2}+j-i+1=\frac{(i-1)\times(2n-i+2)}{2}+j-i+1$$
- 第一部分$\frac{(n-i+2+n)\times(i-1)}{2}$指代$\begin{vmatrix}a_{11}&a_{12}&a_{13}&...&a_{1n}\\c&a_{22}&a_{23}&...&a_{2n}\\c&c&a_{i-1,3}&...&a_{i-1,n}\end{vmatrix}$中，$a_{...}$的个数。
- 第二部分$j-i+1$为$\begin{vmatrix}c&c&...&a_{i,i}&a_{i,i+1}&...&a_{i,j-1}&a_{i,j}\end{vmatrix}$中$i,j$中的个数。
代码：
```cpp
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=0x7f7f7f7f;
int n,q,a,downsj[N*(N+1)/2],c;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
fs(i,1,n,1){
fs(j,1,n,1){
cin>>a;
if(i>j){
c=a;
}else{
downsj[(2*n-i+2)*(i-1)/2+j-i+1]=a;
}
}
}
fs(i,1,q,1){
int x,y;
cin>>x>>y;
if(x>y) cout<<c<<endl;
else cout<<downsj[(2*n-x+2)*(x-1)/2+y-x+1]<<endl;
}
return 0;
}
```
### 3. 对角矩阵
对角矩阵的特点如下：
- 基本所有非$c$元素集结在对角线旁，共$l$条对角线（$l\bmod2=1$），称为$l$对角矩阵。
则半带宽$d=\frac{l+1}{2}$。
矩阵如下所示：$\begin{vmatrix}a_{11}&a_{12}&...&c&c&...&c\\a_{21}&a_{22}&...&c&c&...&c\\c&a_{32}&a_{33}&a_{34}&c&...&c\\...\\c&c&c&c&...&a_{n-1,n}&a_{nn}\end{vmatrix}$
存储方法：
- 总共需要$l\times n-2\times d$空间。
- 对于每一条对角线，先补上$0$直到有意义的每一行长度都是$l$。
- Pass掉$1$行前面的$d$个$0$和$n$行最后的$d$个$0$。
- 公式如下所示（~~其实我也没理解，老师还打错了，还讲的好好的~~）：
$$k=\begin{cases}(i-1)\times l+j-i&|i-j|<d\\c&|i-j|\ge d\end{cases}$$
代码：
```cpp
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1001,inf=0x7f7f7f7f;
int n,q,a,downsj[N*N-2*N],c,d,l;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q>>l;d=(l+1)/2;
fs(i,1,n,1){
fs(j,1,n,1){
cin>>a;
if(abs(i-j)>=d){
c=a;
}else{
downsj[(i-1)*l+j-i]=a;
}
}
}
fs(i,1,q,1){
int x,y;
cin>>x>>y;
if(abs(x-y)>=d) cout<<c<<endl;
else cout<<downsj[(x-1)*l+y-x]<<endl;
}
return 0;
}
```