QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#237827#7687. Randias Permutation Taskucup-team958#RE 1ms5856kbC++142.0kb2023-11-04 15:06:422023-11-04 15:06:45

Judging History

你现在查看的是最新测评结果

  • [2023-11-04 15:06:45]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5856kb
  • [2023-11-04 15:06:42]
  • 提交

answer

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int maxn=185;
const int mod=1e9+7;
const int P=1e7+7;
const int maxs=400010;
il int read(){
	int x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
int n,m;
struct pre{
	int p[10];
	int val(int sum=0){
		for(int i=1;i<=n;i++)
			sum=(1ll*sum*n+p[i]-1)%mod;
		return sum%P;
	}
	bool operator ==(pre a)const{
		for(int i=1;i<=n;i++)
			if(p[i]!=a.p[i]) return 0;
		return 1;
	}
};
struct node{
	pre v;
	int k,to;
}e[2][maxs];
int head[2][P],ecnt[2];
int Find(int t,pre &x,int k){
	int v=x.val();
	for(int i=head[t][v];i;i=e[t][i].to)
		if(e[t][i].v==x&&e[t][i].k==k) return i;
	e[t][++ecnt[t]].v=x,e[t][ecnt[t]].k=k;
	e[t][ecnt[t]].to=head[t][v],head[t][v]=ecnt[t];
}
struct PRE{
	int p[maxn];
	bool operator <(PRE x)const{
		for(int i=1;i<=n;i++)
			if(p[i]<x.p[i]) return 1;
			else if(p[i]>x.p[i]) return 0;
		return 0;
	}
};
map<PRE,bool>M;
int A[maxn][maxn];
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			A[i][j]=read();
	int k;
	pre t1,t2;
	if(m<=18){
		int state=1<<m;
		PRE T1,T2; int ans=0;
		for(int s=1;s<state;s++){
			for(int i=1;i<=n;i++) T1.p[i]=i;
			for(int i=1;i<=m;i++)
				if(s&(1<<i-1)){
					for(int j=1;j<=n;j++) T2.p[j]=T1.p[A[i][j]];
					for(int j=1;j<=n;j++) T1.p[j]=T2.p[j];
				}
			if(!M[T1]) M[T1]=1,ans++;
		}
		printf("%d\n",ans);
		return 0;
	}
	for(int i=1;i<=n;i++) t1.p[i]=i;
	Find(0,t1,0);
	for(int i=1;i<=m;i++){
		int i1=i-1&1,i2=i&1;
//		printf("!!!%d\n",ecnt[i1]);
		for(int j=1;j<=ecnt[i1];j++){
			t1=e[i1][j].v,k=e[i1][j].k;
			for(int k=1;k<=n;k++) 
				t2.p[k]=t1.p[A[i][k]];
			Find(i2,t1,k),Find(i2,t2,1);
		}
		for(int j=1;j<=ecnt[i1];j++)
			head[i1][e[i1][j].v.val()]=0;
		ecnt[i1]=0;
	}
	int ans=0;
	for(int i=1;i<=ecnt[m&1];i++)
		if(e[m&1][i].k) ans++;
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5856kb

input:

5 4
1 2 3 4 5
5 1 3 4 2
3 4 1 5 2
5 2 4 1 3

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

2 1
2 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: -100
Runtime Error

input:

1 180
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

output:


result: