QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#571780#9353. Interesting PermutationhuaxiamengjinRE 0ms5220kbC++14726b2024-09-18 08:34:422024-09-18 08:34:42

Judging History

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

  • [2024-09-18 08:34:42]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:5220kb
  • [2024-09-18 08:34:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NN=1e9+7;
int p[100100],ni[100100];
int n,a[100100];
int mi(int x,int y){
	int sum=1;
	for (;y;y>>=1,x=x*x%NN)
	if(y&1)sum=sum*x%NN;
	return sum;
}
int c(int x,int y){
	if(x<0||y<0||x<y)return 0;
	return p[x]*ni[x-y]%NN;
}
void solve(){
	cin>>n;
	for (int i=1;i<=n;i++)
	cin>>a[i];
	int pre=n-1;
	int ans=1;
	for (int i=n;i>=1;i--){
		if(a[i]!=pre){
			ans=ans*2%NN*c(pre-i,pre-a[i]-1)%NN;
			pre=a[i];
		}
	}
	cout<<ans<<"\n";
}
signed main(){
	int N=1e5;
	p[0]=1;
	for (int i=1;i<=N;i++)
	p[i]=p[i-1]*i%NN;
	ni[N]=mi(p[N],NN-2);
	for (int i=N;i;i--)
	ni[i-1]=ni[i]*i%NN;
	int T;cin>>T;
	while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
3
0 2 2
3
0 1 2
3
0 2 3

output:

2
4
0

result:

ok 3 lines

Test #2:

score: -100
Runtime Error

input:

10039
14
5 6 7 8 9 10 11 12 13 13 13 13 13 13
14
0 5 6 7 8 9 10 11 12 13 14 14 14 14
1
1
14
0 5 4 8 9 10 11 12 13 13 13 13 13 13
45
0 1 1 2 2 3 5 5 6 6 8 9 11 13 15 17 18 18 20 22 22 24 26 26 26 26 27 27 27 28 30 32 32 33 34 34 34 36 36 38 38 38 39 39 44
24
0 2 3 5 7 9 9 10 11 12 13 14 14 14 14 15 1...

output:

256
0
0
0
0
0
24576
0
0
0
0
0
658159182
0
805306368
8
572589350
12288
2
0
981283070
0
0
2
0
0
0
0
4423680
0
0
14155776
16
0
768
0
0
0
855189487
0
2
0
0
0
0
2
0
2
797370259
0
0
0
0
4
0
0
0
301989888
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
192
0
0
12288
0
0
2
8
0
0
495514526
0
0
955131071
768
0
0
147456
0...

result: