Problem Statement
In an $N$-dimensional space, the Manhattan distance $d(x,y)$ between two points $x=(x_1, x_2, \dots, x_N)$ and $y = (y_1, y_2, \dots, y_N)$ is defined by:
\(\displaystyle d(x,y)=\sum_{i=1}^n \vert x_i - y_i \vert.\)
A point $x=(x_1, x_2, \dots, x_N)$ is said to be a lattice point if the components $x_1, x_2, \dots, x_N$ are all integers.
You are given lattice points $p=(p_1, p_2, \dots, p_N)$ and $q = (q_1, q_2, \dots, q_N)$ in an $N$-dimensional space.
How many lattice points $r$ satisfy $d(p,r) \leq D$ and $d(q,r) \leq D$? Find the count modulo $998244353$.
Constraints
- $1 \leq N \leq 100$
- $0 \leq D \leq 1000$
- $-1000 \leq p_i, q_i \leq 1000$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $D$ $p_1$ $p_2$ $\dots$ $p_N$ $q_1$ $q_2$ $\dots$ $q_N$
Output
Print the answer.
Sample Input 1
1 5 0 3
Sample Output 1
8
When $N=1$, we consider points in a one-dimensional space, that is, on a number line.
$8$ lattice points satisfy the conditions: $-2,-1,0,1,2,3,4,5$.
Sample Input 2
3 10 2 6 5 2 1 2
Sample Output 2
632
Sample Input 3
10 100 3 1 4 1 5 9 2 6 5 3 2 7 1 8 2 8 1 8 2 8
Sample Output 3
145428186
#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1005,P=998244353;
int n,d,p[N],q[N],dp[2][M][M],ans;
int main()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
scanf("%d",p+i);
for(int i=1;i<=n;i++)
scanf("%d",q+i);
dp[0][0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=d;j++)
{
for(int k=0;k<=d;k++)
{
dp[i&1][j][k]=0;
for(int l=max(p[i]-j,q[i]-k);l<=min(p[i],q[i]);l++)
{
dp[i&1][j][k]+=dp[i&1^1][j-p[i]+l][k-q[i]+l];
dp[i&1][j][k]%=P;
}
for(int l=max(q[i]-k,p[i]+1);l<=min(q[i]-1,p[i]+j);l++)
{
dp[i&1][j][k]+=dp[i&1^1][j-l+p[i]][k-q[i]+l];
dp[i&1][j][k]%=P;
}
for(int l=max(q[i]+1,p[i]-j);l<=min(p[i]-1,q[i]+k);l++)
{
dp[i&1][j][k]+=dp[i&1^1][j-p[i]+l][k-l+q[i]];
dp[i&1][j][k]%=P;
}
for(int l=max(p[i],q[i])+(p[i]==q[i]);l<=min(p[i]+j,q[i]+k);l++)
{
dp[i&1][j][k]+=dp[i&1^1][j-l+p[i]][k-l+q[i]];
dp[i&1][j][k]%=P;
}
if(i==n)
ans=(ans+dp[i&1][j][k])%P;
}
}
}
printf("%d",ans);
}
发现瓶颈在转移，那么就考虑能不能 \(O(1)\) 转移。
在这四种情况中，有两种情况满足后两个下标之和不变，另两种后两个下标之差不变。考虑在这一点的基础上，使用前缀和。
定义 \(f_{i,j}\) 表示在上一位中，后两个下标差为 \(i\)，且第二位下标不超过 \(j\) 的所有dp 值之和，\(s_{i,j}\) 表示在上一位中，后两个下标和为 \(i\)，且第二位下标不超过 \(j\) 的所有 \(dp\) 值之和。那么我们在更新 dp 值时分情况用 \(f\) 和 \(s\) 去更新就好了。
代码有些繁琐
#include<bits/stdc++.h>
using namespace std;
const int N=105,M=4005,P=998244353;
int n,d,p[N],q[N],dp[M>>2][M>>2],ans,s[M][M],f[M<<1][M],l,r;
int mo(int x)
{
return (x%P+P)%P;
}
int main()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
scanf("%d",p+i);
for(int i=1;i<=n;i++)
scanf("%d",q+i);
dp[0][0]=1;
for(int j=0;j<=d;j++)
{
for(int k=0;k<=d;k++)
{
f[j-k+M][j+1]=f[j-k+M][j]+dp[j][k];
f[j-k+M][j+1]%=P;
s[j+k][j+1]=s[j+k][j]+dp[j][k];
s[j+k][j+1]%=P;
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=d;j++)
{
for(int k=0;k<=d;k++)
{
dp[j][k]=0;
l=max(p[i]-j,q[i]-k),r=min(p[i],q[i]);
if(l<=r)
dp[j][k]=mo(f[j-k-p[i]+q[i]+M][j-p[i]+r+1]-f[j-k-p[i]+q[i]+M][j-p[i]+l]);
dp[j][k]=mo(dp[j][k]);
l=max(q[i]-k,p[i]+1),r=min(q[i]-1,p[i]+j);
if(l<=r)
dp[j][k]+=mo(s[j+k+p[i]-q[i]][j-l+p[i]+1]-s[j+k+p[i]-q[i]][j-r+p[i]]);
dp[j][k]=mo(dp[j][k]);
l=max(q[i]+1,p[i]-j),r=min(p[i]-1,q[i]+k);
if(l<=r)
dp[j][k]+=mo(s[j+k+q[i]-p[i]][j-p[i]+r+1]-s[j+k+q[i]-p[i]][j-p[i]+l]);
dp[j][k]=mo(dp[j][k]);
l=max(p[i],q[i])+(p[i]==q[i]),r=min(p[i]+j,q[i]+k);
if(l<=r)
dp[j][k]+=mo(f[j-k+p[i]-q[i]+M][j-l+p[i]+1]-f[j-k+p[i]-q[i]+M][j-r+p[i]]);
dp[j][k]=mo(dp[j][k]);
if(i==n)
ans=(ans+dp[j][k])%P;
}
}
for(int j=0;j<=d;j++)
{
for(int k=0;k<=d;k++)
{
f[j-k+M][j+1]=f[j-k+M][j]+dp[j][k];
f[j-k+M][j+1]%=P;
s[j+k][j+1]=s[j+k][j]+dp[j][k];
s[j+k][j+1]%=P;
}
}
}
printf("%d",ans);
}