uva11538(组合数学)象棋中的皇后

2017年07月15日 10点热度 0人点赞 0条评论

例题1 象棋中的皇后(Chess Queen, UVa 11538
2×2棋盘上放两个相互攻击的皇后(一白一黑) , 一共有12种方
法, 如图
2-1所示。
168
2-1
如果棋盘是n×m的, 有多少种方法放置两个相互攻击的皇后? 例如n
100m223时答案为10907100
【输入格式】
输入由不超过
5000行组成, 每行均为一组数据, 包含两个整数n
m0≤nm≤106
。 输入结束标志为
nm0
【输出格式】
对于每组数据, 输出在
n×m棋盘上放两个相互攻击的皇后的方案数。
输出保证不超过
64位带符号整数的范围。
【分析】
因为只有两个皇后, 因此相互攻击的方式只有两个皇后在同一行、
同一列或同一对角线
3种情况。 这3种情况没有交集, 因此可以用加法原
理。 设在同一行放两个皇后的方案数为
Anm) , 同一列放两个皇后的
方案数为
Bnm) , 同一对角线放两个皇后的方案数为Dnm
, 则
答案为
Anm) +Bnm
Dnm) 。
Anm) 的计算可以用乘法原理: 放白后有nm种方法,
放黑后有
m
1种方法, 相乘就是nmm1
。 也可以理解为先选一行(有
n种方
法) , 然后在这一行中选两个位置做全排列, 因此有
mm1) 种方案。
根据乘法原理得到
nmm1) 。
Bnm) 其实就等于Amn
(想一想, 为什么) , 也就是
mnn1) 。
Dnm) 的思考过程会稍微麻烦一些。 不妨设n≤m
所有/向的
对角线, 从左到右的长度依次为
考虑到还有另一个方向的对角线, 上面的整个结果还要乘以
2, 即
169

程序如下。

//首先要知道这个公式:1^2+2^2+3^2+...+n^2=n*(n-1)*(2*n-1)/6 
#include
#include
using namespace std;
int main(){
	unsigned long long n,m;
	while(cin>>n>>m)
	{
		if(!n&&!m) break;
		if(n>m) swap(n,m);
		cout<

未经允许不得转载!uva11538(组合数学)象棋中的皇后

update

纸上得来终觉浅, 绝知此事须躬行。