5

你有一个 N x N 棋盘，你想在上面放 N 个国王。每一行和每一列都应该包含一个国王，并且没有两个国王应该互相攻击（如果两个国王出现在共享一个角落的方格中，则两个国王会互相攻击）。

棋盘前K行的K已经被放置。以数组 pos[ ] 的形式给出这些国王的位置。pos[i] 是已经放置第 i 行国王的列。所有索引均为 0 索引。剩下的国王可以以多少种方式放置？

Input:
The first line contains the number of test cases T. T test cases follow. Each test case contains N and K on the first line, followed by a line having K integers, denoting the array pos[ ] as described above.

Output:
Output the number of ways to place kings in the remaining rows satisfying the above conditions. Output all numbers modulo 1000000007.

Constraints:
1 <= T <= 20
1 <= N <= 16
0 <= K <= N
0 <= pos_i < N
The kings specified in the input will be in different columns and not attack each other.

Sample Input:
5
4 1
2
3 0

5 2
1 3
4 4
1 3 0 2
6 1
2

Sample Output:
1
0
2
1
18

解释：对于第一个例子，第0行第2列已经有一个国王。第二行的国王必须属于第0列。第三行的国王必须属于第3列，最后一个国王必须属于到第 1 列。因此只有 1 个有效的展示位置。

对于第二个示例，没有有效的展示位置。

我应该如何解决这个问题

4

5 回答 5

14

这个问题本质上是要求我们计算1 2 ... N这样的排列i并且i+1不相邻1 <= i <= N-1。

此外，我们有一个前缀约束。我们应该只计算那些以 开头的排列pos_1 pos_2 ... pos_k。

如果不是前缀约束，您可以使用OEIS 中的公式在 O(N) 时间内找到答案。那就是如果N不是太大。答案中的位数随着 Θ(N log N) 的增长而增长，因此乘法和加法会产生额外的开销。或者你可以以某个数字为模来计算答案。这个问题是在埃及信息学奥林匹克竞赛（2009）中提出的。

使用前缀约束，我有一个 O(N 2 ) 动态规划解决方案。但是，由于 N 小到 16，因此使用多项式时间算法是多余的。存在一个在时间 O(2 N N 2 ) 上运行的更简单的动态规划解决方案。虽然这个算法可能比以前的解决方案需要更长的时间来编码，但它的思考速度要快得多。然而，在最坏的情况下，回溯解决方案需要 20 到 100 小时（在普通台式机/笔记本电脑上）才能运行。N =有2806878055610单独的解决方案可供访问16。除此之外，访问非解决方案的死胡同可能会付出沉重的代价。

O(2 N N 2 ) 解

该解决方案可以推广到在图中找到哈密顿路径的数量。

我们的状态是一对(S, i)；其中S是 的子集，{1,2...N}是i的元素S。设Sbe的基数M。

定义F(S,i)为将元素放置在1, 2, ..., M指定位置的方式数S；尊重永远不会一起出现的约束k；k+1并且元素M被放置在位置i。

基本情况是F(P,pos_k) = 1直接P = {pos_1, pos_2 ... pos_k}.计算所有F(S,i)时间O(2 N N 2 )。Si

最后的答案是F([N],1) + F([N],2) + ... + F([N],N)哪里[N] = {1,2...N}。

C++ 代码如下。位掩码用于表示{1,2...N}.

const int MAXN = 18;
long long DP[1 << MAXN][MAXN];

void solve() {
    int n, k;
    cin >> n >> k;
    
    int pmask = 0, p;
    for(int i = 0; i < k; i++){
        cin >> p;
        pmask |= (1<<p);
    }

    // base cases
    if(k > 0) {
        DP[pmask][p] = 1;
    }
    else {
        for(int i = 0; i < n; i++) 
            DP[1<<i][i] = 1;
    }

    long long ans = 0;
    for(int bitmask = pmask; bitmask < (1<<n); bitmask++) { 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if((bitmask & (1<<j)) or abs(i-j) == 1) 
                    continue;
                DP[bitmask | (1<<j)][j] += DP[bitmask][i]; 
            }
            if(bitmask == ((1<<n) - 1)) 
                ans += DP[bitmask][i];
        }
    }

    cout << ans << endl;
}

