NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#214548	#2486. 小根堆	KXG	60	307ms	24036kb	C++11	1.8kb	2024-11-19 22:35:43	2024-11-19 23:04:37

answer

#include <cstdio>
#include <vector>
using namespace std;
const long long mod = 998244353;
long long n, x, y;
long long inv[1000010], invfac[1000010], fac[1000010];
long long f[1000010], g[1010][1010], siz[1000010];
long long C(long long n, long long m) {
    return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
bool dfs(int u) {
    if (u > n) {
        siz[u] = 0;
        f[u] = 1;
        return false;
    }
    bool lson = dfs(2 * u);
    bool rson = dfs(2 * u + 1);
    siz[u] = 1 + siz[2 * u] + siz[2 * u + 1];
    if (lson || rson) {
        if (lson) {
            for (int j = 2; j <= siz[u]; j++) {
                for (int k = 1; k <= siz[2 * u]; k++) {
                    g[u][j] = (g[u][j] + f[2 * u + 1] * g[2 * u][k] % mod * C(j - 2, k - 1) % mod * C(siz[u] - j, siz[2 * u] - k) % mod) % mod;
                }
            }
        } else {
            for (int j = 2; j <= siz[u]; j++) {
                for (int k = 1; k <= siz[2 * u + 1]; k++) {
                    g[u][j] = (g[u][j] + f[2 * u] * g[2 * u + 1][k] % mod * C(j - 2, k - 1) % mod * C(siz[u] - j, siz[2 * u + 1] - k) % mod) % mod;
                }
            }
        }
        return true;
    } else if (u == x) {
        g[u][1] = C(siz[u] - 1, siz[2 * u]) * f[2 * u] % mod * f[2 * u + 1] % mod;
        return true;
    } else {
        f[u] = C(siz[u] - 1, siz[2 * u]) * f[2 * u] % mod * f[2 * u + 1] % mod;
        return false;
    }
}
int main() {
    inv[1] = 1;
    invfac[0] = invfac[1] = 1;
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= 1000000; i++) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        invfac[i] = invfac[i - 1] * inv[i] % mod;
        fac[i] = fac[i - 1] * i % mod;
    }
    scanf("%lld%lld%lld", &n, &x, &y);
    dfs(1);
    printf("%lld\n", g[1][y]);
    return 0;
}

源文件, 语言: C++11

详细

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

Test #1:

score: 10

Accepted

time: 44ms

memory: 23960kb

input:

5 2 2

output:

result:

ok single line: '6'

Test #2:

score: 10

Accepted

time: 34ms

memory: 23972kb

input:

10 4 3

output:

result:

ok single line: '840'

Test #3:

score: 10

Accepted

time: 31ms

memory: 23980kb

input:

20 18 19

output:

134772704

result:

ok single line: '134772704'

Test #4:

score: 10

Accepted

time: 34ms

memory: 23976kb

input:

30 20 16

output:

862828891

result:

ok single line: '862828891'

Test #5:

score: 10

Accepted

time: 40ms

memory: 23964kb

input:

50 1 1

output:

454716180

result:

ok single line: '454716180'

Test #6:

score: 10

Accepted

time: 33ms

memory: 23988kb

input:

1000 1 1

output:

517631465

result:

ok single line: '517631465'

Test #7:

score: 0

Wrong Answer

time: 43ms

memory: 24036kb

input:

1000 765 669

output:

80878816

result:

wrong answer 1st lines differ - expected: '582857574', found: '80878816'

Test #8:

score: 0

Wrong Answer

time: 48ms

memory: 24028kb

input:

1000 149 293

output:

272412140

result:

wrong answer 1st lines differ - expected: '25668476', found: '272412140'

Test #9:

score: 0

Runtime Error

input:

100000 42608 7968

output:

result:

Test #10:

score: 0

Runtime Error

input:

1000000 921152 658527