Jajar Genjang Pascal

Soal#

Informasi#

• Sumber: CompFest 7 - Penyisihan CPC Senior

Arsip#

• TLX

Ringkasan#

$D(N, M, L, R)$ menyatakan jumlah nilai-nilai pada segitiga Pascal yang dilingkup oleh jajar genjang yang

1. titik sudut atasnya mencakup nilai ke-$M$ pada baris ke-$N$ (1-based indexing),
2. sisi kirinya mencakup $L$ nilai berurutan di diagonal kiri bawah titik sudut atasnya (inklusif), dan
3. sisi kanannya mencakup $R$ nilai berurutan di diagonal kanan bawah titik sudut atasnya (inklusif).

Dalam $T$ kasus uji, diberikan $N, M, L, R$. Hitunglah nilai dari $D(N, M, L, R)$ (modulo $10^9 + 9$)!

Sebagai contoh, nilai dari $D(4, 3, 2, 2)$ adalah $23$. Perhatikan ilustrasi berikut.

Solusi#

Petunjuk#

Pembahasan#

Untuk memudahkan, putar segitiga Pascal sebesar $90^\circ$ ke kiri. $$ \begin{array}{ ccccccc } 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 2 & \color{palegreen}{3} & \color{palegreen}{4} & 5 & \cdots \\ 1 & 3 & \color{palegreen}{6} & \color{palegreen}{10} & \cdots \\ 1 & 4 & 10 & \cdots \\ 1 & 5 & \cdots \\ 1 & \cdots \\ \cdots \end{array} $$

Segitiga di atas dapat ditulis dalam bentuk sebagai berikut. $$ \begin{array}{ ccccccc } \binom{0}{0} & \binom{1}{1} & \binom{2}{2} & \binom{3}{3} & \binom{4}{4} & \binom{5}{5} & \cdots \\ \binom{1}{0} & \binom{2}{1} & \binom{3}{2} & \binom{4}{3} & \binom{5}{4} & \cdots \\ \binom{2}{0} & \binom{3}{1} & \binom{4}{2} & \binom{5}{3} & \cdots \\ \binom{3}{0} & \binom{4}{1} & \binom{5}{2} & \cdots \\ \binom{4}{0} & \binom{5}{1} & \cdots \\ \binom{5}{0} & \cdots \\ \cdots \end{array} $$

Jadi $D(N, M, L, R)$ juga dapat dinyatakan sebagai jumlah nilai-nilai pada segitiga Pascal yang dilingkup oleh persegi panjang yang

1. titik sudut kiri atasnya mencakup kolom ke-$M$ pada baris ke-$(\color{blue}{N - M + 1}$$)$ atau $(N - M + 1, M)$ (1-based indexing),
2. sisi vertikalnya mencakup $L$ nilai berurutan di baris bawah titik sudut kiri atasnya (inklusif), dan
3. sisi horizontalnya mencakup $R$ nilai berurutan di kolom kanan titik sudut kiri atasnya (inklusif).

Oleh karena itu, kita bisa menggunakan teknik mirip yang digunakan untuk mencari jumlahan nilai pada persegi panjang dengan prefix sum. Didefiniskan $F(X, Y)$ sebagai jumlah nilai-nilai pada segitiga Pascal yang dilingkup oleh persegi panjang dengan titik sudut kiri atas $(1, 1)$ dan titik sudut kiri bawah $(X, Y)$. Misal

• $a = N - M + 1$,
• $b = M$,
• $c = a + L - 1 = N - M + L$, dan
• $d = b + R - 1 = M + R - 1$

Maka, $D(N, M, L, R) = F(c, d) - F(a - 1, d) - F(c, b - 1) + F(a - 1, b - 1)$

Berikut adalah notasi sigma dari $F(X, Y)$. $$F(X, Y) = \sum_{i = 0}^{X - 1} \sum_{j = 0}^{Y - 1} \binom{i + j}{j}$$ Dengan identitas stik hoki (hockey-stick identity), kita bisa menyederhanakannya. $$ \begin{aligned} F(X, Y) &= \sum_{i = 0}^{X - 1} \sum_{j = 0}^{Y - 1} \binom{i + j}{j} \\ &= \sum_{i = 0}^{X - 1} \binom{(Y - 1) + i + 1}{Y - 1} \\ &= \sum_{i = 0}^{X - 1} \binom{Y + i}{Y - 1} \\ &= \sum_{i = \color{red}{1}}^{\color{red}{X}} \binom{Y + (i - 1)}{Y - 1} \\ &= \sum_{i = 1}^X \binom{Y - 1 + i}{Y - 1} + 1 - 1 \\ &= \sum_{i = 1}^X \binom{Y - 1 + i}{Y - 1} + \binom{Y - 1 + 0}{Y - 1} - 1 \\ &= \sum_{i = \color{red}{0}}^X \binom{(Y - 1) + i}{(Y - 1)} - 1 \\ &= \binom{(Y - 1) + X + 1}{X} - 1 \\ &= \binom{Y + X}{X} - 1 \end{aligned} $$

Note

Diketahui identitas stik hoki sebagai berikut. $$\sum_{j = 0}^{n - r} \binom{j + r}{j} = \binom{n + 1}{r + 1}$$ Lakukan substitusi $c \leftrightarrow n - r$. $$\sum_{j = 0}^c \binom{j + r}{j} = \sum_{j = 0}^c \binom{j + r}{r} = \binom{c + r + 1}{r + 1} = \binom{c + r + 1}{c}$$

Kode#

#include <iostream>
using namespace std;
typedef long long int lli;

const int MOD = 1E9 + 9;
const int MAXX = 500000;

int T, N, M, L, R;
lli Fact[MAXX + 1];

int Pow(lli x, int y){
    lli ret = 1;
    while(y){
        if(y & 1) (ret *= x) %= MOD;
        (x *= x) %= MOD;
        y >>= 1;
    }
    return ret;
}

int mod_inv(int x){
    return Pow(x, MOD - 2);
}

int C(int n, int k){
    if(n < 0 || k < 0 || n - k < 0) return 0;
    int denom = Fact[k] * Fact[n - k] % MOD;
    return Fact[n] * mod_inv(denom) % MOD;
}

lli F(int X, int Y){
    return (C(Y + X, X) - 1 + MOD) % MOD;
}

int D(int N, int M, int L, int R){
    int a = N - M + 1;
    int b = M;
    int c = a + L - 1;
    int d = b + R - 1;

    lli ret = F(c, d) - F(a - 1, d) - F(c, b - 1) + F(a - 1, b - 1);
    ret %= MOD;
    if(ret < 0) ret += MOD;
    return ret;
}

int main(){
    Fact[0] = 1;
    for(int i = 1; i <= MAXX; i++)
        Fact[i] = (Fact[i - 1] * i) % MOD;

    cin >> T;
    while(T--){
        cin >> N >> M >> L >> R;
        cout << D(N, M, L, R) << '\n';
    }
    return 0;
}