O(N 2 ) 解

如果您以前没有遇到过这个想法，那么很难想到这个解决方案。

首先，让我们解决没有前缀的问题。

这个想法是通过将元素 1、2 .. N 一个一个放置来“构建”所有有效的排列。

让我们从一个插图开始。假设我们正在构建一个排列，例如 1 2 .. 5。首先，我们放置 1。在放置 1 之后，我们还插入一个占位符元素以填充后面的数字。更准确地说，每个状态都是一类排列，其中占位符x被非空的元素序列替换。

我们的排列，在插入 1 之后，看起来像 3 种情况之一：

  • 1 x- 1 是第一个元素。占位符x将按某种顺序包含所有元素 2、3、4、5。
  • x 1- 1 是最后一个元素。
  • x 1 x- 1 既不是第一个元素也不是最后一个元素。

接下来，我们放置 2。它必须属于前 3 个类之一中的占位符之一。

  • 假设它属于1 x. 由于 2 不能与 1 相邻，所以在放置 2 之后，我们必须在它们之间插入另一个占位符。这导致了状态1 x 2。此外，当 2 不是最后一个元素时，我们需要考虑排列。我们还产生了一个 state 1 x 2 x。

  • 对于x 1，我们类似地创建状态2 x 1和x 2 x 1。

  • 对于x 1 x，我们有两个选择的占位符来放置 2。像前面的情况一样，我们创建状态2 x 1 x, x 2 x 1 x, x 1 x 2, x 1 x 2 x。但是请注意，例如，x 2 x 1 x最后一个占位符与其他两个不同 - 因为 3 可以出现在其中而无需创建另一个屏障！我们通过为占位符使用不同的符号来记录这一点。那就是我们使用x 2 x 1 oando 1 x 2 x来代替。

假设接下来，我们将 3 插入x 2 x 1 o. 如果我们像以前一样将 3 放在一个x中，我们必须创建一个屏障占位符。但是，我们确实可以选择在与屏障占位符相反的方向上创建或省略占位符。如果我们将 3 放在o占位符中，我们可以选择在两个方向上创建或省略占位符。

此外，我们还必须x将不使用的占位符“提升”为占位o符。这是因为，旧x占位符没有像对 3 那样为下一个元素 4 提供约束。

我们已经可以开始猜测发展模式了。在一般情况下，在插入 i 时：

  • 首先，我们必须选择在哪个占位符中放置 i。

  • 接下来，假设我们将 i 放在一个x占位符中。我们必须建立一个屏障占位符。我们可以选择是否在另一个方向构建占位符。

  • 如果我们使用o占位符，我们可以选择在两个方向上构建额外的占位符。也就是一共4个选择。

  • 我们必须将x未使用的占位符更新为占位o符。

将这个想法转化为有效算法的最后一个观察结果是，我们可以将具有相同数量的放置元素和相同数量的和占位符的排列类聚集在一起xo。这是因为，对于共享所有这三个参数的两个不同类，它们表示的排列数是相等的。

为了严格证明这一说法，观察我们列举的类是详尽且不重叠的就足够了。

前缀

稍加思考就会发现，在前缀问题中，我们只需要计算以某个元素开头的排列，（称为 b）；i和之间的一些约束i+1不再适用。

第二个修改很容易修复：如果 i-1 和 i 之间的约束不适用，那么在插入 i 之前，将所有x占位符更新为占位o符。

对于第一次修改，我们应该确保在开始之前总是有一个占位符，直到b被放置。在放置b时，我们很乐意将它放入开始的占位符中，并且不要在它之前添加任何占位符。

执行

让DP[i][no][nx]是构建放置第一个元素的类的方法的数量，并且分别i有no和nx类型的占位符。在任何状态下，占位符的数量都在 0 到 2 之间。因此状态空间为 O(N^2)。状态转换是恒定的时间，正如上面所描述的。oxx

