P1240 诸侯安置网页链接1240 诸侯安置题目描述很久以前有一个强大的帝国它的国土成正方形状如图所示。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功国王准备给他们每人一块封地正方形中的一格。但是这些诸侯又非常好战当两个诸侯位于同一行或同一列时他们就会开战。如下图为n 3 n3n3时的国土阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击第三幅则不可以。国王自然不愿意看到他的诸侯们互相开战致使国家动荡不安。 因此他希望通过合理的安排诸侯所处的位置使他们两两之间都不能攻击。现在给出正方形的边长n nn以及需要封地的诸侯数量k kk要求你求出所有可能的安置方案数。满足n ≤ 100 n\le100n≤100k ≤ 2 n 2 − 2 n 1 k\le2n^2-2n1k≤2n2−2n1由于方案数可能很多你只需要输出方案数除以504 504504的余数即可。输入格式仅一行两个整数n nn和k kk中间用一空格隔开。输出格式一个整数表示方案数除以504 504504的余数。输入输出样例 #1输入 #12 2输出 #14说明/提示注意镜面和旋转的情况属于不同的方案。解题思路解题思路本题是棋盘上互不攻击的放置方案计数问题本质上是“车的放置”问题的变种。国王需要在正方形的国土中为k kk个诸侯分配格子使得任意两个诸侯不在同一行或同一列。由于国土形状特殊菱形直接处理不便需要通过平移变换将其转化为便于动态规划的规则图形。1. 问题等价转化国土是一个旋转了 45° 的正方形可以看作一个菱形。将其按列划分每一列的长度不同。由于“任意两个诸侯不在同一行或同一列”的约束只与行、列的相对关系有关而将整行或整列进行平移并不会改变诸侯之间是否同行或同列因此可以将菱形的每一列向左对齐得到一个列数从左到右不严格递增的阶梯形图形。题目中说明镜面和旋转属于不同方案因此平移操作不会影响方案计数。变换后国土共有2 n − 1 2n-12n−1列。第i ii列的长度记为L[i]对于i 1 … n − 1 i 1 \dots n-1i1…n−1有L[2i-1] L[2i] 2i-1对于最后一列L[2n-1] 2n-1。例如n 3 n3n3时列长度依次为1 , 1 , 3 , 3 , 5 1, 1, 3, 3, 51,1,3,3,5。2. 动态规划设计设dp[i][j]表示在前i ii列中放置j jj个诸侯且互不同行同列的方案数。由于每一列的长度不超过该列的行数且列与列之间行是共享的因此放置时需要考虑当前列有哪些行已被占用。但注意到图形经过平移后每一列都是从第一行开始的连续行例如第i ii列有L[i]行恰好是第1 11行到第L[i]行。因此如果前i − 1 i-1i−1列已经放置了j − 1 j-1j−1个诸侯它们占用了j − 1 j-1j−1个不同的行。第i ii列有L[i]行其中被占用的行数也是j − 1 j-1j−1因为这些行都在前i − 1 i-1i−1列的范围内所以第i ii列可用的行数为L[i] - (j-1)。状态转移不放置第i ii列放0 00个方案数继承自dp[i-1][j]。放置一个第i ii列放1 11个方案数为dp[i-1][j-1] * (L[i] - (j-1))。因为前i − 1 i-1i−1列放了j − 1 j-1j−1个占用了j − 1 j-1j−1行第i ii列还有L[i] - (j-1)个位置可选。转移方程d p [ i ] [ j ] d p [ i − 1 ] [ j ] d p [ i − 1 ] [ j − 1 ] × ( L [ i ] − ( j − 1 ) ) dp[i][j] dp[i-1][j] dp[i-1][j-1] \times (L[i] - (j-1))dp[i][j]dp[i−1][j]dp[i−1][j−1]×(L[i]−(j−1))所有运算对504 504504取模。边界条件dp[i][0] 1放置 0 个的方案数为 1。若k 2 n − 1 k 2n-1k2n−1即超过最大可放置数直接输出0 00。最终答案dp[2n-1][k]。3. 算法实现读入n , k n, kn,k。若k 2 n − 1 k 2n-1k2n−1输出0 00并结束。预处理列长度数组L对于i 1 i 1i1到n − 1 n-1n−1L[2*i-1] L[2*i] 2*i - 1。L[2*n-1] 2*n - 1。初始化 DP 数组dp[2*n][210]dp[i][0] 1。双重循环外层i ii从1 11到2 n − 1 2n-12n−1遍历每一列。内层j jj从1 11到min ( i , k ) \min(i, k)min(i,k)遍历放置数量。计算dp[i][j] (dp[i-1][j] dp[i-1][j-1] * (L[i] - j 1)) % 504。输出dp[2*n-1][k]。4. 复杂度分析时间复杂度状态数O ( n × k ) O(n \times k)O(n×k)每个状态O ( 1 ) O(1)O(1)转移总时间复杂度O ( n 2 ) O(n^2)O(n2)。n ≤ 100 n \le 100n≤100运算量约10 4 10^4104非常快。空间复杂度二维 DP 数组dp[210][210]空间O ( n 2 ) O(n^2)O(n2)完全可接受。总结通过将菱形国土平移为阶梯形使得每一列都是从第一行开始的连续行从而消除了列与列之间行位置的复杂对应关系。在此基础上动态规划只需记录“前i ii列放j jj个”的方案数转移时考虑当前列放或不放并乘以当前列中未被占用的行数。该方法巧妙且高效完美解决了本题。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll P504;ll dp[210][210],L[210];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;cinnk;if(k2*n-1){cout0;return0;}for(ll i1;in;i)L[2*i-1]L[2*i]2*i-1;L[2*n-1]2*n-1;for(ll i0;i2*n-1;i)dp[i][0]1;for(ll i1;i2*n-1;i){for(ll j1;jL[i];j){dp[i][j]dp[i-1][j]dp[i-1][j-1]*(L[i]-j1);dp[i][j]%P;}}coutdp[2*n-1][k];return0;}