UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214537#2486. 小根堆a_sad_soul2031ms25608kbC++111.1kb2024-11-19 21:32:372024-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;
}

Details

小提示:点击横条可展开更详细的信息

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'