[DP] UOJ137. [UER #3] 开学前的日历

不难的题。注意到操作等价与: 对于 \(i,j\ge 0,\ i+j\le k\)\((u+i,v+j)\) 加上 \({i+j\choose i}\)

考虑这个的组合意义,就相当于从 \((u,v)\) 开始往右下走,至少走 \(k\) 步,到每个格子的方案数。

所以就很简单了, \(f(i,j,k)\) 表示走到 \((i,j)\) ,剩 \(k\) 步才有贡献的方案数,\(DP\) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=305,P=998244353;
int n,m,Q,f[maxn][maxn][maxn*2],_x0;
inline int getrand(){
_x0=((LL)100000005*_x0+20150823)%998244353;
return _x0/100;
}
int main(){
scanf("%d%d%d%d",&n,&m,&Q,&_x0);
while(Q--){
int v=getrand()%n+1, u=getrand()%m+1, k=getrand()%(n+m-v-u+1);
f[v][u][k]++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
(f[i][j+1][0]+=f[i][j][0])%=P;
(f[i+1][j][0]+=f[i][j][0])%=P;
for(int k=1;k<=n+m-i-j;k++){
int _f=f[i][j][k];
(f[i][j+1][k-1]+=_f)%=P; (f[i+1][j][k-1]+=_f)%=P;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) printf("%d ",f[i][j][0]);
printf("\n");
}
return 0;
}