QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#745571 | #9740. Aho-Corasick 自动机 | hhoppitree# | AC ✓ | 349ms | 8084kb | C++17 | 4.0kb | 2024-11-14 10:37:51 | 2024-11-14 10:37:51 |
Judging History
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