【NOI2013】向量内积【随机化】
传送门
题意：给nnn个ddd维向量，询问是否有两个向量内积（对应位乘积和）为kkk的倍数
n≤100000,d≤100,k=2,3n \leq100000,d\leq100,k=2,3n≤100000,d≤100,k=2,3
考虑每个向量能否与之前的某一个匹配
如果我们找到某一个与之前的可以匹配，就可以O(nd)O(nd)O(nd)得到答案。我们要做的是排除不能匹配的答案。
（以下mmm为题中给的kkk）
即
∀1≤i<n,∑k=1dai,kan,k≠0(modm)\forall1\leq i<n,\sum_{k=1}^{d}a_{i,k}a_{n,k}\neq0\pmod{m}∀1≤i<n,k=1∑dai,kan,k=0(modm)
当m=2m=2m=2时
∀1≤i<n,∑k=1dai,kan,k≡1(mod2)\forall1\leq i<n,\sum_{k=1}^{d}a_{i,k}a_{n,k}\equiv1\pmod{2}∀1≤i<n,k=1∑dai,kan,k≡1(mod2)
弱化得
∑i=1n−1∑k=1dai,kan,k≡n−1(mod2)\sum_{i=1}^{n-1}\sum_{k=1}^{d}a_{i,k}a_{n,k}\equiv n-1\pmod{2}i=1∑n−1k=1∑dai,kan,k≡n−1(mod2)
∑k=1d(∑i=1n−1ai,k)an,k≡n−1(mod2)\sum_{k=1}^{d}(\sum_{i=1}^{n-1}a_{i,k})a_{n,k}\equiv n-1\pmod{2}k=1∑d(i=1∑n−1ai,k)an,k≡n−1(mod2)
维护个前缀和判一下，如果不满足说明一定有答案
感性理解，理论上这个答案是随便找得到的，所以随机打乱几次能大概率出解
当m=3m=3m=3时同理
∀1≤i<n,∑k=1dai,kan,k≡1or2(mod3)\forall1\leq i<n,\sum_{k=1}^{d}a_{i,k}a_{n,k}\equiv1 or 2\pmod{3}∀1≤i<n,k=1∑dai,kan,k≡1or2(mod3)
平方一下
∀1≤i<n,(∑k=1dai,kan,k)2≡1(mod3)\forall1\leq i<n,(\sum_{k=1}^{d}a_{i,k}a_{n,k})^2\equiv1 \pmod{3}∀1≤i<n,(k=1∑dai,kan,k)2≡1(mod3)
∑i=1n−1(∑k=1dai,kan,k)2≡n−1(mod3)\sum_{i=1}^{n-1}(\sum_{k=1}^{d}a_{i,k}a_{n,k})^2\equiv n-1\pmod{3}i=1∑n−1(k=1∑dai,kan,k)2≡n−1(mod3)
强行拆开
∑i=1n−1∑x=1d∑y=1dai,xan,xai,yan,y≡n−1(mod3)\sum_{i=1}^{n-1}\sum_{x=1}^{d}\sum_{y=1}^da_{i,x}a_{n,x}a_{i,y}a_{n,y}\equiv n-1\pmod{3}i=1∑n−1x=1∑dy=1∑dai,xan,xai,yan,y≡n−1(mod3)
∑x=1d∑y=1d(∑i=1n−1ai,xai,y)an,xan,y≡n−1(mod3)\sum_{x=1}^{d}\sum_{y=1}^d(\sum_{i=1}^{n-1}a_{i,x}a_{i,y})a_{n,x}a_{n,y}\equiv n-1\pmod{3}x=1∑dy=1∑d(i=1∑n−1ai,xai,y)an,xan,y≡n−1(mod3)
然后就可以维护了
复杂度O(ndk−1)O(nd^{k-1})O(ndk−1)
#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #define MAXN 100005 #define MAXM 105 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } int id[MAXN],a[MAXN][MAXM]; int c[MAXM][MAXM],s[MAXM]; int n,d,k; inline bool check(int x,int y) {int sum=0;for (int i=1;i<=d;i++) sum+=a[x][i]*a[y][i];return sum%k==0; } int main() {n=read(),d=read(),k=read();for (int i=1;i<=n;i++)for (int j=1;j<=d;j++)a[i][j]=read()%k;for (int i=1;i<=n;i++) id[i]=i;int T=10;while (T--){random_shuffle(id+1,id+n+1);if (k==2){for (int i=1;i<=d;i++) s[i]=0;for (int i=1;i<=n;i++){int sum=0;for (int j=1;j<=d;j++) sum+=s[j]*a[id[i]][j];if (sum%2!=(i-1)%2){for (int x=1;x<i;x++)if (check(id[x],id[i])){if (id[i]>id[x]) swap(id[i],id[x]);printf("%d %d\n",id[i],id[x]);return 0;}}for (int j=1;j<=d;j++) s[j]+=a[id[i]][j];}}else{for (int i=1;i<=d;i++)for (int j=1;j<=d;j++)c[i][j]=0;for (int i=1;i<=n;i++){int sum=0;for (int x=1;x<=d;x++)for (int y=1;y<=d;y++)sum+=c[x][y]*a[id[i]][x]*a[id[i]][y];if (sum%3!=(i-1)%3){for (int j=1;j<i;j++)if (check(id[j],id[i])){if (id[j]>id[i]) swap(id[j],id[i]);printf("%d %d\n",id[j],id[i]);return 0;}}for (int x=1;x<=d;x++)for (int y=1;y<=d;y++)c[x][y]+=a[id[i]][x]*a[id[i]][y];}}}puts("-1");return 0; }总结
以上是生活随笔为你收集整理的【NOI2013】向量内积【随机化】的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 樱花唯美句子简短 这些句子都可直接用
- 下一篇： OI训练记录