中小企业网站建设与管理课后答案,holy荷勒公司介绍,如何做网站frontpage,网页设计师的工作时间传送门
题意#xff1a;给nnn个ddd维向量#xff0c;询问是否有两个向量内积#xff08;对应位乘积和#xff09;为kkk的倍数 n≤100000,d≤100,k2,3n \leq100000,d\leq100,k2,3n≤100000,d≤100,k2,3
考虑每个向量能否与之前的某一个匹配
如果我们找到某一个与之前的可…传送门
题意给nnn个ddd维向量询问是否有两个向量内积对应位乘积和为kkk的倍数
n≤100000,d≤100,k2,3n \leq100000,d\leq100,k2,3n≤100000,d≤100,k2,3
考虑每个向量能否与之前的某一个匹配
如果我们找到某一个与之前的可以匹配就可以O(nd)O(nd)O(nd)得到答案。我们要做的是排除不能匹配的答案。
以下mmm为题中给的kkk
即
∀1≤in,∑k1dai,kan,k≠0(modm)\forall1\leq in,\sum_{k1}^{d}a_{i,k}a_{n,k}\neq0\pmod{m}∀1≤in,k1∑dai,kan,k0(modm)
当m2m2m2时
∀1≤in,∑k1dai,kan,k≡1(mod2)\forall1\leq in,\sum_{k1}^{d}a_{i,k}a_{n,k}\equiv1\pmod{2}∀1≤in,k1∑dai,kan,k≡1(mod2)
弱化得
∑i1n−1∑k1dai,kan,k≡n−1(mod2)\sum_{i1}^{n-1}\sum_{k1}^{d}a_{i,k}a_{n,k}\equiv n-1\pmod{2}i1∑n−1k1∑dai,kan,k≡n−1(mod2)
∑k1d(∑i1n−1ai,k)an,k≡n−1(mod2)\sum_{k1}^{d}(\sum_{i1}^{n-1}a_{i,k})a_{n,k}\equiv n-1\pmod{2}k1∑d(i1∑n−1ai,k)an,k≡n−1(mod2)
维护个前缀和判一下如果不满足说明一定有答案
感性理解理论上这个答案是随便找得到的所以随机打乱几次能大概率出解
当m3m3m3时同理
∀1≤in,∑k1dai,kan,k≡1or2(mod3)\forall1\leq in,\sum_{k1}^{d}a_{i,k}a_{n,k}\equiv1 or 2\pmod{3}∀1≤in,k1∑dai,kan,k≡1or2(mod3)
平方一下
∀1≤in,(∑k1dai,kan,k)2≡1(mod3)\forall1\leq in,(\sum_{k1}^{d}a_{i,k}a_{n,k})^2\equiv1 \pmod{3}∀1≤in,(k1∑dai,kan,k)2≡1(mod3)
∑i1n−1(∑k1dai,kan,k)2≡n−1(mod3)\sum_{i1}^{n-1}(\sum_{k1}^{d}a_{i,k}a_{n,k})^2\equiv n-1\pmod{3}i1∑n−1(k1∑dai,kan,k)2≡n−1(mod3)
强行拆开
∑i1n−1∑x1d∑y1dai,xan,xai,yan,y≡n−1(mod3)\sum_{i1}^{n-1}\sum_{x1}^{d}\sum_{y1}^da_{i,x}a_{n,x}a_{i,y}a_{n,y}\equiv n-1\pmod{3}i1∑n−1x1∑dy1∑dai,xan,xai,yan,y≡n−1(mod3)
∑x1d∑y1d(∑i1n−1ai,xai,y)an,xan,y≡n−1(mod3)\sum_{x1}^{d}\sum_{y1}^d(\sum_{i1}^{n-1}a_{i,x}a_{i,y})a_{n,x}a_{n,y}\equiv n-1\pmod{3}x1∑dy1∑d(i1∑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 ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();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 sum0;for (int i1;id;i) suma[x][i]*a[y][i];return sum%k0;
}
int main()
{nread(),dread(),kread();for (int i1;in;i)for (int j1;jd;j)a[i][j]read()%k;for (int i1;in;i) id[i]i;int T10;while (T--){random_shuffle(id1,idn1);if (k2){for (int i1;id;i) s[i]0;for (int i1;in;i){int sum0;for (int j1;jd;j) sums[j]*a[id[i]][j];if (sum%2!(i-1)%2){for (int x1;xi;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 j1;jd;j) s[j]a[id[i]][j];}}else{for (int i1;id;i)for (int j1;jd;j)c[i][j]0;for (int i1;in;i){int sum0;for (int x1;xd;x)for (int y1;yd;y)sumc[x][y]*a[id[i]][x]*a[id[i]][y];if (sum%3!(i-1)%3){for (int j1;ji;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 x1;xd;x)for (int y1;yd;y)c[x][y]a[id[i]][x]*a[id[i]][y];}}}puts(-1);return 0;
}
