「UVa 11538」Chess Queen - 计数原理

在一个 N * M 棋盘中放置两个皇后,使得它们可以相互攻击,求方案总数。

链接

UVa 11538

题解

两个皇后可以互相攻击,当且仅当它们在「同一行」或「同一列」或「同一对角线」。这三种情况互相独立,可以用加法原理。

考虑「同一行」的情况,用 f(a, b) 表示在一个 a b 列的棋盘中放置两个皇后在同一行的方案数。令 a = 1 ,此时第一个皇后有 b 种放置方法,第二个有 b - 1 种,即

f(1, b) = b(b - 1)

推广到多行的情况,每一行的情况互不影响,可以用加法原理,即:

\begin{align} f(a, b) & = \sum_{i = 1}^{a} b(b - 1) \\ & = ab(b - 1) \\ \end{align}

「同一列」和「同一行」原理相同,行列数互换后代入上式即可。

「同一对角线」的情况比较复杂,假设 m ≥ n ,则同一方向的对角线中,有 m - n + 1 条的长度为 n (蓝色部分),剩下的两边分别有 n - 1 条长度递增。

(图片使用LibreOffice Calc制作)

中间的一撮所对应的情况相当于在一个 m - n + 1 n 列的棋盘中放置,使得两个皇后在同一行,即 f(m - n + 1, n)

两边长度递增的对角线也要按照类似「同一行」的方法推导,即:

\sum_{i = 1}^{n - 1} f(1, i)

但是根据题目的数据范围, O(n) 地每次计算是会超时的,考虑展开。

\begin{align} & \sum_{i = 1}^{n - 1} f(1, i) \\ = & \sum_{i = 1}^{n - 1} i(i - 1) \\ = & \sum_{i = 1}^{n - 1} i ^ 2 - \sum_{i = 1}^{n - 1} i \\ \end{align}

分别使用平方和公式和等差数列求和公式展开,得

\begin{align} & \sum_{i = 1}^{n - 1} i ^ 2 - \sum_{i = 1}^{n - 1} i \\ = & \frac{(n - 1)n(2n - 1)}{6} - \frac{n(n - 1)}{2} \\ = & \frac{n(n - 1)(2n - 4)}{6} \\ = & \frac{n(n - 1)(n - 2)}{3} \\ \end{align}

这是一边的长度递增的对角线上的方案数,两边的要乘以二,因为有两个方向,所以最后还要乘以二。

代码

#include <cstdio>
#include <algorithm>

const int MAXT = 5000;
const int MAXN = 1000000;

inline long long f(long long a, long long b) {
    return a * (b - 1) * b;
}

inline long long g(long long n, long long m) {
    // m >= n
    if (m < n) std::swap(m, n);
    unsigned long long x = ((n - 1) * n * (n - 2)) / 3;
    return f(m - n + 1, n) + x * 2;
}

int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m), !(n == 0 && m == 0)) {
        printf("%llu\n", f(n, m) + f(m, n) + g(n, m) * 2);
    }

    return 0;
}