题面
题解
首先，我们定义DP的状态，(dp[i][j][s][t])表示所有满足踢完了(i)场比赛，西班牙人一共得了(s)分而其对手一共得了(t)分，且西班牙人当前积了(j)分的可能比赛结果数。
初始值为(dp[0][0][0][0]=1)，即最开始一场比赛都没比的情况。
而最终的答案应该是(Sigma dp[n][dog][x][y])，之中(doggeq m)，这表示了(n)轮比赛后,西班牙人和其对手的分数满足分别为(x,y)时，可使得这赛季西班牙人总分大于等于(m)分的所有方案总和。
接下来考虑转移方程，(dp[i][j][s][t])可以从哪个状态得到呢？为了解决这个问题，我们要枚举第(i)轮比赛的结果。假设第(i)轮比赛的比赛结果是西班牙人得了(dog)分而它的对手得了(cat)分，那么有以下三种情况。
1、若(dog=cat)，则说明第(i)轮比赛平局了，平局积分为1分，因此此时应令(dp[i][j][s][t]+=dp[i-1][j-1][s-dog][t-cat])。
2、若(dog<cat)，则说明第(i)轮比赛输球了，输球积分为0分，因此此时应令(dp[i][j][s][t]+=dp[i-1][j][s-dog][t-cat])。
3、若(dog>cat)，则说明第(i)轮比赛赢球了，赢球积分为3分，因此此时应令(dp[i][j][s][t]+=dp[i-1][j-3][s-dog][t-cat])。
至此，有了状态定义、状态转移方程、初始值，那我们就可以编写程序了，但当你写完之后点击提交按钮后，你会发现...
超时了！
接着，回看你刚刚所写的程序，你会发现，你的程序整体当中循环的大体框架应该是类似这样的：
for i in [1,n]
for j in [1,3*n]
for s in [1,x]
for t in [1,y]
for dog in [1,s]
for cat in [1,t]
经过粗略计算，这样的程序复杂度是(O(nmxyxy)=O(nmx^2y^2))的，并且在本题数据范围下(nmx^2y^2=2.7075*10^{10})，确实是会超时很多的。
所以我们回过头来，看看有没有什么优化的方法，我们再看一下状态转移：
1、若(dog=cat)，则说明第(i)轮比赛平局了，平局积分为1分，因此此时应令(dp[i][j][s][t]+=dp[i-1][j-1][s-dog][t-cat])。
2、若(dog<cat)，则说明第(i)轮比赛输球了，输球积分为0分，因此此时应令(dp[i][j][s][t]+=dp[i-1][j][s-dog][t-cat])。
3、若(dog>cat)，则说明第(i)轮比赛赢球了，赢球积分为3分，因此此时应令(dp[i][j][s][t]+=dp[i-1][j-3][s-dog][t-cat])。
我们发现，上面的状态转移也可以写成(dp[i][j][s][t]=(Sigma dp[i-1][j][u1][v1])+(Sigma dp[i-1][j-1][u2][v2])+(Sigma dp[i-1][j-3][u3][v3]))，之中((u1,v1))满足(s-u1<t-v1)，该不等式左侧的含义是第(i)轮西班牙人进球数，右侧是对手进球数，小于号是因为此时才满足西班牙人输了第(i)场球的限制。类似的，(u2,v2)要满足(s-u2=t-v2)；(u3,v3)要满足(s-u3>t-v3)。
那么我们举个例子来考虑一下，假设现在我想得到(dp[i][j][3][4])的值，现在如果画出(dp[i-1][j])这张表格的话（因为(dp[i-1][j])固定了前两维而后两维是待定的，所以可以说(dp[i-1][j])是一张表，表格的大小应该是((x+1)*(y+1))的），我们来看下该表格中合法的(u1,v1)有什么特点：
我用红色在(dp[i-1][j])标出了所有合法的(u1,v1)，它们可以转移到(dp[i][j][3][4])。发现是一个类似下三角的形状。
接下来画一下可以通过一场平局转移到(dp[i][j][3][4])的状态，即画出(dp[i-1][j-1])表。
可以看到，是一条斜线的形状。
接下来画可以通过一场赢球转移到(dp[i][j][3][4])的状态，即画出(dp[i][j-3])表。
可以看到，这是一个类似上三角的形状。
因此，刚刚的(dp[i][j][s][t]=(Sigma dp[i-1][j][u1][v1])+(Sigma dp[i-1][j-1][u2][v2])+(Sigma dp[i-1][j-3][u3][v3]))可以重新写成(dp[i][j][s][t]=dp[i-1][j]表中的一个下三角的求和+dp[i-1][j-1]表中的一条斜线的求和+dp[i-1][j-3]表中的一个上三角的求和)。
按照这个新的式子，我们的程序伪代码可以重写为：
for i in [1,n]
for j in [1,3*n]
for s in [1,x]
for t in [1,y]
☆ dp[i][j][s][t]=dp[i-1][j]表中的一个下三角的求和+dp[i-1][j-1]表中的一条斜线的求和+dp[i-1][j-3]表中的一个上三角的求和
那么如果可以让☆处代码在(O(1))的时间内执行，那么整个程序的复杂度就是(O(nmxy))的了，可以通过此题。
为了达到(O(1))，我们可以预处理出每张表中三个图形的求和：
令(line[i][j][u][v])表示表格(dp[i][j])中，从((u,v))处发出的向左上的一条线上的求和，那么有(line[i][j][u][v]=line[i][j][u-1][v-1]+dp[i][j][u][v])，这样可以(O(xy))的时间得到一张表的斜线求和。
令(up[i][j][u][v])表示表格(dp[i][j])中，以((u,v))处作为右下角的一个下三角形的求和，那么有(up[i][j][u][v]=up[i][j][u][v-1]+line[i][j][u][v])，这样可以(O(xy))的时间得到一张表的下三角求和。
令(down[i][j][u][v])表示表格(dp[i][j])中，以((u,v))处作为右下角的一个上三角形的求和，那么有(down[i][j][u][v]=down[i][j][u-1][v]+line[i][j][u][v])，这样可以(O(xy))的时间得到一张表的上三角求和。
因为一共有(nm)张表需要处理，所以上述预处理过程总时间也是(O(nmxy))，因此，程序执行的总时间就是(O( 预处理的nmxy + 计算DP值的nmxy)=O(nmxy))，可以在规定时间内通过此题。
至此，就可以写出不超时的代码了，为了节省空间，还可以压缩到上述所有数组的第一维，下面的示例代码就压缩掉了([i])所在那一维。
那么下面来看示例代码。
完整代码
注：下面rep是在第三行定义的宏
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
int n,m,x,y;
const int mod=998244353;
// dp([i])[j][s][t]
const int mx=38*3;
int dp[120][52][52];
int line[120][52][52],up[120][52][52],down[120][52][52];
// line: 一道左上方向的斜线上的求和 ;up: 一个上三角形状部分的求和 ;down: 一个下三角形状部分的求和
int main(){
cin>>n>>m>>x>>y;
dp[0][0][0]=1;
rep(i,1,n){
// 存储i-1 轮后的数据
rep(j,0,mx){
rep(u,0,x) line[j][u][0]=down[j][u][0]=dp[j][u][0];
rep(v,0,y) line[j][0][v]=up[j][0][v]=dp[j][0][v];
rep(u,1,x){
rep(v,1,y){
line[j][u][v]=(line[j][u-1][v-1]+dp[j][u][v])%mod;
}
}
rep(u,0,x){
rep(v,0,y){
if(v) down[j][u][v]=(down[j][u][v-1]+line[j][u][v])%mod;
if(u) up[j][u][v]=(up[j][u-1][v]+line[j][u][v])%mod;
}
}
}
rep(j,0,mx){
rep(u,0,x){
rep(v,0,y){
dp[j][u][v]=0;
if(j>=0){
// += dp[i-1][j][s][t] where (u-s)<(v-t)
if(v) dp[j][u][v]+=down[j][u][v-1];
dp[j][u][v]%=mod;
}
if(j>=1){
// += dp[i-1][j-1][s][t] where (u-s)==(v-t)
dp[j][u][v]+=line[j-1][u][v];
dp[j][u][v]%=mod;
}
if(j>=3){
// += dp[i-1][j-3][s][t] where (u-s)>(v-t)
if(u) dp[j][u][v]+=up[j-3][u-1][v];
dp[j][u][v]%=mod;
}
}
}
}
}
int ans=0;
rep(j,m,mx){
ans+=dp[j][x][y];
ans%=mod;
}
printf("%d
",ans);
return 0;
}