题解 | #[SCOI2005]互不侵犯的国王#

互不侵犯的国王

把每一行能不能放国王的信息用二进制编码。

预处理出：

• 如果当前在某些位置放国王，下一行有哪些位置不能放国王（每个国王可以影响到下一行这三个位置。
• 在上一行的限制下，当前行有多少种不同的合理放置国王的方式（上一行被影响到的位置不能放国王，同时当前行放置的国王不能相邻，否则他们会互相攻击）

利用记忆化搜索 来进行记忆化搜索。代表当前遍历到的行下标，代表上一行对当前行的影响，代表当前还有多少个国王需要放置。

边界条件是：

• 当时，所有行都被遍历过了，此时如果，说明所有的国王都被放好了，是一种合理的放置方法，对应的方案数为。否则，还有国王没有被放置，这种放置方法是不合理的，对应的放置方案数为。
• 其他情况下，如果发现，说明所有国王都被合理放置好了，后面也没有国王再放了，因此这个状态就没必要继续进行搜素了。同时，这时候是一种合理的放置方法，对应的方案数为。

from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

inf = float('inf')


def solve(testcase):
    n, k = MI()

    available = [[[] for _ in range(n + 1)] for _ in range(1 << n)]

    for state in range(1 << n):
        A = []
        cnt = 0
        for bit in range(n):
            if state >> bit & 1:
                A.append(bit)
                cnt += 1
        
        for c in range(cnt + 1):
            for comb in combinations(A, c):
                flag = True
                for i in range(1, c):
                    if comb[i] - comb[i - 1] == 1:
                        flag = False
                        break

                if flag:
                    goodstate = 0
                    for ele in comb:
                        goodstate |= 1 << ele
                    available[state][c].append(goodstate)
    
    B = [0 for _ in range(1 << n)]

    for state in range(1 << n):
        for bit in range(n):
            if state >> bit & 1:
                for i in range(bit - 1, bit + 2):
                    if 0 <= i < n:
                        B[state] |= 1 << i

    F = [[[-inf for _ in range(k + 1)] for _ in range(1 << n)] for _ in range(n + 1)]

    full = (1 << n) - 1

    @bootstrap
    def f(row, state, remain):

        if F[row][state][remain] != -inf:
            yield None

        if row == n:
            if remain == 0:
                F[row][state][remain] = 1
            else:
                F[row][state][remain] = 0

            yield None
        
        if remain == 0:
            F[row][state][remain] = 1
            yield None
        
        F[row][state][remain] = 0
        available_state = full ^ state

        for c in range(n + 1):

            if c > remain:
                break
            else:
                for newstate in available[available_state][c]:
                    if F[row + 1][B[newstate]][remain - c] == -inf:
                        yield f(row + 1, B[newstate], remain - c)

                    F[row][state][remain] += F[row + 1][B[newstate]][remain - c]
        
        yield None
    
    f(0, 0, k)

    print(F[0][0][k])
            
for testcase in range(1):
    solve(testcase)