向量隨機(jī)化

• 神奇的矩陣
• • description
  • solution
  • code
• [NOI2013]向量?jī)?nèi)積
• • description
  • solution
  • code

矩陣既可以看成是一張數(shù)位表，也可以看成是若干個(gè)行向量或者若干個(gè)列向量的向量表

神奇的矩陣

description

solution

暴力做$A?B$會(huì)達(dá)到$n^3$的復(fù)雜度，難以接受

考慮，如果對(duì)于矩陣$A,B,C$滿足$A?B=C$，顯然有$A?B?R=C?R$

于是有隨機(jī)一個(gè)$1\times n$的向量$R$，然后check等式是否成立，$A?R?B$就會(huì)降成$n^2$的復(fù)雜度

隨機(jī)多次都無(wú)法滿足這個(gè)式子，$A?B=C$的概率就微乎其微（除非你是非酋）

code

#include <bits/stdc++.h> using namespace std; #define int long long int n;struct matrix {int n, m;int c[1000][1000];matrix() {memset( c, 0, sizeof( c ) );}matrix operator * ( matrix &t ) {matrix ans;ans.n = n, ans.m = t.m;for( int i = 0;i <= n;i ++ )for( int j = 0;j <= t.m;j ++ )for( int k = 0;k <= m;k ++ )ans.c[i][j] += c[i][k] * t.c[k][j];return ans;} }A, B, C, R, ans1, ans2;signed main() {srand( time( 0 ) );next :while( ~ scanf( "%lld", &n ) ) {n --;A.n = A.m = B.n = B.m = C.n = C.m = n;for( int i = 0;i <= n;i ++ )for( int j = 0;j <= n;j ++ )scanf( "%lld", &A.c[i][j] );for( int i = 0;i <= n;i ++ )for( int j = 0;j <= n;j ++ )scanf( "%lld", &B.c[i][j] );for( int i = 0;i <= n;i ++ )for( int j = 0;j <= n;j ++ )scanf( "%lld", &C.c[i][j] );int t = 30;again :while( t -- ) {R.n = 0, R.m = n;for( int i = 0;i <= n;i ++ )R.c[0][i] = rand();ans1 = R * A * B;ans2 = R * C;for( int i = 0;i <= n;i ++ )if( ans1.c[0][i] != ans2.c[0][i] )goto again;printf( "Yes\n" );goto next;}printf( "No\n" );}return 0; }

[NOI2013]向量?jī)?nèi)積

description

solution

• k=2

  • 求出矩陣兩兩內(nèi)積$(\mathrm{m}\mathrm{o}\mathrm{d}2)$ ，即$Y=A?A^T$
  • 接下來(lái)就是判斷$Y=E,E$為全$1$矩陣（$Y_{i,j}$代表著$A$的$i$行向量與$A^T$的$j$列向量也就是原來(lái)的$A_j$行向量的內(nèi)積）因?yàn)槿绻?span id="ze8trgl8bvbq" class="katex--inline">$1$代表著每?jī)蓚€(gè)向量的內(nèi)積都為$1(\mathrm{m}\mathrm{o}\mathrm{d}2)$
    • 判斷方法就是上一題的隨機(jī)化
    • 只要不等，就會(huì)有一個(gè)$0$向量，找到其位置$pos$，最后暴力求每個(gè)向量與其的內(nèi)積是否整除$k$即可

• k=3，此時(shí)$A_{i,j}=0/1/2$，不能在使用上述$E$來(lái)判斷了

  • 轉(zhuǎn)換一下即可，$Z_{i,j}=Y_{i,j}^2(\mathrm{m}\mathrm{o}\mathrm{d}3)$，有$1^2\equiv 2^3\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3)$，只有$0^2\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}3)$

  • 再次使用$E$來(lái)進(jìn)行判斷

  • 問(wèn)題在于，$Z$是$Y$每個(gè)單項(xiàng)的平方，不是整體的平方，不能使用矩陣快速得到

    • 設(shè)$\alpha$是隨機(jī)的一個(gè)$1\times n$向量

    • $(Z?\alpha {)}_i={\sum }_{j=1}^n{Z}_{i,j}?{\alpha }_j={\sum }_{j=1}^n{Y}_{i,j}^2?{\alpha }_j={\sum }_{j=1}^n{\alpha }_j({\sum }_{k=1}^n{A}_{i,k}{A}_{k,j}^T{)}^2$

      $={\sum }_{j=1}^n{\alpha }_j{\sum }_{k_1=1}^n{A}_{i,k_1}{A}_{k_1,j}^T?{\sum }_{j=1}^n{\alpha }_j{\sum }_{k_2=1}^n{A}_{i,k_2}{A}_{k_2,j}^T$

    • 發(fā)現(xiàn)可以變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">${\sum }_{k_1,k_2}{A}_{i,k_1}{A}_{i,k_2}?{\sum }_{j=1}^n{\alpha }_j{A}_{k_1,j}{A}_{k_2,j}^T$

      預(yù)處理出和$i$無(wú)關(guān)部分，設(shè)$g_{k_1,k_2}={\sum }_{j=1}^n{\alpha }_j{A}_{k_1,j}{A}_{k_2,j}^T$

code

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 100005 #define maxd 105 int n, d, k, sum, pos, flag; int x[maxn][maxd], g[maxn][maxd]; int ret[maxd], r[maxn];void calc2() {for( int i = 1;i <= d;i ++ ) ret[i] = 0;for( int i = 1;i <= d;i ++ )for( int j = 1;j <= n;j ++ )ret[i] = ( ret[i] + r[j] * x[j][i] ) % k;for( int i = 1;i <= n;i ++ ) {int ans = 0;for( int j = 1;j <= d;j ++ )ans = ( ans + ret[j] * x[i][j] ) % k;if( ans != sum ) {pos = i, flag = 1;break;}} }void calc3() {for( int k1 = 1;k1 <= d;k1 ++ )for( int k2 = 1;k2 <= d;k2 ++ ) {g[k1][k2] = 0;for( int j = 1;j <= n;j ++ )g[k1][k2] = ( g[k1][k2] + r[j] * x[j][k1] % k * x[j][k2] ) % k;}for( int i = 1;i <= n;i ++ ) {int ans = 0;for( int k1 = 1;k1 <= d;k1 ++ )for( int k2 = 1;k2 <= d;k2 ++ )ans = ( ans + x[i][k1] * x[i][k2] % k * g[k1][k2] ) % k;if( ans != sum ) {pos = i, flag = 1;break;}} }signed main() {srand( time( 0 ) );scanf( "%lld %lld %lld", &n, &d, &k );for( int i = 1;i <= n;i ++ )for( int j = 1;j <= d;j ++ )scanf( "%lld", &x[i][j] ); for( int T = 1;T <= 6;T ++ ) {sum = 0;for( int i = 1;i <= n;i ++ )r[i] = rand() % k, sum = ( sum + r[i] ) % k;if( k == 2 ) calc2();else calc3();if( flag ) break;}if( ! flag ) return ! printf( "-1 -1\n" );else {for( int i = 1;i <= n;i ++ )if( i ^ pos ) {int ans = 0;for( int j = 1;j <= d;j ++ )ans = ( ans + x[i][j] * x[pos][j] ) % k;if( ! ans ) return ! printf( "%lld %lld\n", min( i, pos ), max( i, pos ) );}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的线性代数一之矩阵转向量随机化求解——神奇的矩阵(BZOJ)+向量内积的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。