# Chỉ xem lời giải khi thực sự bí ý tưởng nha các bạn
Với bài này, chúng ta cần "tư duy ngược" một chút. Thay vì nghĩ cách tính trực tiếp thì ta sẽ
lấy đáp án bằng cách:
$$ TotalWays - BadWays = GoodWays $$
Từ đây bài toán của chúng ta quay về cách tính $TotalWays$ và $BadWays$
## 1. Cách tính $TotalWays$
Có thể chọn ra 3 điểm bất kỳ từ tập $N*M$ điểm, vậy tổng số cách chọn là
$$C(3,N * M)$$
## 2. Cách tính $BadWays$
Chúng ta cần xét các trường hợp không tạo được tam giác từ 3 điểm trên bảng
### 2.1. 3 điểm thuộc cùng 1 hàng
chúng ta có $N$ hàng, mỗi hàng chúng ta có thể chọn ra 3 điểm từ tập $M$ điểm, vậy số cách
chọn 3 điểm thuộc cùng 1 hàng là
$$ N * C(3,M) $$
### 2.2 3 điểm thuộc cùng 1 cột
Tương tự với trường hợp trên, ta cũng sẽ có công thức
$$ M * C(3,N) $$
### 2.3. 3 điểm thuộc cùng 1 đường chéo
Ta xét bảng $n * m$.
Có **2 họ đường chéo**:
* Song song với đường chéo chính (`\`)
* Song song với đường chéo phụ (`/`)
Ta sẽ tính cho một họ rồi nhân đôi (vì đối xứng).
---
## Số lượng đường chéo
Với mỗi họ, số đường chéo là:
$$
n + m - 1
$$
---
## Độ dài các đường chéo
Độ dài các đường chéo tạo thành dãy:
$$
1,2,3,\dots,\min(n,m),\dots,3,2,1
$$
Nếu giả sử $n <= m $, thì dãy độ dài sẽ có dạng:
* Tăng từ 1 đến n
* Có $m-n+1$ đường chéo độ dài $n$
* Sau đó giảm dần từ $n-1$ xuống 1
---
## Số cách chọn 3 điểm trên một đường chéo
Với một đường chéo có độ dài (k), số cách chọn 3 điểm là:
$$
C(3,k)
$$
Vì vậy tổng số bộ ba thẳng hàng theo một họ đường chéo là:
$$
\sum C(3, \text{độ dài})
$$
---
## Công thức tổng quát (giả sử ( n \le m ))
Tổng số bộ ba thẳng hàng theo một họ đường chéo là:
$$
\sum_{k=1}^{n} C(3,k)+(m-n) \cdot C(3,n)+\sum_{k=1}^{n-1} C(3,k)
$$
Gộp lại:
$$
2 \sum_{k=1}^{n-1} C(3,k)+(m-n+1) C(3,n)
$$
---
## Vì có 2 họ đường chéo
Nên tổng số bộ ba thẳng hàng theo đường chéo là:
$$
2 \left(2 \sum_{k=1}^{n-1} C(3,k)+(m-n+1) C(3,n)\right)
$$
```cpp
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
#define ll long long
#define int ll
#define pb push_back
#define all(x) x.begin() + 1, x.end()
#define nall(x) x.begin(), x.end()
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define endl "\n"
#define se second
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mem(a, x) memset(a, x, sizeof(a))
#define working cerr<<"If u see this message, your code is working"<<endl;
#define trailingzero(x) __builtin_ctzll(x)
#define cntbit1(x) __builtin_popcountll(x)
#define leadingzero(x) __builtin_clzll(x)
#define _______TOISETHIVOI_______ signed main()
#define KILL() exit(0)
#define NAME "duxp"
template <typename T>
inline int getbit(T x, int k) { return (x >> k) & 1; }
template <typename T>
inline T onbit(T x, int k) { return x | (T(1) << k); }
template <typename T>
inline T offbit(T x, int k) { return x & ~(T(1) << k); }
const ll OO = 1e18;
const int oo = 1e9;
const int MOD = 1000000007;
const int MOD2 = 998244353;
const int MAXN = 1000;
int n, m;
int C(int x) {
if (x < 3) return 0;
return x * (x - 1) * (x - 2) / 6;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
_______TOISETHIVOI_______
{
fast;
if (FILE *f = fopen(NAME ".inp", "r")) {
fclose(f);
freopen(NAME ".inp", "r", stdin);
freopen(NAME ".out", "w", stdout);
}
cin>>n>>m;
int total = C(n * m);
int bad = 0;
bad += n * C(m);
bad += m * C(n);
for(int dx = 1; dx < n; dx++) {
for(int dy = 1; dy < m; dy++) {
int g = gcd(dx, dy);
if(g >= 2) {
bad += 2LL * (n - dx) * (m - dy) * (g - 1);
}
}
}
cout << total - bad;
}
```
Phatgivp10
Created at
0 likes