QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#237759 | #7687. Randias Permutation Task | ucup-team958# | RE | 0ms | 3788kb | C++14 | 1.9kb | 2023-11-04 14:55:09 | 2023-11-04 14:55:09 |
Judging History
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;
}
}A[maxn];
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 main(){
n=read(),m=read();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
A[i].p[j]=read();
int k;
pre t1,t2;
if(m<=19){
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<=n;i++)
if(s&(1<<i-1)){
for(int j=1;j<=n;j++) T2.p[j]=T1.p[A[i].p[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;
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].p[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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
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: 3788kb
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 ...