### Tóm tắt bài toán
Một con robot hiện tại đang ở tọa độ $(0, 0)$. Nó có thể thực hiện $N$ phép di chuyển, mỗi phép nhiều nhất một lần. Mỗi phép di chuyển có dạng $(x_i, y_i)$, robot đang ở tọa độ $(X, Y)$ sẽ đi tới tọa độ $(X+x_i, Y+y_i)$. Ta phải đếm số cách có thể đi tới tọa độ $(A, B)$ cho trước.
---
### Hướng giải
**Nhận xét**: Nếu ta di chuyển $M$ lần, thì thứ tự phép di chuyển đó sẽ không ảnh hưởng tới đích đến.
Thay vì đếm cách đi từ $(0, 0)$ tới $(A, B)$ thì ta sẽ đếm số cách đi từ $(0, 0)$ tới $(C, D)$ và từ $(A, B)$ đi ngược trở lại về $(C,D)$.
Sử dụng nhận xét trên và ý tưởng của kỹ thuật **Meet in the middle**, ta sẽ chia đôi $N$ thao tác thành hai tập con, gọi là $E, F$. Ta sẽ tìm các tọa độ mà ta có thể đi từ $(0,0)$ tới mà chỉ sử dụng các thao tác trong $E$, và các tọa độ mà ta có thể đi tới khi đi ngược từ $(A, B)$ trở về. Khi đó ta sẽ đếm số cặp mà xuất hiện trong cả hai tập tọa độ có thể tới.
Việc tính các tọa độ có thể đi tới, ta sẽ dùng backtrack. Còn việc kiểm tra xem có cặp nào xuất hiện trong cả hai tập thì ta sẽ có thể sử dụng `map` hoặc chặt nhị phân (Ta không dùng `set` vì một tọa độ có thể có nhiều cách để đi tới).
---
### Độ phức tạp
- Việc tính các tọa độ có thể đi tới $O\left(2^{\frac{N}{2}}\right)$.
- Ta xét tất cả các phần tử trong một trong hai mảng $E$ hoặc $F$ sẽ mất $O\left(2^{\frac{N}{2}}\right)$ (Do $E$ và $F$ đều có khoảng $2^{\frac{N}{2}}$ phần tử).
- Trong bước kiểm tra, sử dụng tìm kiếm nhị phân, `map` đều có độ phức tạp $O\left(\frac{N}{2}\right)$.
$\Rightarrow$ Tổng độ phức tạp của thuật toán là $O\left(\frac{N}{2} \times2^{\frac{N}{2}}\right)$, hoàn toàn phù hợp với giới hạn $N \leq 40$.
---
### Code tham khảo
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<pair<int, int>> a;
void f(int idx, int end, pair<int, int> cur, vector<pair<int, int>> &b)
{
if (idx == end)
{
b.pb(cur);
return;
}
f(idx + 1, end, cur, b);
cur.first += a[idx].first, cur.second += a[idx].second;
f(idx + 1, end, cur, b);
}
signed main()
{
cin >> n;
int x, y; // (A, B)
cin >> x >> y;
a.resize(n);
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
for (int i = n / 2; i < n; i++)
a[i] = make_pair(-a[i].first, -a[i].second); // thao tác đi ngược
vector<pair<int, int>> one, two; // E, F
f(0, n / 2, {0, 0}, one), f(n / 2, n, {x, y}, two);
map<pair<int, int>, int> mp;
for (auto it : two)
mp[it]++;
int ans = 0;
for (auto it : one)
ans += (mp.find(it) != mp.end() ? mp[it] : 0); // Đếm
cout << ans;
}
```
Defylogicguy
Created at
0 likes