【UOJ 137】[UER #3] 开学前的日历

题目传送门：http://uoj.ac/problem/137
官方题解：http://vfleaking.blog.uoj.ac/blog/714

这个题，考试的时候想到了50分的算法，但没写出来QAQ
都搞到这个程度了：

还是没有想出来，可惜啊！

70分算法的关键：\(\left( \begin{array}{l}
x\\
y
\end{array} \right) = \left( \begin{array}{l}
x – 1\\
y
\end{array} \right) + \left( \begin{array}{l}
x – 1\\
y – 1
\end{array} \right)\)

100分的关键：
看一看上面那个图，组合数实际的意义是从(u,v)走到每个点的路径的个数
于是搞一搞dp即可

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300+9;
const int MOD = 998244353;

int f[N][N][N*2],n,m,q,X;

inline int read(){
	X = (100000005*(LL)X+20150823) % MOD;
	return X / 100;
}

int main(){
	cin>>m>>n>>q>>X;
	for (int i=1,u,v,k;i<=q;i++) {
		v = read()%m+1, u = read()%n+1, k = read()%(n+m-v-u+1);
		f[u][v][k]++;
	} 
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
		for (int k=0;k<=n+m;k++) (f[i][j][k] += (f[i-1][j][k+1] + f[i][j-1][k+1]) % MOD) %= MOD;
		(f[i][j][0] += (f[i-1][j][0] + f[i][j-1][0]) % MOD) %= MOD;
	}
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) 
		printf("%d%c",f[i][j][0],(i==n?'\n':' '));
	return 0;
}