View Animation Rotation trong Swift

Ý tưởng

Nhận xét thấy, một đường đi thỏa mãn gồm $m + n$ bước đi (mỗi bước đi là một cạnh ô vuông). Tại mỗi bước đi chỉ được chọn một trong hai giá trị đi lên (ta đặt là $1$) hoặc đi sang phải (ta đặt là $0$). Số bước đi lên đúng bằng $n$ và số bước sang phải đúng bằng $m$. Bài toán lúc này dẫn đến việc tìm xem có bao nhiêu dãy nhị phân có độ dài $m + n$ trong đó có đúng $n$ thành phần có giá trị bằng $1$. Dựa trên bài toán chia kẹo Euler, kết quả cần tìm lúc này là $m + n \choose m$. Ta có thể tính tổ hợp $n \choose k$ bằng quy hoạch động dựa trên tính chất sau của tổ hợp:

$${n \choose k} = {n - 1 \choose k - 1} + {n - 1 \choose k}$$

Độ phức tạp: $O(n^2)$. Các bạn cần kết hợp với việc tính toán modulo liên tục để tránh gây ra tràn số nếu như sử dụng ngôn ngữ C++.

Cài đặt

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long ncr[5005][5005], n, m;
void pre_compute()
{
    int k;
    for (int i = 0; i < 5001; i++)
    {
        ncr[i][0] = ncr[i][i] = 1;
        // Chỉ tính đến vị trí cột thứ i / 2 là đủ cho hàng i.
        k = i >> 1;
        for (int j = 1; j < k + 1; j++)
            ncr[i][j] = ncr[i][i - j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % MOD;
    }
}
int main()
{
    int m, n;
    cin >> m >> n;
    pre_compute();
    cout << ncr[m + n][m];
    return 0;
}