題目描述
兩個 d 維向量 A=[a1,a2,…,ad] 與 B=[b1,b2,…,bd] 的内積為其相對應次元的權值的乘積和,即:
⟨A,B⟩=∑i=1daibi=a1b1+a2b2+⋯+adbd
現在有 n 個 d 維向量 x1,x2,…,xn ,小喵喵想知道是否存在兩個向量的内積為 k 的倍數。請幫助她解決這個問題。
輸入格式
第一行包含 3 個正整數 n,d,k ,分别表示向量的個數,維數以及待檢測的倍數。
接下來 n 行每行有 d 個非負整數,其中第 i 行的第 j 個整數表示向量 xi 的第 j 維權值 xi,j。
輸出格式
包含兩個整數,用空格隔開。
如果存在兩個向量 xp,xq 的内積為 k 的整數倍,則輸出兩個向量的編号 p 與 q (要求 p<q)。如果存在多組這樣的向量組合,輸出其中任意一組即可。
若不存在這樣的向量組合,則輸出兩個 −1 。
樣例一
input
3 5 2
1 0 1 0 1
1 1 0 1 0
0 1 0 1 1
output
2 3
explanation
⟨x1,x2⟩=1 , ⟨x1,x3⟩=1 , ⟨x2,x3⟩=2 。
限制與約定
測試點編号 | n | d | k | xi,j |
---|---|---|---|---|
1 | 2 | 20 | 2 | ≤10 |
2 | 5 | 20 | 2 | ≤10 |
3 | 10 | 20 | 3 | ≤10 |
4 | 20 | 20 | 2 | ≤100 |
5 | 50 | 20 | 3 | ≤100 |
6 | 50 | 50 | 2 | ≤1000 |
7 | 50 | 50 | 3 | ≤3000000 |
8 | 80 | 80 | 2 | ≤3000000 |
9 | 100 | 100 | 3 | ≤3000000 |
10 | 500 | 100 | 3 | ≤3000000 |
11 | 1000 | 100 | 2 | ≤3000000 |
12 | 1000 | 100 | 3 | ≤3000000 |
13 | 10000 | 100 | 2 | <10 |
14 | 10000 | 100 | 3 | <10 |
15 | 15000 | 100 | 2 | <10 |
16 | 18000 | 100 | 2 | <10 |
17 | 20000 | 100 | 2 | <10 |
18 | 50000 | 30 | 3 | <10 |
19 | 80000 | 30 | 3 | <10 |
20 | 100000 | 30 | 3 | <10 |
時間限制: 5s
空間限制: 256MB
分析
注意:以下運算都在模k意義下
k=2
我們把這些向量看成一個 n×d 的矩陣 A
A=⎡⎣⎢⎢⎢⎢⎢x1,1x2,1⋮xn,1x1,2x2,2⋮xn,2x1,3x2,3⋮xn,3⋯⋯⋱⋯x1,dx2,d⋮xn,d⎤⎦⎥⎥⎥⎥⎥
A 的轉置矩陣AT=⎡⎣⎢⎢⎢⎢⎢x1,1x1,2⋮x1,nx2,1x2,2⋮x2,nx3,1x3,2⋮x3,n⋯⋯⋱⋯xn,1xn,2⋮xnn⎤⎦⎥⎥⎥⎥⎥
令 B=A×AT ,那麼 bi,j 就表示 xi⋅xj ,如果 B 矩陣除了主對角線全部是1的話,顯然無解。
但是求出B矩陣的時間顯然是 O(n2d) ,顯然是無法通過本題的。
我們令 B′ 為 bi,i=xi⋅xi ,其餘元素為1的矩陣。
如果 B =B′的話,就無解。
我們再随機找出一個列向量 C (其實就是全是1,因為0沒用。。。)
B×C=B′×CA×AT×C=B′×CA×(AT×C)=B′×C
D=AT×C 我們可以用 O(nd) 的時間求出來, A×D 也可以用 O(nd) 的時間求出來, B′×C 可以 O(n) 求出。
然後比較 A×(AT×C) B′×C 這兩個列向量的每一個元素是否相同,如果第i行的元素不相同,說明 xi 肯定是答案隻要,枚舉找出 xj 即可。
盡管有出錯的機率,但是這個算法還是比較可靠的。
k=3
我們發現
1×1≡2×2≡1(mod3)
是以,我們令 B=(A∗AT)2 其餘矩陣定義不變,那麼展開後會發現
A′=⎡⎣⎢⎢⎢⎢⎢x1,1×x1,1x2,1×x2,1⋮xn,1×xn,1x1,1×x1,2x2,1×x2,2⋮xn,1×xn,2x1,1×x1,3x2,1×x2,3⋮xn,1×xn,3⋯⋯⋱⋯x1,1×x1,dx2,1×x2,d⋮xn,1×xn,dx1,2×x1,1x2,2×x2,1⋮xn,2×xn,1x1,2×x1,2x2,2×x2,2⋮xn,2×xn,2⋯⋯⋱⋯x1,d×x1,dx2,d×x2,d⋮xn,d×xn,d⎤⎦⎥⎥⎥⎥⎥B=A′×A′T
然後參考 k=2 的算法即可,由于 k=3 時矩陣太大,記憶體開不下,但是算的時候按照規則算就行了。
代碼
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100000
#define MAXM 100
int n,d,k,a[MAXN+][MAXM+],s[MAXN+],c[MAXM*MAXM+],g[MAXN+];
void Read(int &x){
char c;
while(c=getchar(),c!=EOF)
if(c>='0'&&c<='9'){
x=c-'0';
while(c=getchar(),c>='0'&&c<='9')
x=x*+c-'0';
ungetc(c,stdin);
return;
}
}
int Get_id(int i,int j){
return (i-)*d+j;
}
void read(){
Read(n),Read(d),Read(k);
int i,j;
for(i=;i<=n;i++)
for(j=;j<=d;j++){
Read(a[i][j]);
a[i][j]%=k;
s[i]+=a[i][j]*a[i][j];
}
for(i=;i<=n;i++)
s[i]%=k;
}
void solve2(){
int i,j,k,sum;
for(i=;i<=d;i++)
for(j=;j<=n;j++)
c[i]^=a[j][i];
for(i=;i<=n;i++)
for(j=;j<=d;j++)
g[i]^=a[i][j]&c[j];
for(i=;i<=n;i++)
if(g[i]!=(s[i]^((n-)&)))
break;
if(i>n){
puts("-1 -1");
return;
}
for(j=;j<=n;j++)
if(i!=j){
sum=;
for(k=;k<=d;k++)
sum^=a[i][k]&a[j][k];
if(!sum)
break;
}
if(i>j)
swap(i,j);
printf("%d %d\n",i,j);
}
void solve3(){
int i,j,k,sum;
for(i=;i<=d;i++)
for(j=;j<=d;j++)
for(k=;k<=n;k++)
c[Get_id(i,j)]+=a[k][i]*a[k][j];
for(i=d*d;i;i--)
c[i]%=;
for(i=;i<=n;i++)
for(j=;j<=d;j++)
for(k=;k<=d;k++)
g[i]+=a[i][j]*a[i][k]*c[Get_id(j,k)];
for(i=;i<=n;i++)
if(g[i]%!=((n-)+s[i]*s[i])%)
break;
if(i>n){
puts("-1 -1");
return;
}
for(j=;j<=n;j++)
if(j!=i){
sum=;
for(k=;k<=d;k++)
sum=(sum+a[i][k]*a[j][k])%;
if(!sum)
break;
}
if(i>j)
swap(i,j);
printf("%d %d\n",i,j);
}
int main()
{
read();
if(k==)
solve2();
else
solve3();
}