QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#48712 | #3537. The only winner | aurelion_sol | AC ✓ | 15ms | 4172kb | C++14 | 1.4kb | 2022-09-15 12:09:21 | 2022-09-15 12:09:23 |
Judging History
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"