题解 | 旅行者的大逃脱 | 出题人我* | 说不清楚时间

艹！！！！！！！！！！！！

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL mod =998244353;

const int N = 505;

bool vis[N][N];
int f[2][N][N];
int row[2][N][N],col[2][N][N];

int n, m, q, K;

vector<pair<int,int>> vec[101];

void solve() {
    for(int i = 1; i <= 100;i++) vec[i].clear();
    memset(vis,0,sizeof vis);
    memset(f,0,sizeof f);
    memset(row,0,sizeof row);
    memset(col,0,sizeof col);
    cin >> n >> m >> q >> K;
    K++;
    for(int i = 1; i <= q; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        vec[t].push_back({x, y});
    }
    f[1][1][1] = 1;
    int ans = 0;
    LL sum = 0;
    for(int k = 1; k <= K; k++) {
        for(auto [x, y]: vec[k]) {
            vis[x][y] = true;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                f[(k&1)][i][j] += (row[(k&1)^1][i][j-1] + col[(k&1)^1][i-1][j]) % mod;
                row[(k&1)][i][j] = (row[(k&1)][i][j-1] + f[(k&1)][i][j]) % mod;
                col[(k&1)][i][j] = (col[(k&1)][i-1][j] + f[(k&1)][i][j]) % mod;
                if(vis[i][j]) f[k&1][i][j] = row[(k&1)][i][j] = col[k&1][i][j] = 0;
            }
        }
        if(f[(k&1)][n][m]) {
            if(!ans) ans = k - 1;
            sum = (sum + f[(k&1)][n][m]) % mod;
        }
        // memcpy(f[(k&1)^1], f[(k&1)], sizeof f[0]);
        // memcpy(row[(k&1)^1], row[(k&1)], sizeof row[0]);
        // memcpy(col[(k&1)^1], col[(k&1)], sizeof col[0]);
        // memset(f[(k&1)], 0, sizeof f[0]);
        // memset(row[(k&1)], 0, sizeof row[0]);
        // memset(col[(k&1)], 0, sizeof col[0]);
        memset(f[(k&1)^1], 0, sizeof f[0]);
        memset(row[(k&1)^1], 0, sizeof row[0]);
        memset(col[(k&1)^1], 0, sizeof col[0]);
    }
    if(ans) {
        cout << sum << " " << ans << "\n";
    } else {
        cout << -1 << "\n";
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    cin >> T;
    while(T--) solve();
}
// 64 位输出请用 printf("%lld")