传送门
思路
唉，我太弱了，什么都不会，听都没有听说过这类题，唉，我太弱啦！
显然这道题可以在
O(n2d)
O
(
n
2
d
)
的时间复杂度内得出答案，顺利得到
60
60
分。注意到，
k
k
是不会影响 O(n2d) 的算法的，而数据规模中
k
k
只会等于 2 或者
3
3
，说明最后的算法一定跟 k 有关。另外，显然的是
x
x
的范围没有任何用处，我们只需要在模 k 意义下进行计算就可以了。
一个 Naive 但又很显然的想法是，既然我们挨着检查算不完，那我们干脆每次随机两个向量相乘。但显然的是，这样做的概率是无法得到保证的，成功得到
0
0
分。
我们可以用矩阵来表示一堆向量两两相乘的结果。我们设矩阵 A 表示一堆向量，则
A×AT
A
×
A
T
的元素
ai,j
a
i
,
j
表示的就是第
i
i
个向量与第 j 个向量的点积。那么我们可以这样判断是否有解：如果
A×AT
A
×
A
T
的非对角线元素存在
0
0
（从这里开始以及下面的讨论中的运算都是在模 k 意义下进行的），则一定有解，且它的行数和列数就是向量的编号。
假设我们有一台运算能力和存储空间无限的计算机，我们考虑上面的操作如何进行。首先我们考虑
k=2
k
=
2
的情况。显然，我们可以保存
A
A
和 AT，然后在
O(n2d)
O
(
n
2
d
)
的时间复杂度内计算出它们的积。接下来我们要找非对角线上的元素是否存在
0
0
，我们可以直接用一个二重循环，也可以考虑这样一个方法：构造矩阵 D，满足：
di,j={1ai⋅aii≠ji=j
d
i
,
j
=
{
1
i
≠
j
a
i
⋅
a
i
i
=
j
我们检查
A×AT
A
×
A
T
是否等于
D
D
，如果等于，说明无解，否则说明有解。
由于我们的计算机运算能力有限，所以我们显然不能暴力开数组，暴力算矩阵乘法。我们考虑这样做：设一个长度为 n 的随机的 01 列向量
R
R
，若 A×AT×R≠D×R，那么我们可以断定
A×AT≠D
A
×
A
T
≠
D
，且我们知道是哪一行不一样。右式显然可以在
O(nd)
O
(
n
d
)
的时间复杂度内计算出来。左式由于等于
A×(AT×R)
A
×
(
A
T
×
R
)
，也能够在
O(nd)
O
(
n
d
)
的时间复杂度内计算出来。在找到哪一行不一样后，我们可以在
O(nd)
O
(
n
d
)
的时间复杂度内找出另外一个向量，问题就解决了。
然而，若
A×AT×R=D×R
A
×
A
T
×
R
=
D
×
R
，我们却没法断定
A×AT=D
A
×
A
T
=
D
，因为这个过程实际上对信息进行了有损压缩。考虑
D×R
D
×
R
的实际意义，它实际上是在考虑
D
D
和 R 均为
1
1
的个数。但是需要注意的是，这个运算必须在模意义下进行，因此个数就变成了个数的奇偶性。那么显然，若一次测试后报告无解，那么实际上无解的几率为 121，所以在进行足够多次后仍然报告无解的话，我们就可以认为无解。
我们考虑
k=3
k
=
3
时该怎么做。当
k=3
k
=
3
时，我们没有办法构造
D
D
矩阵了，因为非对角线元素有可能为 1，也有可能为
2
2
，我们无法知道到底该是什么。
注意到，02≡0(mod3)，
12≡1(mod3)
1
2
≡
1
(
mod
3
)
，
22≡1(mod3)
2
2
≡
1
(
mod
3
)
，也就是说，我们将向量点积的结果平方，就能将问题转换成判断
01
01
矩阵是否相等了。
考虑把结果平方后，原式是如何变化的：
(∑i=1daibi)(∑i=1daibi)=∑i=1d∑j=1daiajbibj
(
∑
i
=
1
d
a
i
b
i
)
(
∑
i
=
1
d
a
i
b
i
)
=
∑
i
=
1
d
∑
j
=
1
d
a
i
a
j
b
i
b
j
我们把
aiaj
a
i
a
j
看作一个整体，则相当于变成了
d2
d
2
维的向量相乘，模数变成了
3
3
（注意：随机生成的列向量仍然是 01 向量，但是模数变成了 3）。如法炮制即可。
这里的转换实际上是这个意思：运算仍然在模
3
3
意义下进行，但是我们用一种特殊的手段强行让最后的结果在模 3 意义下只存在
0
0
和 1，且
0
0
对应原来的零，1 对应原来的非零。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
#define loop register int
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
const int maxn = int(1e5) + 5;
int n, d, K;
struct Rect
{
int c[3000105];
int* operator[](int x)
{
return c + x * d;
}
const int* operator[](int x) const
{
return c + x * d;
}
} vec;
#define RunInstance(x) delete new x
struct brute
{
brute()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < d; j++)
vec[i][j] %= K;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
int sum = 0;
for (int k = 0; k < d; k++)
sum += vec[i][k] * vec[j][k];
if (!(sum % K))
{
printOut(i + 1);
putchar(' ');
printOut(j + 1);
return;
}
}
printf("-1 -1");
}
};
struct work2
{
int random[maxn];
int diagonal[maxn];
int temp[105];
work2()
{
for (loop i = 0; i < n; i++)
{
loop t = 0;
for (loop j = 0; j < d; j++)
t += vec[i][j] * vec[i][j];
t &= 1;
diagonal[i] = t;
}
int T = 1e8 / (n * d);
while (T--)
{
int count1 = 0;
for (loop i = 0; i < n; i++)
count1 += random[i] = rand() & 1;
for (loop j = 0; j < d; j++)
{
loop t = 0;
for (loop i = 0; i < n; i++)
t += vec[i][j] & random[i];
temp[j] = t;
}
for (loop i = 0; i < n; i++)
{
loop t = 0;
for (loop j = 0; j < d; j++)
t += vec[i][j] * temp[j];
if ((t & 1) != ((count1 - (!diagonal[i] && random[i])) & 1))
{
for (loop j = 0; j < n; j++) if (i != j)
{
loop sum = 0;
for (loop k = 0; k < d; k++)
sum += vec[i][k] * vec[j][k];
if (!(sum % K))
{
if (i > j)
std::swap(i, j);
printOut(i + 1);
putchar(' ');
printOut(j + 1);
return;
}
}
}
}
}
puts("-1 -1");
}
};
struct work3
{
int random[maxn];
int diagonal[maxn];
int temp[105 * 105];
work3()
{
for (loop i = 0; i < n; i++)
{
loop t = 0;
loop v;
for (loop j = 0; j < d; j++)
for (loop k = 0; k < d; k++)
t += (v = vec[i][j] * vec[i][k]) * v;
t %= 3;
diagonal[i] = t;
}
int T = 1e8 / (n * d * d);
while (T--)
{
int count1 = 0;
for (loop i = 0; i < n; i++)
count1 += random[i] = rand() & 1;
for (loop j = 0, v = 0; j < d; j++)
for (loop k = 0; k < d; k++, v++)
{
loop t = 0;
for (loop i = 0; i < n; i++)
t += vec[i][j] * vec[i][k] * random[i];
temp[v] = t % 3;
}
for (loop i = 0; i < n; i++)
{
loop t = 0;
for (loop j = 0, v = 0; j < d; j++)
for (loop k = 0; k < d; k++, v++)
t += vec[i][j] * vec[i][k] * temp[v] % 3;
if ((t % 3) != ((count1 - (!diagonal[i] && random[i])) % 3))
{
for (loop j = 0; j < n; j++) if (i != j)
{
loop sum = 0;
for (loop k = 0; k < d; k++)
sum += vec[i][k] * vec[j][k];
if (!(sum % K))
{
if (i > j)
std::swap(i, j);
printOut(i + 1);
putchar(' ');
printOut(j + 1);
return;
}
}
}
}
}
puts("-1 -1");
}
};
void run()
{
n = readIn();
d = readIn();
K = readIn();
for (int i = 0; i < n; i++)
for (int j = 0; j < d; j++)
vec[i][j] = readIn();
if ((LL)n * n * d <= LL(3e8))
RunInstance(brute);
else if (K == 2)
RunInstance(work2);
else
RunInstance(work3);
}
int main()
{
run();
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
