To solve this problem, we need to determine the number of ways to place m non-attacking kings on an n x n grid. Non-attacking kings are those that are not adjacent to each other, including diagonally.

Approach

1. Valid Masks: Generate all valid masks for a single row. A valid mask is a bitmask where no two 1s (representing kings) are adjacent. This can be checked using mask & (mask << 1) == 0.
2. Count Kings: For each valid mask, compute the number of kings (set bits) it contains.
3. Dynamic Programming (DP): Use a DP approach where dp[i][mask][k] represents the number of ways to place k kings in the first i rows with the i-th row using mask. We optimize space by using two 2D arrays (prev_dp and curr_dp) to keep track of the previous and current rows.
4. Compatibility Check: For consecutive rows, ensure that the masks are compatible (no vertical or diagonal adjacency between kings in the previous and current rows). This is checked using three conditions:
   • No vertical adjacency: curr_mask & prev_mask == 0
   • No diagonal left-up to right-down: curr_mask & (prev_mask << 1) == 0
   • No diagonal right-up to left-down: curr_mask & (prev_mask >> 1) == 0

Solution Code

n, m = map(int, input().split())

# Generate all valid masks for a row of n columns
valid_masks = []
mask_counts = []
for mask in range(0, 1 << n):
    if (mask & (mask << 1)) == -0:  # Check no consecutive 1s
        valid_masks.append(mask)
        mask_counts.append(bin(mask).count('1'))

# Initialize DP for the first row
num_masks = len(valid_masks)
prev_dp = [[0] * (m + 1) for _ in range(num_masks)]
for i in range(num_masks):
    cnt = mask_counts[i]
    if cnt <= m:
        prev_dp[i][cnt] = 1

# Fill DP for subsequent rows
for row in range(2, n + 1):
    curr_dp = [[0] * (m + 1) for _ in range(num_masks)]
    for curr_idx in range(num_masks):
        curr_mask = valid_masks[curr_idx]
        curr_cnt = mask_counts[curr_idx]
        if curr_cnt > m:
            continue
        for prev_idx in range(num_masks):
            prev_mask = valid_masks[prev_idx]
            # Check compatibility between current and previous mask
            if (curr_mask & prev_mask) != 0:
                continue
            if (curr_mask & (prev_mask << 1)) != 0:
                continue
            if (curr_mask & (prev_mask >> 1)) != 0:
                continue
            # Update current DP state
            for k in range(curr_cnt, m + 1):
                curr_dp[curr_idx][k] += prev_dp[prev_idx][k - curr_cnt]
    prev_dp = curr_dp

# Sum all valid ways to place m kings in the n-th row
result = sum(prev_dp[i][m] for i in range(num_masks))
print(result)

Explanation

• Valid Masks: We generate all possible masks for a row and filter out those with consecutive kings.
• DP Initialization: The first row's DP is initialized with the count of kings in each valid mask.
• DP Transition: For each row, we compute the valid ways to place kings by checking compatibility with the previous row's masks and updating the DP state.
• Result: The sum of all valid ways to place m kings in the last row gives the final answer.

This approach efficiently handles the constraints and ensures we count all valid configurations of non-attacking kings. The complexity is manageable, making it suitable for the given problem limits.

作者声明:本文包含人工智能生成内容。