QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745571#9740. Aho-Corasick 自动机hhoppitree#AC ✓349ms8084kbC++174.0kb2024-11-14 10:37:512024-11-14 10:37:51

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 10:37:51]
  • 评测
  • 测评结果:AC
  • 用时:349ms
  • 内存:8084kb
  • [2024-11-14 10:37:51]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 105, LIM = 1e6, P = 998244353, G = 3, iG = (P + 1) / G;

int inv[LIM + 5];

int ksm(int x, int y = P - 2)
{
    if (x <= LIM && y == P - 2) {
        return inv[x];
    }
    int res = 1;
    while (y) {
        if (y & 1) {
            res = 1ll * res * x % P;
        }
        x = 1ll * x * x % P;
        y >>= 1;
    }
    return res;
}

string Init()
{
    inv[1] = 1;
    for (int i = 2; i <= LIM; ++i) {
        inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    }
    return "Success";
}

string status = Init();

typedef vector<int> poly;

void simpl(poly &x)
{
    while (!x.empty() && !x.back()) {
        x.pop_back();
    }
    return;
}

poly operator + (poly x, poly y)
{
    int sz = max(x.size(), y.size());
    poly z(sz);
    x.resize(sz), y.resize(sz);
    for (int i = 0; i < (int)z.size(); ++i) {
        ((z[i] = x[i] + y[i]) >= P) && (z[i] -= P);
    }
    return z;
}

poly operator - (poly x, poly y)
{
    int sz = max(x.size(), y.size());
    poly z(sz);
    x.resize(sz), y.resize(sz);
    for (int i = 0; i < (int)z.size(); ++i) {
        ((z[i] = x[i] - y[i]) < 0) && (z[i] += P);
    }
    return z;
}

poly diff(poly x)
{
    if (x.empty()) {
        return x;
    }
    int sz = x.size() - 1;
    poly y(sz);
    for (int i = 0; i < sz; ++i) {
        y[i] = 1ll * x[i + 1] * (i + 1) % P;
    }
    return y;
}

poly inte(poly x)
{
    if (x.empty()) {
        return x;
    }
    int sz = x.size() + 1;
    poly y(sz);
    for (int i = 1; i < sz; ++i) {
        y[i] = 1ll * x[i - 1] * ksm(i) % P;
    }
    return y;
}

poly NTT(poly f, int type = 0)
{
    int n = f.size();
    assert(n && !(n & (n - 1)));
    poly tr(n);
    for (int i = 1; i < n; ++i) {
        tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
        if (i < tr[i]) {
            swap(f[i], f[tr[i]]);
        }
    }
    for (int len = 2; len <= n; len <<= 1) {
        int p = len >> 1, buf = ksm((type ? iG : G), (P - 1) / len);
        for (int i = 0; i < n; i += len) {
            int now = 1;
            for (int j = i; j < i + p; ++j) {
                int tmp = 1ll * now * f[j + p] % P;
                ((f[j + p] = f[j] - tmp) < 0) && (f[j + p] += P);
                ((f[j] += tmp) >= P) && (f[j] -= P);
                now = 1ll * now * buf % P;
            }
        }
    }
    if (type) {
        int invN = ksm(n);
        for (auto &v : f) {
            v = 1ll * v * invN % P;
        }
    }
    return f;
}

poly operator * (poly x, poly y)
{
    if (x.empty() || y.empty()) {
        return {};
    }
    simpl(x), simpl(y);
    int len = x.size() + y.size() - 1, tLen = 1;
    while (tLen < len) {
        tLen <<= 1;
    }
    x.resize(tLen), y.resize(tLen);
    x = NTT(x), y = NTT(y);
    for (int i = 0; i < tLen; ++i) {
        x[i] = 1ll * x[i] * y[i] % P;
    }
    x = NTT(x, 1);
    simpl(x);
    return x;
}

int f[N][N], C[N][N];

signed main() {
    int n, m, d; scanf("%d%d%d", &n, &m, &d);
    for (int i = C[0][0] = 1; i <= m; ++i) {
        for (int j = C[i][0] = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
        }
    }
    f[0][1] = 1;
    for (int i = 1; i <= d; ++i) {
        vector<int> f1(n + 1), f2(n + 1), tf1 = {1}, tf2 = {1};
        for (int k = 0; k < i; ++k) {
            for (int l = 1; l <= n; ++l) {
                f1[l] = (f1[l] + f[k][l]) % P;
                if (k != i - 1) f2[l] = (f2[l] + f[k][l]) % P;
            }
        }
        for (int j = 1; j <= m; ++j) {
            tf1 = tf1 * f1, tf1.resize(n + 1);
            tf2 = tf2 * f2, tf2.resize(n + 1);
            for (int k = 0; k <= n; ++k) {
                f[i][k + 1] = (f[i][k + 1] + 1ll * (tf1[k] - tf2[k] + P) * C[m][j]) % P;
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= d; ++i) {
        res = (res + f[i][n]) % P;
    }
    printf("%d\n", res);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 7668kb

input:

3 2 2

output:

5

result:

ok answer is '5'

Test #2:

score: 0
Accepted
time: 6ms
memory: 7912kb

input:

4 2 2

output:

6

result:

ok answer is '6'

Test #3:

score: 0
Accepted
time: 6ms
memory: 7704kb

input:

1 1 1

output:

1

result:

ok answer is '1'

Test #4:

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

input:

30 30 30

output:

286511539

result:

ok answer is '286511539'

Test #5:

score: 0
Accepted
time: 7ms
memory: 7712kb

input:

13 13 13

output:

818093168

result:

ok answer is '818093168'

Test #6:

score: 0
Accepted
time: 11ms
memory: 7696kb

input:

30 25 25

output:

730504816

result:

ok answer is '730504816'

Test #7:

score: 0
Accepted
time: 13ms
memory: 7692kb

input:

29 29 29

output:

892409454

result:

ok answer is '892409454'

Test #8:

score: 0
Accepted
time: 7ms
memory: 7724kb

input:

15 30 28

output:

505511076

result:

ok answer is '505511076'

Test #9:

score: 0
Accepted
time: 8ms
memory: 7736kb

input:

20 10 30

output:

250115604

result:

ok answer is '250115604'

Test #10:

score: 0
Accepted
time: 9ms
memory: 7816kb

input:

20 30 30

output:

623437187

result:

ok answer is '623437187'

Test #11:

score: 0
Accepted
time: 349ms
memory: 7772kb

input:

100 100 100

output:

933606371

result:

ok answer is '933606371'

Test #12:

score: 0
Accepted
time: 311ms
memory: 8084kb

input:

100 95 95

output:

368609759

result:

ok answer is '368609759'

Test #13:

score: 0
Accepted
time: 342ms
memory: 8044kb

input:

95 100 100

output:

691641619

result:

ok answer is '691641619'

Test #14:

score: 0
Accepted
time: 330ms
memory: 8016kb

input:

95 97 98

output:

517539873

result:

ok answer is '517539873'

Test #15:

score: 0
Accepted
time: 53ms
memory: 7964kb

input:

94 67 23

output:

601572539

result:

ok answer is '601572539'

Extra Test:

score: 0
Extra Test Passed