QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#466892#7687. Randias Permutation Taskyurongyi#WA 222ms33748kbC++142.5kb2024-07-08 11:42:162024-07-08 11:42:17

Judging History

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

  • [2024-07-08 11:42:17]
  • 评测
  • 测评结果:WA
  • 用时:222ms
  • 内存:33748kb
  • [2024-07-08 11:42:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[181][181],sz,flag,b[181],je[189],ans,dp[500005][2];
const long long mod=1e9+7;
map<long long,bool> mm,nn;
void dfs(int x){
//	cout<<x<<endl;
	if(x>=m+1){
		long long sum=0,sm=0;
		for(int i=1;i<=n;++i){
			sum=(sum+(b[i]*(je[n-i+1]))%mod)%mod;
			sm=(sm+b[i]*(i+je[n-i]))%mod;
//			cout<<b[i]<<' ';
		}
//		cout<<sum<<endl;
		if(mm[sum]!=1)mm[sum]=1,ans++;
		if(nn[sm]!=1)nn[sm]=1;
		return;
	}
	int c[181];
	for(int i=1;i<=n;++i){
		c[i]=b[i];
	}
	dfs(x+1);
//	for(int i=1;i<=n;++i)cout<<c[i]<<endl;
	for(int i=1;i<=n;++i){
		b[i]=c[a[x][i]];//cout<<a[x][i]<<endl;
	}
	bool fg=1;
	for(int i=1;i<=n;++i)if(b[i]!=i)fg=0;
	if(fg)flag=1;
	dfs(x+1);
	return;
}
int main(){
	cin>>n>>m;
	je[0]=1;
	for(int i=1;i<=188;++i)je[i]=je[i-1]*i%mod;
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			cin>>a[i][j];
		}
	}
	if(n<=8){
		for(int i=1;i<=n;++i)a[0][i]=i;
		for(int i=1;i<=1;++i){
			int sum=0,e[10],d[10]={0,1,2,3,4,5,6,7,8,9};
			for(int k=1;k<=n;++k){
				e[k]=a[0][k];
				int o=0,nw=0;
				while(d[nw]!=e[k]){
					if(d[nw]!=0)o++;
					nw++;
				}
				d[nw]=0;
				sum+=o*je[n-k];
			}
			dp[sum][1]=1;
			sz=sum;
		}
//		cout<<"SZ="<<sz<<endl;
		for(int i=1;i<=m;++i){
			for(int j=0;j<=je[n];++j)dp[j][(i+1)%2]=0;
//			for(int j=0;j<=je[n];++j)cout<<dp[j][i%2]<<' ';
//			cout<<endl;
			for(int j=0;j<=je[n];++j){
//				cout<<j<<' '<<je[n]<<endl;
				if(dp[j][i%2]==0)continue;
				int c[10],e[10],sum=0,d[10]={0,1,2,3,4,5,6,7,8,9};
				for(int k=1;k<=n;++k){
					int l=(j/je[n-k])%(n+1-k);
					int o=1;
//					cout<<l<<' '<<o<<' '<<k<<endl;
					while(l>=0){
						if(d[o]>0&&l>0)l--;
						else if(d[o]>0)c[k]=d[o],d[o]=0,l--;
						o++;
					}
//					cout<<"DONE"<<endl;
				}
//				cout<<j<<' ';
//				for(int p=1;p<=n;++p)cout<<c[p]<<' ';
//				cout<<endl;
				for(int p=0;p<=9;++p)d[p]=p;
				dp[j][(i+1)%2]=1;
				for(int k=1;k<=n;++k){
					int o=0,nw=0;
					e[k]=c[a[i][k]];
					while(d[nw]!=e[k]){
						if(d[nw]!=0)o++;
						nw++;
					}
					d[nw]=0; 
//					cout<<e[k]<<' '<<o<<' ';
					sum+=o*je[n-k];
				}
//				cout<<sum<<endl;
				if(sum==sz)flag=1;
				dp[sum][(i+1)%2]=1;
			}
		}
		for(int i=1;i<=je[n];++i){
			if(dp[i][(m+1)%2]!=0)ans++;
		}
		cout<<(ans+flag)%mod<<endl;
	}else{
		for(int j=1;j<=n;++j)b[j]=j;
		dfs(1);
		cout<<(ans-1+flag)%mod<<endl;
	}
	return 0;
}
/*
8 3
1 2 3 4 5 6 8 7 
1 2 3 4 5 7 8 6
1 2 3 4 5 8 7 6 
*/
/*
5 5
1 2 3 4 5
1 2 3 4 5 
1 2 4 3 5
1 2 3 5 4
1 2 5 3 4
*/ 

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3648kb

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: 1ms
memory: 5684kb

input:

2 1
2 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

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:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

180 1
52 71 167 89 165 102 119 125 9 128 180 24 48 172 108 22 164 28 159 111 30 91 67 51 136 97 126 133 177 65 115 157 114 11 171 178 23 127 163 103 99 18 56 94 176 77 44 1 124 74 61 87 4 40 63 92 169 84 146 6 88 55 152 49 10 90 43 174 70 50 69 154 73 147 110 20 82 59 112 12 64 143 16 138 5 170 155 ...

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 90
1 2
1 2
1 2
1 2
2 1
2 1
2 1
2 1
1 2
2 1
1 2
1 2
1 2
2 1
2 1
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
2 1
1 2
1 2
1 2
2 1
2 1
1 2
2 1
1 2
2 1
1 2
1 2
2 1
1 2
2 1
2 1
2 1
2 1
1 2
2 1
2 1
2 1
2 1
1 2
1 2
2 1
2 1
1 2
1 2
1 2
2 1
1 2
2 1
2 1
1 2
2 1
2 1
2 1
2 1
2 1
2 1
2 1
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2...

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

