ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214549 | #2486. 小根堆 | N | 80 | 23ms | 1348kb | C++11 | 4.0kb | 2024-11-19 22:39:50 | 2024-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