Один спільний коридор#13119

Один спільний коридор (Розбір)

Розв'язок

Потрібно порахувати кількість пар маршрутів, які мають рівно один спільний неперервний відрізок, що містить щонайменше дві клітинки.

Кожен маршрут може рухатися лише вправо або вниз. Нехай $A = (1, a)$ A=(1,a) та $B = (b, 1)$ B=(b,1) — початкові клітинки, а $C = (c, w)$ C=(c,w) та $D = (h, d)$ D=(h,d) — кінцеві.

Основне спостереження полягає в тому, що кожну сумісну пару маршрутів можна однозначно розділити на три частини:

Два маршрути без спільних клітинок від $A$ та $B$ до першої спільної клітинки.
Один спільний шлях, який містить щонайменше одне ребро.
Два маршрути без спільних клітинок від останньої спільної клітинки до $C$ та $D$ .

Порахуємо кількість способів побудувати кожну з цих частин за допомогою динамічного програмування.

Підрахунок шляхів

Спочатку обчислимо чотири масиви:

$F_{A} (v)$ F_A(v) — кількість шляхів від $A$ до клітинки $v$ .
$F_{B} (v)$ F_B(v) — кількість шляхів від $B$ до клітинки $v$ .
$G_{C} (v)$ G_C(v) — кількість шляхів від клітинки $v$ до $C$ .
$G_{D} (v)$ G_D(v) — кількість шляхів від клітинки $v$ до $D$ .

Усі шляхи мають проходити лише через вільні клітинки та рухатися вправо або вниз.

Перші два масиви можна обчислити, проходячи таблицю зверху вниз та зліва направо. Наприклад, для вільної клітинки $(i, j)$ :

F_{A} (i, j) = F_{A} (i - 1, j) + F_{A} (i, j - 1),

F_A(i,j)=F_A(i-1,j)+F_A(i,j-1),

з початковим значенням $F_{A} (A) = 1$ F_A(A)=1.

Аналогічно, $G_{C}$ G_C та $G_{D}$ G_D можна обчислити у зворотному порядку:

G_{C} (i, j) = G_{C} (i + 1, j) + G_{C} (i, j + 1) .

G_C(i,j)=G_C(i+1,j)+G_C(i,j+1).

Усі значення обчислюємо за модулем $1 0^{9} + 7$ 10^9+7.

Перша спільна клітинка

Нехай $v = (i, j)$ v=(i,j) — перша спільна клітинка двох маршрутів.

Оскільки до $v$ маршрути не перетинаються, вони повинні потрапити в цю клітинку з різних напрямків.

Позначимо клітинку над $v$ через $U = (i - 1, j)$ U=(i-1,j), а клітинку ліворуч — через $L = (i, j - 1)$ L=(i,j-1).

Оскільки перший маршрут починається на верхній межі таблиці, а другий — на лівій, перший маршрут повинен потрапити у $v$ через $U$ , а другий — через $L$ .

Потрібно порахувати кількість пар шляхів від $A$ до $U$ та від $B$ до $L$ , які не мають спільних клітинок.

За лемою Ліндстрема — Гесселя — В'єно ця кількість дорівнює

j o in (v) = F_{A} (U) F_{B} (L) - F_{A} (L) F_{B} (U) .

join(v)=F_A(U)F_B(L)-F_A(L)F_B(U).

Віднімання прибирає пари шляхів, які перетинаються до потрапляння у $v$ . Через взаємне розташування початкових і кінцевих клітинок шляхи з протилежним поєднанням кінців не можуть бути неперетинними.

Для клітинок на верхній або лівій межі, а також для заблокованих клітинок, покладемо $j o in (v) = 0$ join(v)=0.

Отже, $j o in (v)$ join(v) — кількість способів, якими два кур'єри можуть уперше зустрітися у клітинці $v$ .

Остання спільна клітинка

Тепер нехай $v = (i, j)$ v=(i,j) — остання спільна клітинка.

Після виходу з $v$ маршрути повинні одразу розділитися та більше не перетинатися.

Позначимо клітинку праворуч від $v$ через $R = (i, j + 1)$ R=(i,j+1), а клітинку знизу — через $T = (i + 1, j)$ T=(i+1,j).

Оскільки перший кур'єр завершує маршрут на правій межі, а другий — на нижній, перший маршрут повинен виходити через $R$ , а другий — через $T$ .

Використовуючи ту саму лему, отримуємо кількість способів завершити обидва маршрути без подальших перетинів:

