A题补题注意事项！数据有坑！！！

卡了我一下午

老实了

附上ac代码

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>

#include <math.h>

#include <iomanip>

#include <cctype>

#include <string>

#include <cstdio>

#include <vector>

#include <ctime>

#include <queue>

#include <map>

#include <stack>

#include <iostream>

#include <list>

#include <algorithm>

#include <bitset>

#include <unordered_map>

using namespace std;

#define int long long

typedef unsigned long long ull;

int a[5005], b[5005];

int dp[5005][5005];

int maxx[5005][5005];

int val[5006], preval[5006], qval[5006];

const int mod = 998244353;

int qpow(int x, int n, int mod)

{

if (n == 0) return 1;

if (n == 1) return x;

int ans = qpow(x, n / 2, mod);

ans = ans * ans % mod;

if (n % 2) ans = ans * x % mod;

return ans;

}

signed main() {

ios::sync_with_stdio(0);

cin.tie(0); cout.tie(0);

int n, st;

cin >> n >> st;

int r;

for (r = 1; r <= n; r++) cin >> a[r];

for (r = 1; r <= n; r++) cin >> b[r];

for (r = 1; r <= n; r++) maxx[r][r] = a[r];

dp[st][st] = 1;

int total_ans = 0;

for (int len = 2; len <= n; len++)

{

int K = n - len;

preval[0] = 1;

for (r = 1;r <= K;r++)

{

val[r] = (b[r] + b[r + len]) % mod;

if (val[r] == 0) val[r] = 1; // 【加入这一行，免疫除零污染】

preval[r] = (preval[r - 1] * val[r]) % mod;

}

int allinv = qpow(preval[K], mod - 2, mod);

for (r = K;r >= 1;r--)

{

qval[r] = preval[r - 1] * allinv % mod;

allinv = allinv * val[r] % mod;

}

for (int s = 1; s + len - 1 <= n; s++)

{

int e = s + len - 1;

maxx[s][e] = max(maxx[s + 1][e], maxx[s][s]);

if (s > st || e < st) continue;

int gl1 = 0;

if (dp[s + 1][e])

{

if (e != n) gl1 = (dp[s + 1][e] * b[s] % mod * qval[s] % mod);

else gl1 = dp[s + 1][e];

}

int gl2 = 0;

if (dp[s][e - 1])

{

if (s != 1) gl2 = (dp[s][e - 1] * b[e] % mod * qval[s - 1] % mod);

else gl2 = dp[s][e - 1];

}

dp[s][e] = (gl1 + gl2) % mod;

if (maxx[s][e] > maxx[s + 1][e]) total_ans = (total_ans + gl1) % mod;

if (maxx[s][e] > maxx[s][e - 1]) total_ans = (total_ans + gl2) % mod;

}

}

cout << (1 + total_ans) % mod << '\n';

return 0;

}