【fake题解】[NOI2013]向量内积
做法1
大暴力。哪里不会T哪里。
做法2
- 所有数都%=k不影响结果。（废话
- k的取值只有2和3，所以肯定是要分类讨论的。k=2肯定简单些啦。
k=2
出现的数只会有0和1
两个0或1相乘，乘积就是与之后的值
所以可以把向量用bitset存起来，这样计算就是(O(frac{d}{32}))，结果是3.125
然后上暴力，(O(frac{n^2}{2} imes 3.125))，能卡过（事实并非如此，飞起了）
k=3
先讨论前14个点的k=3
出现的数只会有012
bitset似乎无法完成这项任务
然而实际上可以的
想一想0和其它的乘，贡献都是0
1和2单独考虑
1*1=1
2*2=1
1*2=2
把1看成0,2看成1，这就是个xor
所以用两个bitset，一个存0的，一个存2的，搞定
复杂度和上面一样
再讨论后面的
可以用int代替bitset，计算的复杂度降到(O(1))
然后。。。
gzy和我用一样的方法A掉了。。。
// 我死活过不去的代码
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<ctime>
#include<cstdlib>
#include<set>
#define il inline
#define rg register
#define vd void
#define sta static
typedef long long ll;
using namespace std;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,d,k,x,p[100001];
namespace k2{
il vd main(){
for(rg int i=1;i<=n;++i)p[i]=i;
bitset<100>s[20001];
for(rg int i=1;i<=n;++i)
for(rg int j=0;j<d;++j)
s[i][j]=gi()&1;
for(rg int i=1;i<=n;++i){
x=rand()%n+1;
swap(s[i],s[x]);
swap(p[i],p[x]);
}
for(rg int i=n;i;--i)
for(rg int j=i+1;j<=n;++j)
if(((s[i]&s[j]).count()&1)==0){
if(p[i]>p[j])swap(p[i],p[j]);
printf("%d %d
",p[i],p[j]);
return;
}
printf("-1 -1");
}
}
namespace k32{
il vd main(){
for(rg int i=1;i<=n;++i)p[i]=i;
bitset<100>s[100001],S[100001],a;
for(rg int i=1;i<=n;++i)
for(rg int j=0;j<d;++j){
x=gi()%3;
s[i][j]=x==2;
S[i][j]=x==0;
}
for(rg int i=1;i<=n;++i){
x=rand()%n+1;
swap(s[i],s[x]);
swap(S[i],S[x]);
swap(p[i],p[x]);
}
for(rg int i=n;i;--i)
for(rg int j=i+1;j<=n;++j){
a=s[i]^s[j];
x=(a&(~(S[i]|S[j]))).count()*2;
x+=d-(a|(S[i]|S[j])).count();
if(x%3==0){
if(p[i]>p[j])swap(p[i],p[j]);
printf("%d %d
",p[i],p[j]);
return;
}
}
puts("-1 -1");
}
}
namespace k31{
il int count(int x){
int ret=0;
while(x)++ret,x-=x&-x;
return ret;
}
struct yyb{int a,b,c;};
bool operator <(const yyb&a,const yyb&b){
return a.a==a.b?a.b<b.b:a.b<b.b;
}
il vd main(){
int a;
yyb s[100001];
set<pair<int,int> >l,ll;
int N=n,n=0,A,B;
for(rg int i=1;i<=N;++i){
A=B=0;
for(rg int j=0;j<d;++j){
x=gi()%3;
if(x==2)A|=1<<j;
if(x==0)B|=1<<j;
}
if(l.find(make_pair(A,B))==l.end())++n,s[n]=(yyb){A,B,i},l.insert(make_pair(A,B));
//else if(ll.find(make_pair(A,B))==ll.end())++n,s[n]=(yyb){A,B,i},ll.insert(make_pair(A,B));
}
sort(s+1,s+n+1);
for(rg int i=1;i<n;++i)
for(rg int j=i+1;j<=n;++j){
a=s[i].a^s[j].a;
x=count((a&(~(s[i].b|s[j].b))))*2;
x+=d-count((a|(s[i].b|s[j].b)));
if(x%3==0){
if(s[i].c>s[j].c)swap(s[i].c,s[j].c);
printf("%d %d
",s[i].c,s[j].c);
return;
}
}
printf("-1 -1");
}
}
int main(){
srand(time(NULL));
n=gi(),d=gi(),k=gi();
if(k==2)k2::main();
else if(d<=30)k31::main();
else k32::main();
return 0;
}
// gzy无敌AC代码
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define RG register
#define REP(i,a,b) for(RG int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(RG int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
int sum=0,p=1;char ch=getchar();
while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
if(ch=='-')p=-1,ch=getchar();
while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
return sum*p;
}
const int maxn=2e5+20;
int n,d,k;
bitset<120>a[maxn],b[maxn],c[maxn];
void init()
{
n=read();d=read();k=read();
}
int A[maxn],B[maxn],C[maxn],p[maxn],pp[maxn];
inline bool cmp(const int a,const int b)
{
if(A[a]==A[b])return B[a]==B[b]?C[a]<C[b]:B[a]<B[b];else return A[a]<A[b];
}
int v[1<<20];
inline int count(int a)
{
return v[a & (1<<16)-1]+v[a>>16];
}
void doing()
{
REP(i,1,(1<<20)-1)v[i]=v[i>>1]+(i & 1);
if(k==2)
{
REP(i,1,n)REP(j,0,d-1)if(read() & 1)a[i].set(j);
REP(i,1,n-1)REP(j,i+1,n)if(!((a[i]|a[j]).count() & 1))
{
printf("%d %d
",i,j);
exit(0);
}
}else
{
if(n<=10000)
{
REP(i,1,n)REP(j,0,d-1)
{
int x=read()%3;
if(x!=0)a[i].set(j);
if(x!=2)b[i].set(j);
if(x!=1)c[i].set(j);
}
REP(i,1,n-1)REP(j,i+1,n)
{
int x=((a[i] & a[j]).count()-2*((a[i] & b[i])&(a[j] & c[j])).count()-2*((a[j]&b[j])&(a[i]&c[i])).count());
if(x%3==0)
{
printf("%d %d
",i,j);
exit(0);
}
}
}else
{
REP(i,1,n)REP(j,0,d-1)
{
int x=read()%3;
if(x!=0)A[i]|=1<<j;
if(x!=2)B[i]|=1<<j;
if(x!=1)C[i]|=1<<j;
}
REP(i,1,n)p[i]=i;
sort(p+1,p+n+1,cmp);
int tot=1;
pp[1]=p[1];
REP(i,2,n)
{
int u=p[i],v=pp[tot];
if(A[u]!=A[v] || B[u]!=B[v] || C[u]!=C[v])pp[++tot]=p[i];
else{
int x=count(A[u]&A[v]);
if(x%3==0)
{
if(u>v)swap(u,v);
printf("%d %d
",u,v);
return;
}
}
}
REP(i,1,tot-1)REP(j,i+1,tot)
{
int u=pp[i],v=pp[j],x=(count(A[u]&A[v])-2*count((A[u]&B[u])&(A[v]&C[v]))-2*count((A[u]&C[u])&(A[v]&B[v])));
if(x%3==0)
{
if(u>v)swap(u,v);
printf("%d %d
",u,v);
return;
}
}
}
}
puts("-1 -1");
}
int main()
{
init();
doing();
return 0;
}