「UVa 11538」Chess Queen - 计数原理

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

链接

UVa 11538

题解

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

考虑「同一行」的情况，用 表示在一个 行 列的棋盘中放置两个皇后在同一行的方案数。令 ，此时第一个皇后有 种放置方法，第二个有 种，即

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

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

「同一对角线」的情况比较复杂，假设 ，则同一方向的对角线中，有 条的长度为 （蓝色部分），剩下的两边分别有 条长度递增。

中间的一撮所对应的情况相当于在一个 行 列的棋盘中放置，使得两个皇后在同一行，即 。

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

但是根据题目的数据范围， 地每次计算是会超时的，考虑展开。

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

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

代码

#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;
}