P1350 车的放置网页链接P1350 车的放置题目描述有下面这样的一个网格棋盘a , b , c , d a,b,c,da,b,c,d表示了对应边长度也就是对应格子数当a b c d 2 abcd2abcd2时对应下面这样一个棋盘要在这个棋盘上放k kk个相互不攻击的车也就是这k kk个车没有两个车在同一行也没有两个车在同一列问有多少种方案。输入格式只有一行为五个非负整数分别代表a , b , c , d a,b,c,da,b,c,d和k kk。输出格式输出一行一个整数代表答案m o d \bmodmod10 5 3 10^531053后的结果。输入输出样例 #1输入 #12 2 2 2 2输出 #138说明/提示数据规模与约定存在部分数据保证b 0 b0b0存在部分数据保证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 acac列其中c cc列仅下半部分有d dd行格子剩余a aa列上下连通共有b d bdbd行格子。定义状态f[i][j]表示前i ii列放置j jj个互不攻击的车的方案数。状态转移分两种情况第i列不放车方案数直接继承前i − 1 i-1i−1列放j jj个车的结果即f[i][j] f[i-1][j]。第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[ac][k]即为答案。算法时间复杂度O ( ( a c ) ⋅ k ) O((ac) \cdot k)O((ac)⋅k)完全适配题目千级的数据范围。总结核心逻辑将L形棋盘按列拆分通过动态规划逐列递推利用“车不同行不同列”的约束计算合法放置方案数。关键操作拆分棋盘得到每列的行数、定义二维DP状态、按“放/不放车”两种情况完成状态转移、全程取模。效率保障DP数组规模仅为2000×1000线性递推无冗余运算运行效率极高。代码简要说明列高度数组v前c列对应高度为d仅下半部分有格子后a列对应高度为bd上下两部分连通匹配L形棋盘结构。DP初始化f[0][0] 1且所有前i列放置0个车的方案数初始化为1作为递推边界。状态转移双重循环遍历所有列与车数分别累加“不放车”和“放车”的方案数每次运算后对100003取模。结果输出最终输出f[ac][m]即为放置m个互不攻击的车的总方案数。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll SZ2005;ll f[SZ][SZ],v[SZ];ll a,b,c,d,m,mo100003;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 i1;ic;i)v[i]d,f[i][0]1;for(ll i1;ia;i)v[ci]db,f[ci][0]1;f[0][0]1;for(ll j1;jac;j)for(ll i1;im;i)f[j][i](f[j-1][i]f[j-1][i-1]*(v[j]-i1))%mo;printf(%lld,f[ac][m]);return0;}