挺妙的题。
考虑 dp,\(f_{i, j}\) 表示走到 \((i, j)\) 方案数,则 \(f_{i, j} = [j > 1] f_{i - 1, j - 1} + f_{i - 1, j} + [j < m] f_{i - 1, j + 1}\)。
发现这个东西很像什么 \(x^{-1} + x^0 + x^1\) 的 \(n\) 次方,但是我们还要规定 \(f_{i, 0} = f_{i, m + 1} = 0\),有点烦。
考虑把 dp 值沿着 \(f_{i, m + 1}\) 对称过去,并且 \(f_{i, j} + f_{i, 2m + 2 - j} = 0\)。这样的转移保证 \(f_{i, 0} = f_{i, m - 1} = 0\)。
于是我们做一个多项式 \(n\) 次幂即可。
code
// Problem: Ex - Simple Path Counting Problem
// Contest: AtCoder - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
// URL: https://atcoder.jp/contests/abc309/tasks/abc309_h
// Memory Limit: 1024 MB
// Time Limit: 10000 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 = 1000100;
const ll mod = 998244353, 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, A, B, a[maxn], b[maxn], r[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;
}
inline poly qpow(poly t, ll p) {
int n = (int)t.size();
poly res(n);
for (int i = 1; i <= A; ++i) {
res[a[i]] = (res[a[i]] + 1) % mod;
res[m * 2 + 2 - a[i]] = (res[m * 2 + 2 - a[i]] + mod - 1) % mod;
}
while (p) {
if (p & 1) {
res = res * t;
for (int i = m * 2 + 2; i < n; ++i) {
res[i % (m * 2 + 2)] = (res[i % (m * 2 + 2)] + res[i]) % mod;
res[i] = 0;
}
}
t = t * t;
for (int i = m * 2 + 2; i < n; ++i) {
t[i % (m * 2 + 2)] = (t[i % (m * 2 + 2)] + t[i]) % mod;
t[i] = 0;
}
p >>= 1;
}
return res;
}
void solve() {
scanf("%lld%lld%lld%lld", &n, &m, &A, &B);
for (int i = 1; i <= A; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= B; ++i) {
scanf("%lld", &b[i]);
}
int k = 0;
while ((1 << k) <= 4 * m + 4) {
++k;
}
for (int i = 1; i < (1 << k); ++i) {
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
poly t(1 << k);
t[m * 2 + 1] = t[0] = t[1] = 1;
poly res = qpow(t, n - 1);
ll ans = 0;
for (int i = 1; i <= B; ++i) {
ans = (ans + res[b[i]]) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner Counting AtCoder Contest Problembeginner counting atcoder contest beginner counting nameless atcoder 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 334