没有前缀约束的问题的 O(N) 解

根据 OEIS，A n = (n+1)A n-1 - (n-2)A n-2 - (n-5)A n-3 + (n-3)A n-4；其中A n是i和i+1从不连续的排列数。

我们可以在 O(n) 中计算序列 A n 。（也就是说，假设我们计算 A n以一个相当小的数字为模。）

下面是公式的推导：

定义辅助序列：

  • B n =恰好违反了一个1 2 ... N邻接约束的排列数。N-1

  • C n =仅违反1 2 ... N涉及元素的邻接约束的排列数。也就是说，在这些排列中彼此相邻；并且满足所有其他邻接约束。NN-1N

我们现在寻找序列 A、B 和 C 的递归。

A n的复发

假设我们n从一个有效的 permutation中删除元素P，其中i和i+1从不相邻。Q的结果排列1 .. n-1必须恰好满足以下两种情况之一：

  • 中没有相邻的数字1 ... n-1是相邻的Q。即，是 A n-1Q中考虑的排列之一。

  • 恰好一对(i,i+1)连续出现在Q和i+1 =/= n-1中。即，Q是从 B n-1 - C n-1的排列。

在第一种情况下，n可以将元素插入精确的n - 2位置。其中两个位置被元素挡住了n - 1。n在第二种情况下， - 在连续元素之间的位置只有一种选择。

我们得到递归：A n = (n - 2)A n-1 + B n-1 - C n-1。

B n的复发

令 B n,kk为其中和k+1连续出现的排列数。我们可以将一个元素合并在一起，并考虑元素的排列k，保持相对顺序。k+1Qn-1

  • 如果k-1和（原始标签）都没有出现在合并元素k+2旁边，则对B n,k贡献排列- 它们对应于排列并在合并元素内。这样的数量是A n-1。(k,k+1)Q2k k+1k+1 kQ

  • 如果其中一个k-1或出现在元素k+2旁边，则有助于排列。这样的数量是B n-1,k-1 + B n-1,k。(k,k+1)Q1Q

  • 如果两者都k-1出现在元素k+2旁边，则有助于排列。这样的数量是B n-2,k-1。(k,k+1)Q1Q

我们有B n,k = 2A n-1 + B n-1,k-1 + B n-1,k + B n-2,k-1。（某些项在 时消失k = 1 and k = n-1）。

求和k，我们得到递归：B n = 2(n-1)A n-1 + 2B n-1 + B n-2。

C n的复发

好吧，C n只是B n,n-1。从前面的结果可知， C n = 2A n-1 + C n-1。

把它们放在一起

我们应该能够消除B和C以仅在A中重现。它留作练习。:-)

于 2012-07-08T15:55:02.337 回答
3

回溯可能太慢了。考虑到某一行 k 的解决方案数量仅取决于 k-1 行中国王的位置以及行 <k 的占用位置集，可以使用记忆化提高其速度。

于 2012-10-25T08:55:49.397 回答
2

你应该使用回溯来解决这个问题，像下面这样一个简单的函数可以解决你的问题，（处理输入文件和输出很容易，所以我跳过它）。

int CanPlaceKingInPosition(int pos[],int MaxIndex,int NewCol){
    for(int i=0;i<MaxIndex-1;i++)
        if(pos[i]==NewCol)
            return 0;
    //MaxIndex is the index of the above row of the new king, so we have to check attacking conditions

    if (abs(pos[MaxIndex-1]-NewCol)<=1)
       return 0;
    return 1;
}

int solver(int pos[], int N, int K){      
    int result=0;
    if (K>N) //termination condition
        return result;
    if (K==N-1) //last row
        return IsOnlyPossibleColAGoodOne(pos,N,N-1);
    for (int i=0;i<N;i++){ //for each column if we can place the king in it, move one step forward
        if (CanPlaceKingInPosion(pos,K,i)){
            pos[K]=i;  //add new king
            result+=solver(pos,N,K+1);  
        }
    }
    return result;
}

