UVA 11538 Chess Queen （數學）

ProblemAChess Queen
Input: Standard Input

Output: Standard Output

You probably know how the game of chess is played and howchess queen operates. Two chess queens are in attacking position when they areon same row, column or diagonal of a chess board. Suppose two such chess queens(one black and the other white) are placed on (2x2) chess board. They can be inattacking positions in 12 ways, these are shown in the picture below:

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+R2l2ZW4gYW4gKDxzdHJvbmc+Tjwvc3Ryb25nPng8c3Ryb25nPk08L3N0cm9uZz4pIGJvYXJkIHlvdSB3aWxsIGhhdmUgdG8gZGVjaWRlIGluIGhvd21hbnkgd2F5cyAyIHF1ZWVucyBjYW4gYmUgaW4gYXR0YWNraW5nIHBvc2l0aW9uIGluIHRoYXQuPC9wPgo8cD48c3Ryb25nPklucHV0PC9zdHJvbmc+PC9wPgo8cD5JbnB1dCBmaWxlIGNhbiBjb250YWluIHVwIHRvIDUwMDAgbGluZXMgb2YgaW5wdXRzLiBFYWNoIGxpbmVjb250YWlucyB0d28gbm9uLW5lZ2F0aXZlIGludGVnZXJzIHdoaWNoIGRlbm90ZSB0aGUgdmFsdWUgb2Y8c3Ryb25nPk08L3N0cm9uZz4gYW5kCjxzdHJvbmc+Tjwvc3Ryb25nPiAoPHN0cm9uZz4wPCBNLCBOoeoxMDxzdXA+Njwvc3VwPjwvc3Ryb25nPikgcmVzcGVjdGl2ZWx5LjwvcD4KPHA+SW5wdXQgaXMgdGVybWluYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyB0d28gemVyb2VzLiBUaGVzZXR3byB6ZXJvZXMgbmVlZCBub3QgYmUgcHJvY2Vzc2VkLjwvcD4KPHA+PHN0cm9uZz5PdXRwdXQ8L3N0cm9uZz48L3A+CjxwPkZvciBlYWNoIGxpbmUgb2YgaW5wdXQgcHJvZHVjZSBvbmUgbGluZSBvZiBvdXRwdXQuIFRoaXMgbGluZWNvbnRhaW5zIGFuIGludGVnZXIgd2hpY2ggZGVub3RlcyBpbiBob3cgbWFueSB3YXlzIHR3byBxdWVlbnMgY2FuIGJlIGluYXR0YWNraW5nIHBvc2l0aW9uIGluICBhbiAoPHN0cm9uZz5NeE48L3N0cm9uZz4pIGJvYXJkLCB3aGVyZSB0aGUgdmFsdWVzIG9mPHN0cm9uZz5NPC9zdHJvbmc+CiBhbmQgPHN0cm9uZz5OPC9zdHJvbmc+IGNhbWUgZnJvbSB0aGUgaW5wdXQuIEFsbCBvdXRwdXQgdmFsdWVzIHdpbGwgZml0IGluIDY0LWJpdCBzaWduZWRpbnRlZ2VyLjwvcD4KPHA+PGJyPgo8L3A+CjxwIGFsaWduPQ=="left">SampleInput Outputfor Sample Input

2 2

100 223

2300 1000

0 0

12

10907100

11514134000

Problemsetter: Shahriar Manzoor

Special Thanks to: Mohammad Mahmudur Rahman

分析：

因為只有兩個皇後，因此相互攻擊的方式只有兩個皇後在同一行，同一列或同一對角線3中情況，這3中情況沒有交集，因此可以采用加法原理，設在同一行放置兩個皇後的方案數位A(n,m), 同一列放置兩個皇後的方案數為B(n,m),在同一對角線放置兩個皇後的方案數為D(n, m); 則答案為A(n, m)+B(n, m)+D(n, m);

A(n, m)的計算可以采用乘法原理，放白有n 種方法，放黑有(m-1)種方法，相乘就是n*m*(m-1);

B(n, m)計算的方法跟上述的一樣，共有m*n*(n-1)種；

求D(n, m)的過程會稍微麻煩一些，不妨設n <= m 所有/向對角線，從左到右的長度依次為

1,2,3,4.....n-1, n, n.....n, n,n-1....4,3,2,1注意：共有(m-n+1)個n;

考慮到還有另一個方向的對角線，上面的整個結果還要乘以2，即：

公式有點變態，那個鳥符號我打不出來，所以公式就打不出來。。。嘻嘻

最後化簡後的公式：

D(n, m) =2(m(n-1)(2n-4)/4 + (m-n+1)(n-1)m) = 2n(n-1)(3m-n-1)/3;

用加法原理就行啦。。

代碼：

#include 
#include 
#include 
#include 
using namespace std;

typedef unsigned long long ULL;

int main()
{
    ULL n, m;
    while(~scanf("%lld %lld", &n, &m) && n || m) {
        if(n > m) swap(n, m);
        printf("%lld\n", n*m*(m+n-2)+2*n*(n-1)*(3*m-n-1)/3);
    }
    return 0;
}