简单计数题（P1350车的放置 dp）

题目传送门

题目大意 ： 给定一个图，在图中放置棋子，每行每列仅能放置一个，求放置 \(k\) 个的方案数。

题目分析 ：
对于给定图，若对于每个点都从前到后进行放置，难免会出现重复，所以我们从最左端进行遍历，只在它及它以后的列上进行放置，那么我们令 \(dp_{i , j}\) 为在前 \(i\) 列放置 \(j\) 个的方案数，则可以实现转移。

很明显，我们不难发现可以分为在该该列放置或者不放置，我们假设当前目标状态为 \(dp_{i , j}\)，当前列有 \(x\) 个位置：

• [\(1\)] : 不在该列放置， 很明显 \(dp_{i,j} = dp_{i - 1， j}\)。
• [\(2\)] : 在该列放置 ， 因为我们是枚举列，所以列重复的情况就不用考虑了，那么对于每一行来说的话，因为前面已经放了 \(j - 1\) 个元素 ， 那么也就是用了 \(j - 1\) 行，现在可用的行还剩 \(x - j + 1\)，根据乘法原理，我们可知 \(dp_{i,j} += dp_{i - 1 , j - 1} * (x - j + 1)\)

可得转移方程为 ： \(dp_{i,j} = dp_{i - 1 , j} + dp_{i - 1 , j - 1} * (x - j + 1)\)

仔细观察一下图形，不难发现，若我们从列长的到列短的进行遍历，那么所用的行会不好处理，那么我们就将图形进行翻转 ：

这个问题就解决了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e5 + 3;
const int M = 2e3  +7;
int a , b , c , d , k;
int dp[M][M];
signed main () {
	cin >> a >> b >> c >> d >> k;
	for(int i = 0; i <= a + c; ++ i) dp[i][0] = 1;
	for(int i = 1; i  <= a + c; ++ i) {
		for(int j = 1; j <= k; ++ j) {
			if(i > c)
			dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * max(b + d - j + 1 , 0ll) % mod) % mod;
			else 
			dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * max(d - j + 1 , 0ll) % mod) % mod;
		}
	}
	cout<< dp[a + c][k];
	return 0;	
}

本题完结！