您可以像这样从 main() 调用此函数： //read N,K //fill pos

printf("%d",solver(pos,N,K+1) % 1000000007)

“IsOnlyPossibleColAGoodOne”函数返回 1，如果可以将国王放置在船上唯一的空闲列中（一个简单的 for 就可以了）。我没有测试过这个功能，所以你应该把它当作一个指导而不是一个实际的代码。（它可能工作得很好，但我没有测试过）

PS：是ACM/ICPC的问题吗？

于 2012-07-08T11:13:36.647 回答
0

您好使用下面的代码我可以生成有效国王位置的排列，如果内存不受限制，我们可以生成最多 16X16 的所有排列并将它们存储在给定测试用例的相应表中生成可以匹配已经生成的排列的相应不完整排列相应的 NXN 板，数一数那将是答案

int columns[]={1,2,3,4,5,6,7,8,9,10,11,12};

public void displayPermitationsBoth(int prev,StringBuilder sb,int n,int stage){
    if(stage==n){
        display(sb);
        return;
    }
    String localStr=sb.toString();
    int localStage=stage;
    for(int i=0;i<n;i++){
        if((sb.toString().contains("-"+Integer.toString(columns[i])+"-"))||(Math.abs(prev-columns[i])==1)){
            continue;
        }
        displayPermitationsBoth(columns[i],sb.append("-"+columns[i]+"-"),n,++stage);
        stage=localStage;
        sb.delete(0,sb.capacity());
        sb.append(localStr);
    }
}
于 2013-07-15T14:23:28.907 回答
0 
import java.util.*;

/**
*
* @author BENDIABDELLAH
**/
public class Solution {

boolean boards[][];
Set<Integer> occupied_CL = new HashSet<Integer>();

Solution(int n) {
    boards = new boolean[n][n];
}

Solution() {
}

void setBoard(boolean[][] boards) {
    this.boards = boards;
    for (int i = 0; i < boards.length; ++i) {
        for (int j = 0; j < boards.length; ++j) {
            if (boards[i][j]) {
                occupied_CL.add(j);
            }
        }
    }
}

int waysToPlace(int k) {
    if (k == boards.length - 1) {
        return 1;
    }
    int totalWays = 0;
    for (int pos = 0; pos < boards.length; ++pos) {
        int ways = 1;
        if (!isAttack(k + 1, pos)) {
            boards[k + 1][pos] = true;
            occupied_CL.add(pos);
            ways *= waysToPlace(k + 1);
            boards[k + 1][pos] = false;
            occupied_CL.remove(pos);
        } else {
            ways = 0;
        }
        totalWays += ways;
    }
    return totalWays;
}

boolean isAttack(int row, int col) {
    if (occupied_CL.contains(col)) {
        return true;
   }
    if ((col > 0 && row > 0 && boards[row - 1][col - 1]) || (col < boards.length - 1 && row > 0 && boards[row - 1][col + 1])) {
        return true;
    }
    return false;
}

void printArray() {
    for (int i = 0; i < boards.length; ++i) {
        for (int j = 0; j < boards.length; ++j) {
            System.out.print(boards[i][j] + " ");
        }
        System.out.println();
    }
}

public static void main(String args[]) {
    //Solution sol = new Solution(5);
    // System.out.println(sol.waysToPlace(-1));
    //sol.printArray();
    readInput();
}

static void readInput() {
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    for (int i = 0; i < t; ++i) {
        int n = scan.nextInt();
        //System.out.println(" n "+n );
        int k = scan.nextInt();
        // System.out.println(" k "+k );
        boolean boards[][] = new boolean[n][n];
        for (int row = 0; row < k; ++row) {
            int col = scan.nextInt();
            boards[row][col] = true;
        }
        Solution s = new Solution();
        s.setBoard(boards);
        int ways = s.waysToPlace(k - 1);
        System.out.println(ways);
        }
    }
}
于 2013-10-08T13:24:56.913 回答