---

線性空間

定義

線性空間是一個關于一下兩個運算封閉的向量集合：
\(1.\)向量加法\(a+b\)，其中\(a,b\)為向量
\(2.\)標量乘法\(k*a\)，其中\(a\)為向量，\(k\)為常數

基礎概念

\(1.\)給定若干個向量\(a_1,a_2,...,a_n\)，若向量\(b\)能夠通過\(a_1,a_2,...,a_n\)經過向量加法和標量乘法得到，則稱向量\(b\)能夠通過\(a_1,a_2,...,a_n\)表出。

\(2.\)對于向量\(a_1,a_2,...,a_n\)能夠表出的所有向量所構成了一個線性空間，稱\(a_1,a_2,...,a_n\)為這個線性空間的生成子集。

\(3.\)在一個線性空間中選取若干個向量，若一個向量能夠被其他向量表出，則稱這些向量線性相關，反之，稱這些向量線性無關。

\(4.\)線性無關的生成子集成為線性空間的基底，簡稱基。

\(4'.\)另外地，線性空間的極大線性無關子集也稱為線性空間的基底，簡稱基。

\(5.\)一個線性空間的所有基包含的向量個數都相等，這個個數稱為線性空間的維數。

高斯消元和線性基

對于一個\(n*m\)的矩陣，我們可以把它看做\(n\)個長度為\(m\)的向量，即它的維數為\(m\)。那么如果將這個矩陣看做系數矩陣進行高斯消元，則消元后得到的矩陣中所有非\(0\)行代表的向量線性無關。

因為初等行變換就是對每行的向量之間進行向量加法和標量乘法，所以高斯消元的操作并不改變\(n\)個向量所能表出的線性空間，則消元后的矩陣的所有非\(0\)行所代表的向量就是原線性空間的一個基。

綜上所述，我們可以利用高斯消元算法對若干個向量求解其構成線性空間的一個基。

裝備購買

Description

臉哥最近在玩一款神奇的游戲，這個游戲里有 n 件裝備，每件裝備有 m 個屬性，用向量zi(aj ,.....,am) 表示 (1 <= i <= n; 1 <= j <= m)，每個裝備需要花費 ci，現在臉哥想買一些裝備，但是臉哥很窮，所以總是盤算著 怎樣才能花盡量少的錢買盡量多的裝備。對于臉哥來說，如果一件裝備的屬性能用購買的其他裝備組合出（也就是 說臉哥可以利用手上的這些裝備組合出這件裝備的效果），那么這件裝備就沒有買的必要了。嚴格的定義是，如果 臉哥買了 zi1,.....zip這 p 件裝備，那么對于任意待決定的 zh，不存在 b1,....,bp 使得 b1zi1 + ... + bpzi p = zh（b 是實數），那么臉哥就會買 zh，否則 zh 對臉哥就是無用的了，自然不必購買。舉個例子,z1 =(1; 2; 3);z2 =(3; 4; 5);zh =(2; 3; 4)，b1 =1/2，b2 =1/2，就有 b1z1 + b2z2 = zh，那么如果臉哥買了 z1 和 z2 就不會再買 zh 了。臉哥想要在買下最多數量的裝備的情況下花最少的錢，你能幫他算一下嗎？

Input Format

第一行兩個數 n;m。接下來 n 行，每行 m 個數，其中第 i 行描述裝備 i 的各項屬性值。接下來一行 n 個數， 其中 ci 表示購買第 i 件裝備的花費。

Output Format

一行兩個數，第一個數表示能夠購買的最多裝備數量，第二個數表示在購買最多數量的裝備的情況下的最小花費

Sample Input

3 3 1 2 3 3 4 5 2 3 4 1 1 2

Sample Output

2 2

解析

本題即求所給向量所構成的線性空間中的一個極大線性無關子集，即求解一個整數域線性空間的基，使用高斯消元算法即可。

本題還要求最小花費，可以使用貪心策略，在高斯消元時，每次選擇該未知數系數非零時，花費最小的一行用來消元，選作主元即可。

\(Code:\)

#include<bits/stdc++.h> using namespace std; const int N=520,M=520; const long double eps=1e-8; int n,m,c[N],ans,sum; long double a[N][M]; inline void input(void) {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)scanf("%Lf",&a[i][j]);for (int i=1;i<=n;i++)scanf("%d",&c[i]); } inline void Guass(void) {for (int i=1;i<=m;i++){int row=0;for (int j=i;j<=n;j++)if ( fabs(a[j][i]) > eps && ( !row || c[row] > c[j] ) )row = j;if ( fabs(a[row][i]) < eps )continue;if ( row ^ i )swap(a[i],a[row]) , swap(c[i],c[row]);sum += c[i];ans ++;for (int j=1;j<=n;j++){if (i==j)continue;long double rate = a[j][i] / a[i][i];for (int k=i;k<=m;k++)a[j][k] -= a[i][k] * rate;}}return; } int main(void) {input();Guass();printf("%d %d\n",ans,sum);return 0; }

異或運算

Description

給定你由N個整數構成的整數序列，你可以從中選取一些（甚至一個）進行異或（XOR）運算，從而得到很多不同的結果。

請問，所有能得到的不同的結果中第k小的結果是多少。

Input Format

第一行包含整數T，表示共有T組測試數據。

對于每組測試數據，第一行包含整數N。

第二行包含N個整數(均在1至1018之間)，表示完整的整數序列。

第三行包含整數Q，表示詢問的次數。

第四行包含Q個整數k1,k2,…,kQ,表示Q個詢問對應的k。

Output Format

對于每組測試數據，第一行輸出“Case #C:”，其中C為順序編號（從1開始）。

接下來Q行描述Q次詢問的結果，每行輸出一個整數，表示第i次詢問中第kiki小的結果。

如果能得到的不同結果的總數少于kiki，則輸出“-1”。

Sample Input

2 2 1 2 4 1 2 3 4 3 1 2 3 5 1 2 3 4 5

Sample Output

Case #1: 1 2 3 -1 Case #2: 0 1 2 3 -1

解析

本題的題面很清晰地描述了一個線性空間的樣子，但是運算法則是異或，因此，我們就能類似的定義異或意義下的線性空間。

于是，這個異或線性空間的基的求解就和高斯消元算法中的異或高消對應了起來。那么利用異或高消，我們假設求出了\((a_1,a_2,...,a_n)\)的表出線性空間的基為\((b_1,b_2,...,b_t)\)，設\(b_1>b_2>...>b_t\)。

從\((b_1,b_2,...,b_t)\)中取出若干個整數進行異或運算得到數字，顯然有\(2^t\)種取法，即可得到異或空間中有\(2^t\)個數字。由基的定義可得，\((b_1,b_2,...,b_t)\)可表出的線性空間和\((a_1,a_2,...,a_n)\)可表出的線性空間是一樣的。

對于主元\(x_i\)，高斯消元保證了除第\(i\)行的\(x_i\)系數外，其他行的\(x_i\)系數均為\(0\)，又因為\(b_1>b_2>...>b_t\)，所以在異或運算上，必然有取\(b_1\)的比不取\(b_1\)的大，不取\(b_1\)時，取\(b_2\)的比不取\(b_2\)的大，不取\(b_1\)和\(b_2\)時，取\(b_3\)的比不取\(b_3\)的大 \(...\) 即異或空間中的最大數是所有\(b_i\)異或的結果，最小數是\(0\)。

那么這就可以和所求第\(k\)小數的\(k\)聯系起來。將\(k\)二進制分解，如果\(k\)的第\(i(0 \leq i<t)\)位為\(0\)，則選\(b_{t-i}\)。最后，將所有所選的數異或起來就是異或空間中的第\(k\)小數。

事實上，直接對\(k\)進行二進制分解不能保證正確性。這樣是因為在異或空間中，一定可以異或得到整數\(0\)(由某個數異或它本身)，而在本題中，不允許這樣的操作。所以在高斯消元時可以進行判斷，若存在全\(0\)行，則說明\(0\)本身可以通過若干個不同的數異或得到，最小值為\(0\)，需要二進制分解\(k-1\)來取數字。反之，則\(0\)是實際中不能得到的一個數字，二進制分解\(k\)即可。

\(Code:\)

#include<bits/stdc++.h> using namespace std; const int N=10020,Q=10020; int n,q,flag,Pow; unsigned long long a[N]; inline void input(void) {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%llu",&a[i]); } inline void Guass(void) {flag=0 , Pow=n;for (int i=1;i<=n;i++){for (int j=i+1;j<=n;j++)if ( a[j] > a[i] )swap(a[j],a[i]);if ( !a[i] ){flag=true;Pow=i-1;return;}for (int j=63;j>=0;j--){if ( a[i] >> j & 1 ){for (int k=1;k<=n;k++)if ( i!=k && a[k] >> j & 1 )a[k] ^= a[i];break;}}} } inline void solve(void) {scanf("%d",&q);for (int i=1;i<=q;i++){unsigned long long k,ans=0;scanf("%llu",&k);if (flag)k--;if ( k >= (1ULL<<Pow) )printf("-1\n");else {for (int i=0;i<Pow;i++)if ( k >> i & 1 )ans ^= a[ Pow-i ];printf("%llu\n",ans);}} } int main(void) {int T;scanf("%d",&T);for (int i=1;i<=T;i++){input();Guass();printf("Case #%d:\n",i);solve();}return 0; }

---

轉載于:https://www.cnblogs.com/Parsnip/p/10726036.html

總結

以上是生活随笔為你收集整理的『线性空间 整数线性基和异或线性基』的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。