Bình luận

• 
  

  3

  

  pppssslc  đã bình luận lúc 14, Tháng 5, 2025, 14:52 ← sửa 10 →

  Spoil!!!

  Giải thích:

  TH1: ~m ≤ 1000~ và ~n ≤ 1000~

  • Gọi ~f[i][j]~ là số cách có thể tới được ô ~(i, j)~.
  • Quy hoạch động như bình thường với công thức truy hồi:

  • Nếu ô ~(i, j)~ không bị chặn: ~f[i][j] = f[i-1][j] + f[j][i-1]~.

  • Nếu ô ~(i, j)~ bị chặn: ~f[i][j] = 0~.

  TH2: ~m > 1000~ hoặc ~n > 1000~

  • Ta thấy đề bài cho ~x[t] ≤ 1000~ và ~y[t] ≤ 1000~ nên:

  Ta quy hoạch động như TH1 tới ~f[1000][1000]~.(có thể nhỏ hơn nếu ~n~ hoặc ~m~ nhỏ hơn ~1000~)

  • Nhận xét:

  Muốn đi từ ~(0, 0)~ tới ~(m, n)~ thì phải đi qua ~1~ trong số các ô:

  ~(1, 1000), (2, 1000),..., (min(1000, n), 1000)~(với ~m>1000~)

  ~(1000, 1), (1000, 2),..., (1000, min(1000, m))~(với ~n>1000~)

  → Đáp án sẽ là:

  Tổng số cách đi từ ~(0, 0)~->mỗi ô bên trên->~(n, m)~.

  Hay là tổng của:

  (số cách đi (~1001, i~) → (~m, n~)) × ~f[i][1000]~ với i là ~1 → min(1000, n)~. (nếu ~m > 1000~)

  (số cách đi (~1001, i~) → (~n, m~)) × ~f[1000][i]~ với i là ~1 → min(1000, m)~. (nếu ~n > 1000~)

  Lưu ý:

  Tại sao không phải là ~(1000, i)~ mà là ~(1001, i)~ là do nếu tính từ ~(1000, i)~ thì sẽ bị trùng, khi mà tính các cách đi sang phải nếu ~n > 1000~ và đi xuống dưới nếu ~m > 1000~, mà sau đó ta lại tính tới các cách đó → bị trùng lặp nhiều lần. Vì vậy thì cần tính từ ~(1001, i)~.

  Cách tính số cách đi từ ~(a, b) → (x, y)~:

  • Là tổ hợp chập ~(x - a)~ của ~(x - a + b - y)~.

  • Tính tổ hợp:

    • Chuẩn bị trước 2 mảng ~fact~ và ~inv_fact~ để lưu các giai thừa và nghịch đảo modular của các giai thừa.

    • Tổ hợp chập ~k~ của ~n~ sẽ là ~fact[n] × inv_fact[k] × inv_fact[n-k]~.

  Code mẫu:

  #include<bits/stdc++.h>
  #define str string
  #define ll long long
  #define db double
  #define pii pair < int, int>
  #define piii pair < int, pii>
  #define piiii pair < pii, pii>
  #define se second
  #define fi first
  #define vi vector<int>
  #define vii vector<vector<int>>
  #define mpii map < int, int>
  #define umpii unordered_map < int, int>
  #define si set<int>
  #define usa unordered_set<int>
  #define mulsi multiset<int>
  using namespace std;
  
  const ll mod=1e9+7;
  const ll maxn=2e5;
  const ll maxm=1e3;
  
  ll n, m, k, res;
  ll fact[maxn+1], inv_fact[maxn+1], f[maxm+1][maxm+1];
  
  ll pow(ll n, ll k){
      if(k==0)return 1;
      ll a=pow(n, k/2);
      if(k%2==0)return (a*a)%mod;
      else return ((a*a)%mod*n)%mod;
  }
  
  void init(){
      fact[0]=1;
      for(int i=1; i<=maxn; ++i)fact[i]=(fact[i-1]*i)%mod;
      inv_fact[maxn]=pow(fact[maxn], mod-2);
      for(int i=maxn-1; i>=0; --i)inv_fact[i]=(inv_fact[i+1]*(i+1))%mod;
  }
  
  ll C(ll n, ll k){
      if(0>k || k>n) return 0;
      return (((fact[n]*inv_fact[k])%mod)*inv_fact[n-k])%mod;
  }
  
  ll cnt(ll a, ll b, ll x, ll y){
      return C(x-a+y-b, max(y-b, x-a));
  }
  
  int main(){
      ios_base::sync_with_stdio(0);
      cin.tie(0); cout.tie(0);
      init();
      cin>>n>>m>>k;
      for(int i=1; i<=k; ++i){
          int x, y; cin>>x>>y;
          f[x][y]=1;
      }
      for(int i=1; i<=min(maxm, n); ++i){
          for(int j=1; j<=min(maxm, m); ++j){
              if(i==1 && j==1)f[i][j]=1;
              else if(f[i][j])f[i][j]=0;
              else f[i][j]=f[i-1][j]+f[i][j-1];
              f[i][j]%=mod;
          }
      }
      if(maxm < n){
          for(int i=1; i<=min(maxm, m); ++i){
              res=(res+(cnt(maxm+1, i, n, m)*f[maxm][i])%mod)%mod;
          }
      }
      if(maxm < m){
          for(int i=1; i<=min(maxm, n); ++i){
              res=(res+(cnt(maxm+1, i, m, n)*f[i][maxm])%mod)%mod;
          }
      }
      if(maxm>=m && maxm>=n)res=f[n][m];
      cout << res;
      return 0;
  }
  

  Lưu ý:

  Lời giải chỉ mang tính tham khảo nên đừng ai copy lời giải này.