F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 4128 >> My code
lzxzy @ 2019-07-18 16:27:19
[ Quote ] [ Edit ] [ Delete ] 1#
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

template<typename T>
inline T read()
{
T x=0,f=1;char c=getchar();
while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}

const int MAXK=75;
const int MAXN=37779;
const int MAXM=10000;
int n,mod,id;

struct weight
{
long long cnt,sum,xor_sum;

weight(){cnt=sum=xor_sum=0;}

bool operator == (struct weight tmp)
{
return (cnt==tmp.cnt)&(sum==tmp.sum)&(xor_sum==tmp.xor_sum);
}
};

struct matrix
{
struct weight w;
int a[MAXK][MAXK];

matrix(){memset(a,0,sizeof(a));}

void read_in()
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
a[i][j]=read<int>();
w.cnt|=a[i][j];
w.xor_sum^=a[i][j];
w.sum+=(i*(n-1)+j)*a[i][j];
}
}

struct matrix operator * (struct matrix tmp)
{
struct matrix ans;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
for (int k=1;k<=n;k++)
ans.a[i][j]=(ans.a[i][j]+a[i][k]*tmp.a[k][j]%mod)%mod;
ans.w.cnt|=ans.a[i][j];
ans.w.xor_sum^=ans.a[i][j];
ans.w.sum+=(i*(n-1)+j)*ans.a[i][j];
}
return ans;
}
}a,b;

struct Hash
{
int val,nx;
struct weight v;
}Hash[MAXM];
int head[MAXN];

inline void insert(struct matrix num,int k)
{
int u=num.w.cnt%MAXN;
id++;Hash[id].v=num.w;Hash[id].val=k;Hash[id].nx=head[u];
head[u]=id;
}

inline int find(struct matrix num)
{
int u=num.w.cnt%MAXN;
for (int k=head[u];k>0;k=Hash[k].nx)
if (Hash[k].v==num.w) return Hash[k].val;
return -1;
}

inline int BSGS(struct matrix a,struct matrix b,int p)
{
struct matrix q,d;
for (int i=1;i<=n;i++)
{
q.a[i][i]=1,d.a[i][i]=1;
q.w.cnt|=q.a[i][i];
q.w.xor_sum^=q.a[i][i];
q.w.sum+=(i*(n-1)+i)*q.a[i][i];
d.w.cnt|=d.a[i][i];
d.w.xor_sum^=d.a[i][i];
d.w.sum+=(i*(n-1)+i)*d.a[i][i];
}
int m=ceil(sqrt((double)p)),res;
for (int i=0;i<m;i++) {insert(q*b,i); q=q*a;}
for (int i=1;i<=m;i++)
{
d=d*q;res=find(d);
if (res!=-1) return i*m-res;
}
return -1;
}

int main()
{
n=read<int>();mod=read<int>();
a.read_in();b.read_in();
printf("%d\n",BSGS(a,b,mod));
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back