Bình luận

• 
  

  0

  

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

  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].invfact[k].invfact[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;
  }