BZOJ 3243 向量内积

http://www.lydsy.com/JudgeOnline/problem.php?id=3243

考虑K==2的情况

考虑把n个向量用n*d的矩阵表示，则A*AT(A的转置矩阵)中的i,j代表i和j的向量积。

考虑K==3的情况

1*1%3=1

2*2%3=1

则我们将原来矩阵中元素平方。

(A,B)^2=(a1×b1+a2×b2+a3×b3)^2

展开来就是新的向量积表示，转换之后就是像K=2一样。

详细参考:http://www.cnblogs.com/mmlz/p/4313031.html

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<time.h>
 7 #define N 120005
 8 #define ll long long
 9 int B[120][N],A[N][120],c[N],g[N],f,T[N];
10 int sz,s[2][N];
11 int n,d,K;
12 int read(){
13     int t=0,f=1;char ch=getchar();
14     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
15     while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
16     return t*f;
17 }
18 void find(int pos){
19     for (int i=1;i<=n;i++)
20      if (i!=pos){
21             int res=0;
22             for (int j=1;j<=d;j++)
23              res+=A[i][j]*A[pos][j];
24             res%=K; 
25             if (res==0){
26                 printf("%d %d",std::min(i,pos),std::max(i,pos));
27                 return;
28             } 
29      }
30 }
31 void mul1(){
32     if (K==2){
33     memset(T,0,sizeof T);
34     for (int i=1;i<=d;i++)
35      for (int j=1;j<=n;j++)
36       T[i]=(T[i]+B[i][j]*s[0][j])&1;
37     memset(s[0],0,sizeof s[0]);
38     for (int i=1;i<=n;i++)
39      for (int j=1;j<=d;j++)
40       s[0][i]=(s[0][i]+A[i][j]*T[j])&1;  
41     }
42     else{
43         memset(T,0,sizeof T);
44         for (int i=1;i<=d;i++) 
45          for (int j=1;j<=d;j++)
46           for (int k=1;k<=n;k++)
47            T[i*d+j]=(T[i*d+j]+B[j][k]*B[i][k]*s[0][k])%3;
48         memset(s[0],0,sizeof s[0]);
49         for (int i=1;i<=n;i++)
50          for (int j=1;j<=d;j++)
51           for (int k=1;k<=d;k++)
52            s[0][i]=(s[0][i]+A[i][j]*A[i][k]*T[j*d+k])%3;
53     }
54 }
55 void mul2(){
56     int sum=0;
57     for (int i=1;i<=n;i++) sum+=s[1][i];
58     for (int i=1;i<=n;i++)
59      s[1][i]=(sum-(1-g[i])*s[1][i])%K;
60 }
61 void solve(){
62     for (int i=1;i<=n;i++)
63      for (int j=1;j<=d;j++)
64       B[j][i]=A[i][j];
65     for (int i=1;i<=n;i++) 
66      for (int j=1;j<=d;j++){
67         (g[i]+=A[i][j]*A[i][j])%=K;
68         if (K==3) g[i]=(g[i]*g[i])%K;
69      } 
70     for (int t=1;t<=10;t++){
71         for (int i=1;i<=n;i++) s[0][i]=rand()%2;
72         for (int i=1;i<=n;i++) s[1][i]=s[0][i];
73         mul1();mul2();
74         for (int i=1;i<=n;i++)
75          if (s[0][i]!=s[1][i]){
76           find(i);
77           return;
78          }
79     } 
80 }
81 int main(){
82     srand(233);
83     n=read();d=read();K=read();
84     for (int i=1;i<=n;i++)
85      for (int j=1;j<=d;j++)
86       (A[i][j]=read())%=K;
87     solve();
88     return 0;
89 }