s pl i t (v) = G_{C} (R) G_{D} (T) - G_{C} (T) G_{D} (R) .

split(v)=G_C(R)G_D(T)-G_C(T)G_D(R).

Для клітинок на правій або нижній межі, а також для заблокованих клітинок, покладемо $s pl i t (v) = 0$ split(v)=0.

Спільний відрізок

Ми вже обчислили кількість способів почати та завершити спільний відрізок. Залишилося з'єднати його кінці.

Нехай $d p (v)$ — кількість способів вибрати першу спільну клітинку та побудувати спільний шлях, який закінчується у $v$ і містить щонайменше одне ребро.

Для кожної клітинки $u$ можемо почати спільний відрізок $j o in (u)$ способами.

Проте не можна одразу завершити його в $u$ , оскільки спільний відрізок повинен містити щонайменше дві клітинки.

Тому такі нові відрізки враховуватимемо лише під час переходу з $u$ до однієї із сусідніх клітинок.

Для вільної клітинки $v = (i, j)$ v=(i,j) нехай $U$ та $L$ знову позначають її верхнього та лівого сусідів.

Тоді

d p (v) = d p (U) + j o in (U) + d p (L) + j o in (L) .

dp(v)=dp(U)+join(U)+dp(L)+join(L).

Тут $d p (U)$ та $d p (L)$ враховують продовження вже побудованих спільних відрізків, а $j o in (U)$ join(U) та $j o in (L)$ — відрізки, які починаються у відповідних сусідніх клітинках.

Таким чином, кожен врахований спільний відрізок гарантовано містить щонайменше одне ребро.

Нарешті, якщо спільний відрізок закінчується у $v$ , існує $s pl i t (v)$ split(v) способів завершити обидва маршрути без подальших перетинів.

Отже, відповідь дорівнює

an s = v \sum d p (v) \cdot s pl i t (v) (mod 1 0^{9} + 7) .

ans=\sum_v dp(v)\cdot split(v)\pmod{10^9+7}.

Кожна сумісна пара маршрутів має однозначно визначені першу та останню спільні клітинки, тому буде порахована рівно один раз.

Асимптотична складність

Кожен із чотирьох масивів кількостей шляхів можна обчислити за $O (h w)$ часу.

Значення $j o in (v)$ join(v), $s pl i t (v)$ split(v) та $d p (v)$ також обчислюються за $O (1)$ для кожної клітинки.

Отже, загальна часова складність становить $O (h w)$ , а просторова — $O (h w)$ .

Реалізація

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int mod = 1e9 + 7;

void solve() {
    int h, w;
    cin >> h >> w;

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    --a; --b; --c; --d;

    vector<string> g(h);
    for (auto &s : g) cin >> s;

    int n = h * w;

    vector<int> fromA(n), fromB(n);
    vector<int> join(n), dp(n);
    vector<int> toC(n), toD(n);

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            int v = i * w + j;

            if (g[i][j] == '#') continue;

            int up = v - w;
            int left = v - 1;

            ll x = (i == 0 && j == a);
            ll y = (i == b && j == 0);

            if (i) {
                x += fromA[up];
                y += fromB[up];
            }

            if (j) {
                x += fromA[left];
                y += fromB[left];
            }

            fromA[v] = x % mod;
            fromB[v] = y % mod;

            if (i && j) {
                int t = 1LL * fromA[up] * fromB[left] % mod;

                t -= 1LL * fromA[left] * fromB[up] % mod;

                if (t < 0) t += mod;

                join[v] = t;
            }

            ll z = 0;

            if (i) {
                z += dp[up] + join[up];
            }

            if (j) {
                z += dp[left] + join[left];
            }

            dp[v] = z % mod;
        }
    }

    int ans = 0;

    for (int i = h - 1; i >= 0; i--) {
        for (int j = w - 1; j >= 0; j--) {
            int v = i * w + j;

            if (g[i][j] == '#') continue;

            int down = v + w;
            int right = v + 1;

            ll x = (i == c && j == w - 1);
            ll y = (i == h - 1 && j == d);

            if (i + 1 < h) {
                x += toC[down];
                y += toD[down];
            }

            if (j + 1 < w) {
                x += toC[right];
                y += toD[right];
            }

            toC[v] = x % mod;
            toD[v] = y % mod;

            if (i + 1 < h && j + 1 < w) {
                int t = 1LL * toC[right] * toD[down] % mod;

                t -= 1LL * toC[down] * toD[right] % mod;

                if (t < 0) t += mod;

                ans = (ans + 1LL * dp[v] * t) % mod;
            }
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}