Hi everyone Hope you're doing great!

Yesterday, in the Div1+Div2 contest held on July 20, 2025, the E 2126E - G-C-D, Unlucky! 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. 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.