rt

提交记录

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll N = 110, D = 1010, mod = 998244353;
ll n, d;
ll p[N], q[N];
ll f[N][2 * D][D], sum[2 * D][D], sum2[2 * D][D];
int main() {
	cin >> n >> d;
	for(int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	for(int i = 1; i <= n; i++) {
		cin >> q[i];
	}
	f[0][0][0] = 1;
	for(int i = 1; i <= n; i++) {
		memset(sum, 0, sizeof(sum));
		memset(sum2, 0, sizeof(sum2));
		for(int j = 0; j <= d; j++) {
			for(int k = 0; k <= d; k++) {
				if(j > 0) {
					sum[j][k] += sum[j - 1][k + 1];
					sum[j][k] %= mod;
				}
				sum[j][k] += f[i - 1][j][k];
				sum[j][k] %= mod;
				if(j - 1 >= 0 && k - 1 >= 0) {
					sum2[j][k] += sum2[j - 1][k - 1];
					sum2[j][k] %= mod;
				}
				sum2[j][k] += f[i - 1][j][k];
				sum2[j][k] %= mod;
			}
		}
		ll s = abs(p[i] - q[i]);
		for(int j = 0; j <= d; j++) {
			for(int k = 0; k <= d; k++) {
				f[i][j][k] = 0;
				if(k - s >= 0) {
					f[i][j][k] += (sum[j][k - s] - sum[j - s - 1][k + 1] + mod) % mod;
				}
				else {
					f[i][j][k] += (sum[j - s + k][0] - sum[j - s - 1][k + 1] + mod) % mod;
				}
				f[i][j][k] %= mod;
				if(j - 1 >= 0 && k - s - 1 >= 0) {
					f[i][j][k] += (sum2[j - 1][k - s - 1] + mod) % mod;
					f[i][j][k] %= mod;
				}
				if(j - s - 1 >= 0 && k - 1 >= 0) {
					f[i][j][k] += (sum2[j - s - 1][k - 1] + mod) % mod;
					f[i][j][k] %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for(ll j = 0; j <= d; j++) {
		for(ll k = 0; k <= d; k++) {
			if(abs(j - k) <= d) {
				ans += f[n][j][k];
				ans %= mod;
			}
		}
	}
	cout << ans;
	return 0;
}