90 2
43 44 28 69 66 18 5 23 87 8 24 89 31 29 81 1 68 2 78 53 49 54 4 13 77 61 33 57 63 85 55 79 46 35 45 64 65 42 30 6 19 74 82 80 17 26 32 59 7 72 16 3 47 73 39 36 25 34 56 86 71 62 84 40 41 11 50 27 20 14 37 12 38 58 48 83 76 70 51 88 22 90 21 9 10 60 15 52 75 67
9 73 52 51 81 16 71 77 6 57 11 75 ...

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

3 60
2 1 3
3 1 2
3 2 1
1 2 3
1 2 3
3 2 1
3 1 2
2 3 1
2 1 3
3 1 2
2 3 1
2 3 1
2 1 3
3 2 1
3 1 2
3 2 1
1 2 3
2 1 3
2 1 3
2 1 3
2 3 1
2 3 1
2 3 1
3 1 2
1 2 3
3 1 2
2 3 1
2 3 1
2 1 3
1 2 3
3 1 2
2 1 3
2 3 1
2 3 1
2 3 1
3 1 2
2 3 1
1 2 3
1 2 3
3 2 1
3 1 2
3 1 2
2 3 1
1 3 2
3 1 2
1 3 2
1 2 3
1 3 2
1 3 2
3...

output:

6

result:

ok 1 number(s): "6"

Test #8:

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

input:

60 3
35 38 36 43 59 60 20 16 8 51 58 18 33 26 44 7 41 27 39 9 37 48 25 40 30 14 21 13 5 1 19 11 3 28 57 47 17 56 45 34 12 49 29 32 55 24 31 50 42 22 53 23 4 15 2 46 6 10 52 54
41 49 10 55 3 38 35 29 6 26 2 46 58 39 24 47 51 25 44 37 42 43 20 53 60 12 40 17 28 13 27 57 15 52 8 22 11 14 59 21 48 9 32 ...

output:

7

result:

ok 1 number(s): "7"

Test #9:

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

input:

4 45
1 3 4 2
2 3 4 1
4 1 3 2
4 1 2 3
1 4 3 2
3 4 2 1
2 3 4 1
1 3 2 4
2 1 4 3
4 2 3 1
4 1 3 2
1 3 4 2
2 4 3 1
4 2 3 1
1 3 2 4
3 2 1 4
2 3 4 1
3 2 4 1
1 2 4 3
4 1 2 3
4 3 2 1
3 4 1 2
1 3 2 4
2 4 3 1
4 2 1 3
2 3 4 1
4 2 1 3
4 2 3 1
1 2 3 4
1 3 2 4
1 4 3 2
3 2 4 1
2 3 1 4
1 3 4 2
3 1 2 4
1 3 2 4
3 2 4 1...

output:

24

result:

ok 1 number(s): "24"

Test #10:

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

input:

45 4
44 38 33 27 25 17 35 4 22 41 15 3 10 16 21 28 23 19 34 37 2 32 43 12 6 31 29 9 45 18 11 30 13 26 42 5 39 40 8 24 14 1 7 20 36
28 43 12 34 21 7 20 26 13 1 25 4 44 32 11 15 33 18 14 5 6 42 45 36 9 35 2 30 38 10 41 27 17 23 19 8 29 16 3 37 40 31 39 22 24
5 22 23 43 36 33 29 39 44 9 35 34 7 42 8 11...

output:

15

result:

ok 1 number(s): "15"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

18 10
13 4 18 16 1 8 17 6 14 2 10 12 5 9 3 11 15 7
1 7 15 13 12 2 17 18 16 11 9 8 6 14 3 4 10 5
1 9 3 4 6 14 5 10 12 13 7 8 16 2 15 17 18 11
2 10 16 3 17 8 4 13 12 11 5 7 14 9 1 15 18 6
7 9 4 14 10 2 17 6 8 16 1 13 12 5 11 18 15 3
13 4 16 10 5 2 9 1 11 3 18 8 6 12 15 14 7 17
9 14 18 17 2 12 16 10 15...

output:

1023

result:

ok 1 number(s): "1023"

Test #12:

score: -100
Wrong Answer
time: 222ms
memory: 33748kb

input:

10 18
9 6 4 8 3 7 10 1 2 5
10 9 8 3 5 6 1 2 7 4
8 2 5 4 9 3 1 7 6 10
10 5 2 8 1 6 4 7 9 3
2 3 5 4 10 9 6 8 7 1
6 7 8 10 5 3 4 1 9 2
10 6 4 2 1 5 3 8 9 7
6 8 9 1 2 4 5 3 7 10
7 6 3 1 5 9 2 10 4 8
10 5 7 4 9 1 2 6 3 8
5 4 6 9 3 7 8 1 2 10
5 9 8 2 7 1 3 10 6 4
5 2 10 3 7 1 4 6 9 8
1 10 2 6 5 7 8 9 3 4
...

output:

251033

result:

wrong answer 1st numbers differ - expected: '252941', found: '251033'