https://www.hackerrank.com/challenges/matrix-tracing

[thafnhlong]

Bài toán mang tính chất tam giác pascal Xét ma trận:

Từ vị trí 0, ta có thể "qua phải" hoặc "xuống dưới", vậy ô 1 và ô 4 sẽ có số cách đi vào là 1 ( ô 1 và 4 thì chỉ tới được từ ô 0)

Từ vị trí 2 chỉ có thể tới từ vị trí 1 (tương tự như vị trí 8)

Từ vị trí 3 cũng thế:

Từ vị trí 5 có thể tới từ vị trí 1 và 4, vậy số cách đi vào 5 chính là tổng số cách đi tới 1 và đi tới 4 = 1 + 1 = 2

Cứ như thế...

Xem qua ma trận pascal

Hệ số (hay số cách di tới điểm cuối) chính bằng n C r.

Nhưng ta phải tìm ra n và r

Xét ma trận lớn hơn

Với ma tran 6x3 số cách = 21, ứng với r=7, c= 2; có thể tìm được r= 6+3-2; c = min(3,6)-1;

(Ngoài ra chúng ta có thể giải theo quy hoạch động, nhưng m và n quá lớn nên việc fill table sẽ rất chậm)

// a ^ n mod n
int pow(int mod, int a, int b){
    long ret=1, base = a;
    while(b){
        if (b%2){
            ret*=base;
            ret%=mod;
        }
        b>>=1;
        base*=base;
        base%=mod;
    }
    return ret;
}

// a^-1
int inverse(int mod, int a){
    return pow(mod, a, mod-2);
}

// n!
int perm(int mod, int n){
    long ret=1;
    while(n){
        ret=ret*(n--);
        ret%=mod;
    }
    return ret;
}

// a C b
int combine(int mod, int a, int b){
    // a ! 
    int pa = perm(mod, a);
    // (a-b)! 
    int pab = perm(mod, a-b);
    // b!
    int pb= perm(mod, b);

    int pabb = ((long)pab*pb)%mod;
    int ipabb = inverse(mod, pabb);

    return ((long)pa * ipabb)%mod;
}

int solve(int n, int m) {
    int mod = 1e9+7;   
    // (m+n-2) C [min(m,n)-1]
    return combine(mod, m+n-2, min(m,n)-1);
}

[thafnhlong]

dp

int solve(int m, int n) {
    vector<vector<int>> vec;
    int i=0,j;
    for(;i<m;++i){
        vec.push_back(vector<int>(n));
        j=0;
        for(;j<n;++j){
            if(i==0 || j==0){
                vec[i][j]=1;
            } else {
                vec[i][j]= ((long long)vec[i][j-1]+vec[i-1][j])%1000000007;
            }
        }

    }
    return vec[i-1][j-1];
}