QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#48712#3537. The only winneraurelion_solAC ✓15ms4172kbC++141.4kb2022-09-15 12:09:212022-09-15 12:09:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-15 12:09:23]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:4172kb
  • [2022-09-15 12:09:21]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a),_=(b);i<=_;++i)
#define per(i,a,b) for(int i=(a),_=(b);i>=_;--i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define size(x) int(x.size())
using namespace std;

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ul;
typedef __int128 LL;
typedef __uint128_t UL;
typedef double db;
typedef vector<int> VI;

const int mod=1e9+7;
int inc(int x,int y){return x+=y-mod,x+=x>>31&mod;}
int dec(int x,int y){return x-=y,x+=x>>31&mod;}
int mul(int x,int y){return ul(x)*y%mod;}
int inc2(int &x,int y){return x+=y-mod,x+=x>>31&mod;}
int dec2(int &x,int y){return x-=y,x+=x>>31&mod;}
int mul2(int &x,int y){return x=ul(x)*y%mod;}
int qpow(int x,int y){int z=1;for(;y;y>>=1,x=mul(x,x))if(y&1)z=mul(x,z);return z;}

const int N=1e5+10;
int n,ff[N];

/*
bool vis[N];

int ans;

void dfs(int x,int mx,int cnt){
	if(vis[x])return dfs(x+1,mx,cnt);
	if(x==n+1){
		ans+=cnt==1;
		return;
	}
	rep(i,x+1,n)if(!vis[i]){
		vis[i]=1;
		dfs(x+1,max(mx,x+i),mx==x+i?cnt+1:(mx>x+i?cnt:1));
		vis[i]=0;
	}
}
*/

int main(){
	scanf("%d",&n);
	ff[0]=1;
	rep(i,1,n)ff[i]=mul(ff[i-1],2*i-1);
	n*=2;
	int x=0;
	rep(i,n+1,2*n-1){
		inc2(x,mul(mul((2*n+1-i)/2,qpow(i-1-n,n-(i+1)/2)),ff[(n>>1)-(n-(i+1)/2+1)]));
	}
	printf("%d\n",mul(x,qpow(ff[n>>1],mod-2)));
	exit(0);
}

详细

Test #1:

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

input:

2

output:

666666672

result:

ok 1 number(s): "666666672"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

5

output:

647619053

result:

ok 1 number(s): "647619053"

Test #4:

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

input:

3

output:

600000005

result:

ok 1 number(s): "600000005"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

7

output:

365567769

result:

ok 1 number(s): "365567769"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3828kb

input:

10

output:

458729432

result:

ok 1 number(s): "458729432"

Test #7:

score: 0
Accepted
time: 2ms
memory: 3684kb

input:

42

output:

643505700

result:

ok 1 number(s): "643505700"

Test #8:

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

input:

228

output:

125716107

result:

ok 1 number(s): "125716107"

Test #9:

score: 0
Accepted
time: 2ms
memory: 3796kb

input:

1225

output:

497563335

result:

ok 1 number(s): "497563335"

Test #10:

score: 0
Accepted
time: 3ms
memory: 3768kb

input:

8888

output:

372234803

result:

ok 1 number(s): "372234803"

Test #11:

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

input:

10500

output:

553242929

result:

ok 1 number(s): "553242929"

Test #12:

score: 0
Accepted
time: 5ms
memory: 3816kb

input:

16384

output:

235400649

result:

ok 1 number(s): "235400649"

Test #13:

score: 0
Accepted
time: 5ms
memory: 3880kb

input:

30000

output:

348712971

result:

ok 1 number(s): "348712971"

Test #14:

score: 0
Accepted
time: 10ms
memory: 4036kb

input:

65535

output:

304508463

result:

ok 1 number(s): "304508463"

Test #15:

score: 0
Accepted
time: 14ms
memory: 4060kb

input:

89898

output:

178782007

result:

ok 1 number(s): "178782007"

Test #16:

score: 0
Accepted
time: 15ms
memory: 4128kb

input:

100000

output:

600566479

result:

ok 1 number(s): "600566479"

Test #17:

score: 0
Accepted
time: 15ms
memory: 4172kb

input:

99999

output:

933686708

result:

ok 1 number(s): "933686708"

Test #18:

score: 0
Accepted
time: 11ms
memory: 4052kb

input:

99998

output:

113943006

result:

ok 1 number(s): "113943006"

Test #19:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

4

output:

228571431

result:

ok 1 number(s): "228571431"

Test #20:

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

input:

16

output:

646577665

result:

ok 1 number(s): "646577665"

Test #21:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

1024

output:

489408992

result:

ok 1 number(s): "489408992"

Test #22:

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

input:

2048

output:

390257222

result:

ok 1 number(s): "390257222"