首页 > 代码库 > UVA 11538 - Chess Queen(数论+计数问题)
UVA 11538 - Chess Queen(数论+计数问题)
题目链接：11538 - Chess Queen
题意：给一个n*m棋盘，问放两个皇后，使得两个皇后互相能攻击到，有几种放法
思路：分横竖，对角线来考虑。
横：n * A(m, 2)种
竖：m * A(n, 2)种
对角线：由于有两条，可以算一条再乘2
2 * 所有对角线和（A（对角线格数，2））。
那么对角线格数为:(1, 2, 3, 4 ... n .n .n .n.n - 1. .. 4. 3 .2. 1) 然后为n的有m - n + 1条（m >= n)
所以答案为：2*(2*∑i*(i-1) + (m-n+1)*n*(n-1)) (1 <= i <= n - 1)
可以进行化简，*∑i*(i-1) （1 <= i <= n -1） = (n - 2) * (n - 1) * n / 3;
化简后得到式子为：n * m * (n + m - 2) + 2 * n * (n - 1) * (3 * m - n - 1) / 3
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long n, m;
int main() {
while (~scanf("%lld%lld", &n, &m) && n || m) {
if (n > m) swap(n, m);
printf("%lld\n", n * m * (n + m - 2) + 2 * n * (n - 1) * (3 * m - n - 1) / 3);
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。