如何做明星的个人网站,网易企业邮箱手机端设置,中国菲律宾世预赛,沧州*网站建设向量随机化神奇的矩阵descriptionsolutioncode[NOI2013]向量内积descriptionsolutioncode矩阵既可以看成是一张数位表#xff0c;也可以看成是若干个行向量或者若干个列向量的向量表神奇的矩阵
description
solution
暴力做A∗BA*BA∗B会达到n3n^3n3的复杂度#xff0c;难…
向量随机化神奇的矩阵descriptionsolutioncode[NOI2013]向量内积descriptionsolutioncode矩阵既可以看成是一张数位表也可以看成是若干个行向量或者若干个列向量的向量表神奇的矩阵
description
solution
暴力做A∗BA*BA∗B会达到n3n^3n3的复杂度难以接受
考虑如果对于矩阵A,B,CA,B,CA,B,C满足A∗BCA*BCA∗BC显然有A∗B∗RC∗RA*B*RC*RA∗B∗RC∗R
于是有随机一个1×n1\times n1×n的向量RRR然后check等式是否成立A∗R∗BA*R*BA∗R∗B就会降成n2n^2n2的复杂度
随机多次都无法满足这个式子A∗BCA*BCA∗BC的概率就微乎其微除非你是非酋
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]向量内积
description
solution k2 求出矩阵两两内积(mod2)\pmod 2(mod2) 即YA∗ATYA*A^TYA∗AT接下来就是判断YE,EYE,EYE,E为全111矩阵Yi,jY_{i,j}Yi,j代表着AAA的iii行向量与ATA^TAT的jjj列向量也就是原来的AjA_jAj行向量的内积因为如果全111代表着每两个向量的内积都为1(mod2)1\pmod 21(mod2) 判断方法就是上一题的随机化只要不等就会有一个000向量找到其位置pospospos最后暴力求每个向量与其的内积是否整除kkk即可 k3此时Ai,j0/1/2A_{i,j}0/1/2Ai,j0/1/2不能在使用上述EEE来判断了 转换一下即可Zi,jYi,j2(mod3)Z_{i,j}Y_{i,j}^2\pmod 3Zi,jYi,j2(mod3)有12≡23≡1(mod3)1^2\equiv 2^3\equiv 1\pmod 312≡23≡1(mod3)只有02≡0(mod3)0^2\equiv 0\pmod302≡0(mod3) 再次使用EEE来进行判断 问题在于ZZZ是YYY每个单项的平方不是整体的平方不能使用矩阵快速得到 设α\alphaα是随机的一个1×n1\times n1×n向量 (Z∗α)i∑j1nZi,j∗αj∑j1nYi,j2∗αj∑j1nαj(∑k1nAi,kAk,jT)2(Z*\alpha)_i\sum_{j1}^nZ_{i,j}*\alpha_j\sum_{j1}^nY_{i,j}^2*\alpha_j\sum_{j1}^n\alpha_j\bigg(\sum_{k1}^nA_{i,k}A^T_{k,j}\bigg)^2(Z∗α)i∑j1nZi,j∗αj∑j1nYi,j2∗αj∑j1nαj(∑k1nAi,kAk,jT)2 ∑j1nαj∑k11nAi,k1Ak1,jT∗∑j1nαj∑k21nAi,k2Ak2,jT\sum_{j1}^n\alpha_j\sum_{k_11}^nA_{i,k_1}A^T_{k_1,j}*\sum_{j1}^n\alpha_j\sum_{k_21}^nA_{i,k_2}A^T_{k_2,j}∑j1nαj∑k11nAi,k1Ak1,jT∗∑j1nαj∑k21nAi,k2Ak2,jT 发现可以变为∑k1,k2Ai,k1Ai,k2∗∑j1nαjAk1,jAk2,jT\sum_{k_1,k_2}A_{i,k_1}A_{i,k_2}*\sum_{j1}^n\alpha_jA_{k_1,j}A^T_{k_2,j}∑k1,k2Ai,k1Ai,k2∗∑j1nαjAk1,jAk2,jT 预处理出和iii无关部分设gk1,k2∑j1nαjAk1,jAk2,jTg_{k_1,k_2}\sum_{j1}^n\alpha_jA_{k_1,j}A^T_{k_2,j}gk1,k2∑j1nαjAk1,jAk2,jT
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;
}
