考虑一个朴素 dp,\(f_{t, u}\) 表示 \(t\) 时刻走到 \(u\) 点的方案数。有转移:
\[f_{t, u} = \sum\limits_{(u, v) = E_i} \sum\limits_{k = 0}^{t - 1} f_{k, v} \times p_{i, t - k}
\]
直接做时间复杂度 \(O(mT^2)\),无法接受。
发现转移是加法卷积形式,又因为这个 dp 是在线的,考虑分治 NTT。设当前递归区间为 \([l, r]\),设 \(mid = \left\lfloor\frac{l + r}{2}\right\rfloor\),计算出 \(f_{l \sim mid, v}\) 后,卷上 \(p_{i, 0 \sim r - l}\) 可以转移至 \(f_{mid + 1 \sim r, u}\)。时间复杂度降至 \(O(mT \log^2 T)\),可以通过。
code
// Problem: H - Stroll
// Contest: AtCoder - AtCoder Beginner Contest 213
// URL: https://atcoder.jp/contests/abc213/tasks/abc213_h
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
const ll G = 3;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, K, a[15][maxn], r[maxn], f[maxn][15];
vector<pii> E[maxn];
typedef vector<ll> poly;
inline poly NTT(poly a, int op) {
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
if (i < r[i]) {
swap(a[i], a[r[i]]);
}
}
for (int k = 1; k < n; k <<= 1) {
ll wn = qpow(op == 1 ? G : qpow(G, mod - 2), (mod - 1) / (k << 1));
for (int i = 0; i < n; i += (k << 1)) {
ll w = 1;
for (int j = 0; j < k; ++j, w = w * wn % mod) {
ll x = a[i + j], y = w * a[i + j + k] % mod;
a[i + j] = (x + y) % mod;
a[i + j + k] = (x - y + mod) % mod;
}
}
}
if (op == -1) {
ll inv = qpow(n, mod - 2);
for (int i = 0; i < n; ++i) {
a[i] = a[i] * inv % mod;
}
}
return a;
}
inline poly operator * (poly a, poly b) {
a = NTT(a, 1);
b = NTT(b, 1);
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
a[i] = a[i] * b[i] % mod;
}
a = NTT(a, -1);
return a;
}
void cdq(int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1, n = mid - l, m = r - l, k = 0;
cdq(l, mid);
while ((1 << k) <= n + m) {
++k;
}
for (int i = 1; i < (1 << k); ++i) {
::r[i] = (::r[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
for (int u = 1; u <= ::n; ++u) {
for (pii p : E[u]) {
int v = p.fst, id = p.scd;
poly A(1 << k), B(1 << k);
for (int i = 0; i <= n; ++i) {
A[i] = f[l + i][v];
}
for (int i = 0; i <= m; ++i) {
B[i] = a[id][i];
}
poly C = A * B;
for (int i = mid + 1; i <= r; ++i) {
f[i][u] = (f[i][u] + C[i - l]) % mod;
}
}
}
cdq(mid + 1, r);
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &K);
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
E[u].pb(v, i);
E[v].pb(u, i);
for (int j = 1; j <= K; ++j) {
scanf("%lld", &a[i][j]);
}
}
f[0][1] = 1;
cdq(0, K);
printf("%lld\n", f[K][1]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Stroll 213beginner atcoder contest stroll contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315 beginner atcoder contest 334