Hi everyone ↵
Hope you're doing great! ↵
↵
Yesterday, in the **Div1+Div2** contest held on **July 20, 2025**, the **E** [problem:2126E] problem had an interesting path to optimize the constraints and ordering of computations. ↵
With tighter constraints and better prefix handling, I managed to push the solution down to **~62ms** and **O(n * k)**, even for `(n, k)` limits.↵
[submission:330006746]↵
↵
## Source Code↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long ll;↵
↵
const ll mod = 998244353;↵
const int N = 504;↵
int A[N], B[N], n, k;↵
↵
ll dp[N], pre[N], pree[N], dp1[N];↵
↵
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);↵
↵
int main() {↵
fast_io↵
int T; cin >> T;↵
while (T--) {↵
cin >> n >> k;↵
for (int i = 1; i <= n; i++) cin >> A[i];↵
for (int i = 1; i <= n; i++) cin >> B[i];↵
↵
dp1[0] = 1;↵
for (int i = 1; i <= n - 1; i++) {↵
pre[0] = dp[0];↵
pree[0] = dp[0] * (k + 1) % mod;↵
for (int j = 1; j <= k; j++) {↵
pre[j] = (pre[j - 1] + dp[j]) % mod;↵
pree[j] = (pree[j - 1] + dp[j] * (k + 1 - j)) % mod;↵
}↵
↵
if (A[i + 1] == -1 && B[i] == -1) {↵
for (int j = 0; j <= k; j++) {↵
if (j == 0) dp[j] = pree[k] - pre[k] + mod;↵
else dp[j] = (pree[k] - pree[j - 1] + mod + (pre[k] - pre[j - 1] + mod) * (j - 1) + mod) % mod;↵
if (j != 0) {↵
dp[j] = (dp[j] + pre[k] * (k - j) + dp1[i - 1] * (k - j)) % mod;↵
}↵
}↵
dp1[i] = dp1[i - 1] * (k * k - k * (k - 1) / 2) % mod;↵
continue;↵
}↵
↵
int l = (A[i + 1] == -1 ? 1 : A[i + 1]) - (B[i] == -1 ? k : B[i]);↵
int r = (A[i + 1] == -1 ? k : A[i + 1]) - (B[i] == -1 ? 1 : B[i]);↵
↵
for (int j = 0; j <= k; j++) {↵
int l2 = max(j + l, j) - 1, r2 = min(k, j + r);↵
if (l2 < r2) dp[j] = ((r2 < 0 ? 0 : pre[r2]) - (l2 < 0 ? 0 : pre[l2]) + mod) % mod;↵
else dp[j] = 0;↵
if (-r <= j && j <= -l && j != 0) dp[j] = (dp[j] + dp1[i - 1] + pre[k]) % mod;↵
}↵
↵
dp1[i] = dp1[i - 1] * max(0, r + 1 - max(l, 0)) % mod;↵
}↵
↵
ll ans = dp1[n - 1];↵
for (int i = 0; i <= k; i++) ans = (ans + dp[i]) % mod;↵
ans = ans * (A[1] == -1 ? k : 1) % mod * (B[n] == -1 ? k : 1) % mod;↵
↵
cout << ans << '\n';↵
↵
for (int i = 0; i <= k; i++) dp[i] = 0;↵
}↵
}↵
~~~~~↵
↵
↵
If there’s enough interest, I’ll share the full theoretical explanation for this code as well.
Hope you're doing great! ↵
↵
Yesterday, in the **Div1+Div2** contest held on **July 20, 2025**, the **E** [problem:2126E] problem had an interesting path to optimize the constraints and ordering of computations. ↵
With tighter constraints and better prefix handling, I managed to push the solution down to **~62ms** and **O(n * k)**, even for `(n, k)` limits.↵
[submission:330006746]↵
↵
## Source Code↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long ll;↵
↵
const ll mod = 998244353;↵
const int N = 504;↵
int A[N], B[N], n, k;↵
↵
ll dp[N], pre[N], pree[N], dp1[N];↵
↵
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);↵
↵
int main() {↵
fast_io↵
int T; cin >> T;↵
while (T--) {↵
cin >> n >> k;↵
for (int i = 1; i <= n; i++) cin >> A[i];↵
for (int i = 1; i <= n; i++) cin >> B[i];↵
↵
dp1[0] = 1;↵
for (int i = 1; i <= n - 1; i++) {↵
pre[0] = dp[0];↵
pree[0] = dp[0] * (k + 1) % mod;↵
for (int j = 1; j <= k; j++) {↵
pre[j] = (pre[j - 1] + dp[j]) % mod;↵
pree[j] = (pree[j - 1] + dp[j] * (k + 1 - j)) % mod;↵
}↵
↵
if (A[i + 1] == -1 && B[i] == -1) {↵
for (int j = 0; j <= k; j++) {↵
if (j == 0) dp[j] = pree[k] - pre[k] + mod;↵
else dp[j] = (pree[k] - pree[j - 1] + mod + (pre[k] - pre[j - 1] + mod) * (j - 1) + mod) % mod;↵
if (j != 0) {↵
dp[j] = (dp[j] + pre[k] * (k - j) + dp1[i - 1] * (k - j)) % mod;↵
}↵
}↵
dp1[i] = dp1[i - 1] * (k * k - k * (k - 1) / 2) % mod;↵
continue;↵
}↵
↵
int l = (A[i + 1] == -1 ? 1 : A[i + 1]) - (B[i] == -1 ? k : B[i]);↵
int r = (A[i + 1] == -1 ? k : A[i + 1]) - (B[i] == -1 ? 1 : B[i]);↵
↵
for (int j = 0; j <= k; j++) {↵
int l2 = max(j + l, j) - 1, r2 = min(k, j + r);↵
if (l2 < r2) dp[j] = ((r2 < 0 ? 0 : pre[r2]) - (l2 < 0 ? 0 : pre[l2]) + mod) % mod;↵
else dp[j] = 0;↵
if (-r <= j && j <= -l && j != 0) dp[j] = (dp[j] + dp1[i - 1] + pre[k]) % mod;↵
}↵
↵
dp1[i] = dp1[i - 1] * max(0, r + 1 - max(l, 0)) % mod;↵
}↵
↵
ll ans = dp1[n - 1];↵
for (int i = 0; i <= k; i++) ans = (ans + dp[i]) % mod;↵
ans = ans * (A[1] == -1 ? k : 1) % mod * (B[n] == -1 ? k : 1) % mod;↵
↵
cout << ans << '\n';↵
↵
for (int i = 0; i <= k; i++) dp[i] = 0;↵
}↵
}↵
~~~~~↵
↵
↵
If there’s enough interest, I’ll share the full theoretical explanation for this code as well.
