P1350 车的放置 【洛谷算法习题】

P1350 车的放置

网页链接

P1350 车的放置

题目描述

有下面这样的一个网格棋盘，a , b , c , d a,b,c,da,b,c,d表示了对应边长度，也就是对应格子数：

当a = b = c = d = 2 a=b=c=d=2a=b=c=d=2时，对应下面这样一个棋盘：

要在这个棋盘上放k kk个相互不攻击的车，也就是这k kk个车没有两个车在同一行，也没有两个车在同一列，问有多少种方案。

输入格式

只有一行，为五个非负整数，分别代表a , b , c , d a,b,c,da,b,c,d和k kk。

输出格式

输出一行一个整数代表答案m o d \bmodmod10 5 + 3 10^5+3105+3后的结果。

输入输出样例 #1

输入 #1

2 2 2 2 2

输出 #1

38

说明/提示

数据规模与约定

• 存在部分数据，保证b = 0 b=0b=0；
• 存在部分数据，保证a , b , c , d ≤ 4 a,b,c,d\leq 4a,b,c,d≤4。
• 对于100 % 100\%100%的数据，保证0 ≤ a , b , c , d , k ≤ 10 3 0\leq a,b,c,d,k\leq 10^30≤a,b,c,d,k≤103，且至少有一种可行方案。

解题思路

本题是L形棋盘的不攻击车放置计数问题，采用动态规划按列递推求解，全程对 100003 取模。
棋盘可拆分为共a + c a+ca+c列：其中c cc列仅下半部分有d dd行格子，剩余a aa列上下连通，共有b + d b+db+d行格子。定义状态f[i][j]表示前i ii列放置j jj个互不攻击的车的方案数。
状态转移分两种情况：

1. 第i列不放车：方案数直接继承前i − 1 i-1i−1列放j jj个车的结果，即f[i][j] += f[i-1][j]。
2. 第i列放车：前i − 1 i-1i−1列已放置j − 1 j-1j−1个车，占用了j − 1 j-1j−1个不同行；当前列有v [ i ] v[i]v[i]个格子，因此可选行数为v [ i ] − ( j − 1 ) v[i] - (j-1)v[i]−(j−1)，贡献方案数f[i][j] += f[i-1][j-1] * (v[i] - j + 1)。
   初始状态f[0][0] = 1，所有列放置0个车的方案数均为1。最终f[a+c][k]即为答案。算法时间复杂度O ( ( a + c ) ⋅ k ) O((a+c) \cdot k)O((a+c)⋅k)，完全适配题目千级的数据范围。

总结

核心逻辑：将L形棋盘按列拆分，通过动态规划逐列递推，利用“车不同行不同列”的约束计算合法放置方案数。
关键操作：拆分棋盘得到每列的行数、定义二维DP状态、按“放/不放车”两种情况完成状态转移、全程取模。
效率保障：DP数组规模仅为2000×1000，线性递推无冗余运算，运行效率极高。

代码简要说明

1. 列高度数组v：前c列对应高度为d（仅下半部分有格子），后a列对应高度为b+d（上下两部分连通），匹配L形棋盘结构。
2. DP初始化：f[0][0] = 1，且所有前i列放置0个车的方案数初始化为1，作为递推边界。
3. 状态转移：双重循环遍历所有列与车数，分别累加“不放车”和“放车”的方案数，每次运算后对100003取模。
4. 结果输出：最终输出f[a+c][m]，即为放置m个互不攻击的车的总方案数。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll SZ=2005;ll f[SZ][SZ],v[SZ];ll a,b,c,d,m,mo=100003;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&m);for(ll i=1;i<=c;i++)v[i]=d,f[i][0]=1;for(ll i=1;i<=a;i++)v[c+i]=d+b,f[c+i][0]=1;f[0][0]=1;for(ll j=1;j<=a+c;j++)for(ll i=1;i<=m;i++)f[j][i]=(f[j-1][i]+f[j-1][i-1]*(v[j]-i+1))%mo;printf("%lld",f[a+c][m]);return0;}