UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214549#2486. 小根堆N8023ms1348kbC++114.0kb2024-11-19 22:39:502024-11-19 23:04:40

answer

//
//  na 2486.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/19.
//

#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long int ll;
const int maxn = 1e6 + 5, mod = 998244353, maxdep = 20;
int n, x, y, ans, dp[maxn], siz[maxn], dep[maxn] = {-1};
inline int qpow(int base, int exp){
    int res = 1;
    while(exp){
        if(exp & 1)
            res = ll(res) * base % mod;
        base = ll(base) * base % mod;
        exp >>= 1;
    }
    return res;
}
void init_tree(int idx){
    siz[idx] = 1;
    dep[idx] = dep[idx >> 1] + 1;
    if((idx << 1) <= n){
        init_tree(idx << 1);
        siz[idx] += siz[idx << 1];
    }
    if((idx << 1 | 1) <= n){
        init_tree(idx << 1 | 1);
        siz[idx] += siz[idx << 1 | 1];
    }
}
inline int inv(int x){
    return qpow(x, mod - 2);
}
int fac[maxn], ifac[maxn];
inline void init_fac(){
    fac[0] = 1;
    for(int i = 1; i <= n; ++i)
        fac[i] = fac[i - 1] * ll(i) % mod;
    ifac[n] = inv(fac[n]);
    for(int i = n - 1; i >= 0; --i)
        ifac[i] = ifac[i + 1] * ll(i + 1) % mod;
}
inline int C(int a, int b){
    if(b > a)
        return 0;
//    cerr << "C(" << a << ", " << b << ") = " << (fac[a] * ll(ifac[b]) % mod) * ifac[a - b] % mod << endl;
    return (fac[a] * ll(ifac[b]) % mod) * ifac[a - b] % mod;
}
namespace smalln_sol{
int v[maxn];
void dfs(int dep){
    if(dep == n){
        ++ans;
        return;
    }
    for(int i = 1; i <= n; ++i)
        if(v[i]){
            if((i << 1) <= n && !v[i << 1] && ((i << 1) != x || dep + 1 == y)){
                v[i << 1] = dep + 1;
                dfs(dep + 1);
                v[i << 1] = 0;
            }
            if((i << 1 | 1) <= n && !v[i << 1 | 1] && ((i << 1 | 1) != x || dep + 1 == y)){
                v[i << 1 | 1] = dep + 1;
                dfs(dep + 1);
                v[i << 1 | 1] = 0;
            }
        }
}
inline void smalln(){
    if(x == 1 && y != 1)
        return;
    v[1] = 1;
    dfs(1);
}
}
namespace spec_sol{
void dfs(int idx){
    if((idx << 1) <= n){
        dfs(idx << 1);
        if((idx << 1 | 1) <= n){
            dfs(idx << 1 | 1);
            dp[idx] = ((ll(C(siz[idx << 1] + siz[idx << 1 | 1], siz[idx << 1])) * dp[idx << 1]) % mod) * dp[idx << 1 | 1] % mod;
        }else{
            dp[idx] = dp[idx << 1];
        }
    }else{
        dp[idx] = 1;
    }
}
inline void spec(){
    dfs(1);
    ans = dp[1];
}
}
namespace final_sol{
using namespace spec_sol;
int dp2[maxdep][maxn], seq[maxn], seql;
inline void add(int &x, int y){
    if((x += y) >= mod)
        x -= mod;
}
inline int mul(int a, int b, int c, int d){
    return ((ll(a) * b) % mod) * ((ll(c) * d) % mod) % mod;
}
inline void sol(){
    spec();
    for(int i = x; i; i >>= 1)
        seq[seql++] = i;
//    cerr << x;
//    for(int i = 1; i < seql; ++i)
//        cerr << " -> " << seq[i];
//    cerr << endl;
    dp2[0][1] = dp[x];
    int x, y, z;
    for(int ipos = 1; ipos < seql; ++ipos){
        x = seq[ipos];
        z = seq[ipos - 1];
        y = (z == (x << 1))? (x << 1 | 1): (x << 1);
//        cerr << "x = " << x << ", y = " << y << ", z = " << z << endl;
        if(y > n){
            for(int i = 2; i <= siz[x]; ++i)
                dp2[ipos][i] = dp2[ipos - 1][i - 1];
        }else{
            for(int i = 2; i <= siz[x]; ++i)
                for(int j = min(i - 1, siz[z]); j; --j)
                    add(dp2[ipos][i], mul(dp2[ipos - 1][j], C(i - 2, j - 1), C(siz[x] - i, siz[z] - j), dp[y]));
        }
//        cerr << "dp: ";
//        for(int i = 1; i <= siz[x]; ++i)
//            cerr << dp2[ipos][i] << " ";
//        cerr << endl;
    }
    ans = dp2[seql - 1][::y];
}
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> x >> y;
    init_fac();
    init_tree(1);
//    if(n <= -10){
//        smalln_sol::smalln();
//    }else if(x == y && y == 1){
//        spec_sol::spec();
//    }else{
        final_sol::sol();
//    }
    cout << ans << endl;
    return 0;
}

详细

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

Test #1:

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

input:

5 2 2

output:

6

result:

ok single line: '6'

Test #2:

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

input:

10 4 3

output:

840

result:

ok single line: '840'

Test #3:

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

input:

20 18 19

output:

134772704

result:

ok single line: '134772704'

Test #4:

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

input:

30 20 16

output:

862828891

result:

ok single line: '862828891'

Test #5:

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

input:

50 1 1

output:

454716180

result:

ok single line: '454716180'

Test #6:

score: 10
Accepted
time: 1ms
memory: 1300kb

input:

1000 1 1

output:

517631465

result:

ok single line: '517631465'

Test #7:

score: 10
Accepted
time: 9ms
memory: 1348kb

input:

1000 765 669

output:

582857574

result:

ok single line: '582857574'

Test #8:

score: 10
Accepted
time: 13ms
memory: 1336kb

input:

1000 149 293

output:

25668476

result:

ok single line: '25668476'

Test #9:

score: 0
Time Limit Exceeded

input:

100000 42608 7968

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

1000000 921152 658527

output:


result: