P9743（2023 激励计划评分 9）
Spouter_27
·
·
题解
设 dp_{x,y,c,la,lb} 表示走到 x,y，花了 c 元，还剩 la 张 L 公司的票，lb 张 Z 公司的。
初始值 dp_{1,1,0,0,0}=1。
转移枚举在 x,y 买了多少票，设 c'=c-a_{i,j}\times ca-b_{i,j}\times cb：
dp_{x,y,c,la,lb}=\sum_{ca=0}^{la}\sum_{cb=0}^{lb} dp_{x-1,y,c',la-ca+1,lb-cb}+dp_{x,y-1,c',la-ca,lb-cb+1}
有一些边界情况需要判断。
这样做是 $O(n^7)$，实现的好可以获得 $65$ 分，不过还要优化。
注意到枚举其实大可不必，考虑一个类似二维前缀和的容斥：
$$dp_{x,y,c,la,lb}=dp_{x,y,c-a_{i,j},la-1,lb}+dp_{x,y,c-b_{i,j},la,lb-1}-dp_{x,y,c-a_{i,j}-b_{i,j},la-1,lb-1}$$
然后再加上 $dp_{x-1,y,c,la+1,lb}+dp_{x,y-1,c,la,lb+1}$ 就可以了。
但是空间开不下五维数组，不过可以把 $x$ 这一维用滚动数组优化。
取模不用取得很勤，最后算答案再取模就行。复杂度 $O(n^5)$，已经可以过了。
一个优化：如果现在买的票已经不可能贡献了，就不再转移了。具体看代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define deb(x) cerr<<"Line: "<<__LINE__<<", val= "<<x<<"; \n"
typedef long long ll;
#define pii pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
const ll N=50,K=95,mod=998244353;
inline ll read(){
ll a=0,x=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-') x=-x;
c=getchar();
}
while(isdigit(c)){
a=a*10+c-'0';
c=getchar();
}
return a*x;
}
ll n,m,k,cnt;
ll a[N][N],b[N][N];
ll dp[N][N];
ll f[2][N][K][N][N],ans[N][N];
ll flag=1;
signed main(){
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=read();
if(a[i][j]!=1) flag=0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
b[i][j]=read();
if(b[i][j]!=45) flag=0;
}
}
f[1][1][0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i!=1) f[i&1][j][0][0][0]=0;
for(int c=1;c<=k;c++){
for(int la=0;la+i<=n;la++){
for(int lb=0;lb+j<=m;lb++){//如果现在买的票已经不可能贡献了，就不再转移了。
ll res=mod;
if(la!=0&&c>=a[i][j]) res+=f[i&1][j][c-a[i][j]][la-1][lb];
if(lb!=0&&c>=b[i][j]) res+=f[i&1][j][c-b[i][j]][la][lb-1];
if(la!=0&&lb!=0&&c>=a[i][j]+b[i][j]) res-=f[i&1][j][c-a[i][j]-b[i][j]][la-1][lb-1];
if(i!=1) res+=f[(i-1)&1][j][c][la+1][lb];
if(j!=1) res+=f[i&1][j-1][c][la][lb+1];
f[i&1][j][c][la][lb]=res%mod;
if(c==k&&la==0&&lb==0) ans[i][j]=res%mod;
}
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%lld ",ans[i][j]);
}
putchar('\n');
}
return 0;
}
```