【UVA-11538】解题报告（数学，组合数）

原始题目

题目大意

在\(n \times m\)的棋盘上放置\(2\)个皇后（一黑一白），问相互攻击的情况共有多少种。

解题思路

  • 根据加法原理，总情况由下面三种子情况构成（覆盖全部切不重复）（n<m)

    两个皇后在同一行，情况数为\(nm(m-1)\)

    两个皇后在同一列，情况数为\(mn(n-1)\)

    两个皇后在同一斜行，情况数为\(2 \times (2 \sum_{i=1}^{n-1}{i(i-1)} + (m+1-n)n(n-1)) = 2 \times( (2 \frac {n(n-1)(2n-4)}{6} )+(m-n+1)n(n-1))\)

    相加即可

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-a;i>=a;--i)
#define se second
#define fi first
#define eps 1e-8
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
const int maxl=26;
const int maxm=1e5+5;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
ll n,m;
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>m&&n+m){
			if(n>m) swap(n,m);
			ll ans=(n*m*(m-1) );
			ans+=(m*n*(n-1));
			ans+=(2*(n*(n-1)*(2*n-4)/6)+(m-n+1)*n*(n-1))*2;
			cout<<ans<<endl;
		
	}
}

收获与反思

  • 熟悉排列组合的加法原理与乘法原理
  • 两个求和公式以及简单叠加

\[\sum {i=1}^n i = \frac {n(n+1)}{2} \]

\[\sum {i=1}^n {i^2} = \frac {n(n+1)(2n+1)}{6} \]

推导出

\[\sum {i=1}^n {i(i-1)} = \frac {n(n+1)(n-1)}{3} \]