在国际象棋棋盘上放置国王的方法数量

Question

你有一个N x N棋盘,你希望在它上面放置N个国王.每一行和每列应该只包含一个国王,并且没有两个国王应该相互攻击(如果两个国王存在于共享角落的方格中,则两个国王互相攻击).

已经放置了板的前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列,最后一个国王必须是第3行因此,只有1个有效的展示位置.

对于第二个示例,没有有效的展示位置.

我应该如何处理这个问题

Answer 1

问题基本上是要求我们计算这样的排列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 ²)动态编程解决方案.但是,由于N小到16,因此使用多项式时间算法是过度的.存在一种在时间O(2 ^N N ²)内运行的更容易的动态编程解决方案.尽管这种算法的编码可能比以前的解决方案花费的时间更长,但它的思考速度要快得多.然而,在最坏的情况下,回溯解决方案需要花费20到100个小时(在普通台式机/笔记本电脑上)才能运行.2806878055610N = 有单独的解决方案16.除此之外,访问非解决方案的死胡同可能会付出沉重的代价.

O(2 ^N N ²)溶液

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

我们的州将是一对(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)用于所有S和i在时间O(2 ^Ñ Ñ ²).

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

C++代码如下.Bitmasks用于表示子集{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 ²)溶液

如果您之前没有遇到过这个想法,那么很难想到这个解决方案.

首先,让我们解决没有前缀的问题.

我们的想法是通过逐个放置元素1,2 ......来"构建"所有有效的排列.

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

插入1后,我们的排列看起来像3个案例中的一个:

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

接下来,我们放置2.它必须属于前三个类之一的占位符之一.

• 假设它属于唯一的占位符1 x.由于2不能与1相邻,因此在放置2后我们必须在它们之间插入另一个占位符.这导致了状态1 x 2.另外,当2不是最后一个元素时,我们需要考虑排列.我们也产生了一个州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 o和o 1 x 2 x陈述.

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

此外,我们还必须"推广" x不适合o占位符的占位符.这是因为旧的x占位符不为下一个元素4提供约束,就像它们为3做的那样.

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

• 首先,我们必须选择放置i的占位符.

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

• 如果我们使用o占位符,我们可以选择在两个方向上构建其他占位符.也就是说,共有4种选择.

• 我们必须将x我们没有使用的占位符更新为占位o符.

,轮流这种想法成一个有效的算法最终的观察结果是,我们可以一起一堆置换具有相同数目的放置元件和相同数量的类x和o占位符.这是因为,对于共享所有这三个参数的两个不同的类,它们所代表的排列的数量是相等的.

为了严格证明这一说法,我们可以观察到我们所列举的类是详尽且不重叠的.

前缀

一个小小的想法揭示了在前缀问题中,我们只需要计算以某个元素开头的排列,(称之为b); 以及之间的一些约束i和i+1不再适用.

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

对于第一次修改,我们应该确保在开始之前总是有一个占位符b.放置时b我们乐意将它放在开头占位符中,并且不要在它之前添加任何占位符.

履行

我们DP[i][no][nx]是如何建立,其中第一类数量i的元素已经被放置,并有no和nx类型的占位符o和x分别.在任何状态下,x占位符的数量都在0到2之间.因此状态空间为O(N ^ 2).状态转换是恒定时间,完全如上所述.

没有前缀约束的问题的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 modulo一个相当小的数.)

这是公式的推导:

定义辅助序列:

• 乙_Ñ =的排列数量1 2 ... N,这样正好一个所述的N-1邻接约束被违反.

• C _n =排列的数量,1 2 ... N使得仅N违反涉及该元素的邻接约束.那就是N-1并且N在这些排列中彼此相邻; 并且满足所有其他邻接约束.

我们现在寻找序列A,B和C的重现.

复发一_ñ

假设我们n从有效排列中删除元素P,其中i和i+1从不相邻.得到的排列Q的1 .. n-1必须满足正好以下两种情况之一:

• 没有相邻的数字1 ... n-1相邻Q.也就是说,Q是A _n-1中考虑的排列之一.

• 正好一对(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,K是排列的数量,其中k和k+1连续发生.我们可以合并k,并k+1一起到一个元素,并考虑置换Q的n-1元素,保留相对顺序.

• 如果k-1和k+2(原始标签)都不出现在合并(k,k+1)元素旁边,那么Q对B _n,k贡献2排列- 它们对应于排列和合并元素内的排列.这样的数量是A _n-1.k k+1k+1 kQ

• 如果元素中的一个k-1或k+2出现在(k,k+1)元素旁边,则Q提供1排列.其数量Q为B _n-1,k-1 + B _n-1,k.

• 如果同时k-1和k+2旁边会出现(k,k+1)元素,那么Q有助于1排列.其数量Q为B _n-2,k-1.

我们有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中复发.它留作练习.:-)