Счёт путей на решётке с запретной клеткой: как вычесть «плохие» пути?

Число монотонных путей из (0,0) в (a,b) равно C(a+b, a) — выбираем, на каких из (a+b) шагов идём вправо. Если одна клетка (x,y) запрещена, считаем пути ЧЕРЕЗ неё и вычитаем: путей через (x,y) = C(x+y, x) · C((W−x)+(H−y), W−x). Ответ = C(W+H, W) − (через запретную).

// fact, inv_fact mod p предподсчитаны
long long paths(int a, int b) {            // (0,0)->(a,b)
    if (a < 0 || b < 0) return 0;
    return fact[a+b] * inv_fact[a] % MOD * inv_fact[b] % MOD;
}
long long answerOneBlock(int W, int H, int x, int y) {
    long long total = paths(W, H);
    long long through = paths(x, y) * paths(W - x, H - y) % MOD;
    return (total - through % MOD + MOD) % MOD;
}

Сложность O(1) на запрос. Для НЕСКОЛЬКИХ препятствий простое вычитание ломается (пути через два препятствия вычтутся дважды) — нужно либо включение-исключение, либо, если препятствий немного (≤ k), ДП по препятствиям: отсортировать их по (x+y), и dp[i] = пути до i-го препятствия минус Σ (путей до более раннего j через j). Это O(k^2) и обходит double-counting.