傳送門

題意：給$n$個$d$維向量，詢問是否有兩個向量內(nèi)積（對應(yīng)位乘積和）為$k$的倍數(shù)

$n\le 100000,d\le 100,k=2,3$

考慮每個向量能否與之前的某一個匹配

如果我們找到某一個與之前的可以匹配，就可以$O(nd)$得到答案。我們要做的是排除不能匹配的答案。

（以下$m$為題中給的$k$）

即

$$?1\le i<n,\sum _{k=1}^d{a}_{i,k}{a}_{n,k}=0(\mathrm{m}\mathrm{o}\mathrm{d}m)$$

當(dāng)$m=2$時

$$?1\le i<n,\sum _{k=1}^d{a}_{i,k}{a}_{n,k}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)$$

弱化得

$$\sum _{i=1}^{n?1}\sum _{k=1}^d{a}_{i,k}{a}_{n,k}\equiv n?1(\mathrm{m}\mathrm{o}\mathrm{d}2)$$

$$\sum _{k=1}^d(\sum _{i=1}^{n?1}{a}_{i,k})a_{n,k}\equiv n?1(\mathrm{m}\mathrm{o}\mathrm{d}2)$$

維護個前綴和判一下，如果不滿足說明一定有答案

感性理解，理論上這個答案是隨便找得到的，所以隨機打亂幾次能大概率出解

當(dāng)$m=3$時同理

$$?1\le i<n,\sum _{k=1}^d{a}_{i,k}{a}_{n,k}\equiv 1or2(\mathrm{m}\mathrm{o}\mathrm{d}3)$$

平方一下

$$?1\le i<n,(\sum _{k=1}^d{a}_{i,k}{a}_{n,k}{)}^2\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3)$$

$$\sum _{i=1}^{n?1}(\sum _{k=1}^d{a}_{i,k}{a}_{n,k}{)}^2\equiv n?1(\mathrm{m}\mathrm{o}\mathrm{d}3)$$

強行拆開

$$\sum _{i=1}^{n?1}\sum _{x=1}^d\sum _{y=1}^d{a}_{i,x}{a}_{n,x}{a}_{i,y}{a}_{n,y}\equiv n?1(\mathrm{m}\mathrm{o}\mathrm{d}3)$$

$$\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(\mathrm{m}\mathrm{o}\mathrm{d}3)$$

然后就可以維護了

復(fù)雜度$O(n{d}^{k?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; }

總結(jié)

以上是生活随笔為你收集整理的【NOI2013】向量内积【随机化】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。