题意:给出m行n列的棋盘,当两皇后在同行同列或同对角线上时可以互相攻击,问共有多少种攻击方式。
分析:首先可以利用加法原理分情况讨论:①两皇后在同一行;②两皇后在同一列;③两皇后在同一对角线( / 或 \ );
其次利用乘法原理分别讨论:
①同一行时(A),先选某一行某一列放置其中一个皇后,共m*n种情况;其次在选出的这一行里的其他n-1个位置中选一个放另一个皇后;共m*n*(n-1)种情况;
②同一列时(B)情况相同,为n*m*(m-1)种情况;
③同一对角线(D)上时,先讨论 / 方向对角线:
为方便假设m>=n,则从左到右每条对角线长度依次为:
1,2,3,... ...,n-1,n,n,... ...,n,n,n-1,... ... 3,2,1
其中中间的n有(m-n+1)个;
则共有: (1*0 + 2*1 + ... + (n-1)*(n-2)) * 2 + (m-n+1)*n*(n-1) 种情况;
其中∑[1,n-1] (i*(i-1)) = ∑[1,n-1] (i*i - i) = ∑[1,n-1] (i*i) - ∑[1,n-1] (i) ;
又∑[1,n-1] (i*i) = n*(n-1)*(2n-1) / 6; ∑(1,n-1) (i) = n*(n-1) / 2;
则原式可化简为 n*(n-1)*(2n-4)/3 + (m-n+1)*n*(n-1);
再加上 \ 对角线的情况,与上述相同,则D = 2*(n*(n-1)*(2n-4)/3 + (m-n+1)*n*(n-1));
答案为A+B+D;
代码如下
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std; typedef unsigned long long ULL; int main()
{
ULL m, n;
while(cin >> m >> n)
{
if(!m && !n) break;
if(m<n) swap(m, n);
ULL A = m*n*(n-), B = n*m*(m-);
ULL D = *(n*(n-)*(*n-)/ + (m-n+)*n*(n-));
cout << A+B+D << endl;
}
return ;
}