暴力dp是显然的,f[s1][s2]
假设a,b是第i维中p,q两个向量分别对应的数。
那么分类讨论一下
不妨设
a<c<b
\[f[i][s1][s2]= \sum f[i-1][s1-(c-a)][s2-(b-c)]
\]
\[=\sum f[i-1][s1+a-c][s2-b+c]
\]
可以发现就是跟反对角线平行的方向,那么弄一个前缀维护即可
其它情况类似。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
using namespace std;
typedef long long ll;
const int N=105;
const int S=1005;
const ll mo=998244353;
ll g[S][S],f[S][S],h[S][S],z[S][S];
int x[N],y[N],n,d,a,b;
void add(ll &x,ll y){
x=(x+y)%mo;
}
void calc(){
fo(i,1,d) fo(j,1,d) {
g[i][j]=(g[i-1][j-1]+f[i][j])%mo;
}
fd(i,d,1) fo(j,1,d) {
h[i][j]=(h[i+1][j-1]+f[i][j])%mo;
}
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%d %d",&n,&d);
fo(i,1,n) scanf("%d",&x[i]);
fo(i,1,n) scanf("%d",&y[i]);
d++;
f[1][1]=1;
calc();
int l,r,a,b;
fo(i,1,n) {
fo(s1,1,d) fo(s2,1,d){
a=x[i]; b=y[i];
l=max(1+a-s1,1+b-s2);
r=min(a,b)-1;
if (l<=r) add(z[s1][s2], g[s1-a+r][s2-b+r]-g[s1-a+l-1][s2-b+l-1]);
l=max(a,b)+1;
r=min(s1+a-1,s2+b-1);
if (l<=r) add(z[s1][s2], g[s1+a-l][s2+b-l]-g[s1+a-r-1][s2+b-r-1]);
if (a<=b) {
l=max(b-s2+1, a);
r=min(s1+a-1, b);
if (l<=r) add(z[s1][s2], h[s1+a-r][s2-b+r]-h[s1+a-l+1][s2-b+l-1]);
}
else{
l=max(a-s1+1, b);
r=min(s2+b-1, a);
if (l<=r) add(z[s1][s2], h[s1-a+l][s2+b-l]-h[s1-a+r+1][s2+b-r-1]);
}
}
fo(s1,1,d) fo(s2,1,d) {
f[s1][s2]=z[s1][s2];
z[s1][s2]=0;
}
calc();
}
ll ans=0;
fo(i,1,d) {
fo(j,1,d) {
add(ans, f[i][j]);
// printf("%lld ",f[i][j]);
}
// printf("\n");
}
ans=(ans%mo+mo)%mo;
printf("%lld",ans);
return 0;
}