ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214537 | #2486. 小根堆 | a_sad_soul | 20 | 31ms | 25608kb | C++11 | 1.1kb | 2024-11-19 21:32:37 | 2024-11-19 23:03:07 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int MAXN = 1e6+10;
ll fac[MAXN],rev[MAXN];
ll siz[MAXN<<1];bool is[MAXN];
#define ls(p)(p<<1)
#define rs(p)(p<<1|1)
ll ksm(ll a,ll b){
ll re=1;
while(b){
if(b&1)re=re*a%mod;
a=a*a%mod;
b>>=1;
}
return re;
}
int n;
void Init(){
fac[0]=1;
for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod;
rev[n]=ksm(fac[n],mod-2);
for(int i=n-1;~i;--i)rev[i]=rev[i+1]*(i+1)%mod;
}
ll C(int n,int m){
// if(n<m||n<=0||m<0)return 0;
if(n<m)return 0;
return fac[n]*rev[m]%mod*rev[n-m]%mod;
}
void dfs(int u){
if(u>n)return ;
dfs(ls(u)),dfs(rs(u));
siz[u]=1+siz[ls(u)]+siz[rs(u)];
is[u]|=is[ls(u)]|is[rs(u)];
}
ll calc(int u){
if(u>n)return 1;
//if(is[u])return C(siz[u]-2,siz[ls(u)]+(is[ls(u)]?-1:0))*calc(ls(u))%mod*calc(rs(u));
return C(siz[u]-1,siz[ls(u)])*calc(ls(u))%mod*calc(rs(u))%mod;
}
int x,y;
int main(){
cin>>n>>x>>y;
is[x]=1;
Init();dfs(1);
//for(int i=1;i<=n;++i)cout<<is[i]<<" ";
cout<<calc(1)<<endl;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1208kb
input:
5 2 2
output:
8
result:
wrong answer 1st lines differ - expected: '6', found: '8'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 1208kb
input:
10 4 3
output:
3360
result:
wrong answer 1st lines differ - expected: '840', found: '3360'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 1208kb
input:
20 18 19
output:
818419393
result:
wrong answer 1st lines differ - expected: '134772704', found: '818419393'
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 1204kb
input:
30 20 16
output:
872967700
result:
wrong answer 1st lines differ - expected: '862828891', found: '872967700'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1208kb
input:
50 1 1
output:
454716180
result:
ok single line: '454716180'
Test #6:
score: 10
Accepted
time: 0ms
memory: 1228kb
input:
1000 1 1
output:
517631465
result:
ok single line: '517631465'
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 1228kb
input:
1000 765 669
output:
517631465
result:
wrong answer 1st lines differ - expected: '582857574', found: '517631465'
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 1228kb
input:
1000 149 293
output:
517631465
result:
wrong answer 1st lines differ - expected: '25668476', found: '517631465'
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 3644kb
input:
100000 42608 7968
output:
608747415
result:
wrong answer 1st lines differ - expected: '754109918', found: '608747415'
Test #10:
score: 0
Wrong Answer
time: 31ms
memory: 25608kb
input:
1000000 921152 658527
output:
773860226
result:
wrong answer 1st lines differ - expected: '563335284', found: '773860226'