记录编号	219544	评测结果	AAAAAAAAAA
题目名称	[POJ 1282]庆典的日期	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-01-14 21:59:57	内存使用	0.49 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=210,maxn=0x7fffffff;
int N,P;
class miku//置换群
{
public:
	int a[SIZEN];
	miku(){}
	void print()
	{
		for(int i=1;i<=N;i++) cout<<a[i]<<" ";
		cout<<endl;
	}
	void clear()
	{
		for(int i=0;i<=N;i++) a[i]=i;
	}
	void operator *=(miku b)
	{
		for(int i=1;i<=N;i++)	a[i]=b.a[a[i]];
	}
	void inverse()
	{
		int at[SIZEN];
		for(int i=1;i<=N;i++) at[i]=a[i];
		for(int i=1;i<=N;i++) a[at[i]]=i;
	}
}T[SIZEN];
int rm[SIZEN],ra[SIZEN];
int gcd(int a,int b,int &x,int &y)
{
	if(!b) {x=1,y=0;return a;}
	int re=gcd(b,a%b,y,x);
	y-=a/b*x;
	return re;
}
int China(int n,int rm[],int ra[])
{
	int A=0,M=1,k,t,g,tem;
	for(int i=1;i<=n;i++)
	{
		tem=ra[i]-A;
		g=gcd(M,rm[i],k,t);
		if(tem%g) return -1;
		k*=tem/g;
		A+=k*M;
		M=(M*rm[i])/g;
		A=(A+M)%M;
	}
	return A;
}
bool find(miku A,int k,int goal)
{
	int now=k,r=-1,m=1;
	if(now==goal) r=0;
//if(k==6) cout<<now<<endl;
	now=A.a[k];
	while(now!=k)
	{
		if(now==goal) r=m;
		now=A.a[now];
		m++;
	}
	rm[k]=m;ra[k]=r;
	if(r==-1) return 0;
	return 1;
}
int rlog(miku A,miku B)
{
	for(int i=1;i<=N;i++)
	{
		if(!find(A,i,B.a[i])) return -1;
		//if(i==6) cout<<"arrive"<<endl;
		//cout<<i<<endl;
	}
	return China(N,rm,ra);
}
void read()
{
	scanf("%d%d",&N,&P);
	for(int i=1;i<=N;i++) for(int j=1;j<=P;j++) scanf("%d",&T[j].a[i]);
}
miku Tstep,Thead,Tdeah;
void work()
{
	int ans=1e9;
	Tstep.clear();Thead.clear();
	for(int i=1;i<=P;i++) Tstep*=T[i];
	for(int i=1;i<=P;i++)
	{
		Thead*=T[i];
		Tdeah=Thead;
		Tdeah.inverse();
		//Tstep.print();
		//Tdeah.print();
		int tem=rlog(Tstep,Tdeah);
		//cout<<tem<<endl;
		if(tem!=-1) ans=min(ans,tem*P+i);
	}
	if(ans!=1e9) printf("%d",ans);
	else printf("No one knows.");
}
int main()
{
	freopen("celebration.in","r",stdin);
	freopen("celebration.out","w",stdout);
	read();
	work();
	return 0;
}