On an \(n\times n\) board, exactly one square is blocked in every row and exactly one square is blocked in every column. So every board is determined by a permutation \(p\in S_n\), where the blocked square in row \(i\) lies in column \(p_i\). A position is called open if there exists a path from the top-left square to the bottom-right square using only right and down moves and never stepping on a blocked square.
If \(f(n)\) denotes the number of open boards, the task is to compute \(f(10^8)\) modulo \(1008691207\). The important point is that the implementations do not search for paths on the huge board. They use an exact combinatorial identity that reduces the whole problem to factorials and a prefix sum of factorials.
Let \(f(n)\) be the number of open permutation boards of size \(n\). Since every placement is a permutation, there are \(n!\) total configurations. The mathematical job is therefore to understand which permutations force every monotone path to fail.
Choose a permutation \(p=(p_1,\dots,p_n)\). The blocked cells are then
$$ (1,p_1),(2,p_2),\dots,(n,p_n). $$
Because the blocked columns are all distinct, the board is a permutation matrix of forbidden cells. This observation removes the need to think about arbitrary obstacle patterns. The geometry is rigid enough that the counting problem can be translated into a combinatorial question about permutations.
A monotone path uses only right and down moves, so only the relative order of the blocked cells matters. That is the reason a closed formula exists at all.
It is more convenient to think about closed boards, where every monotone path is blocked. Those closed boards can be organized by the depth of the first effective barrier that separates the reachable northwest region from the unreachable southeast region.
The simplest closed families occur near the corners: the starting square may already be blocked, the ending square may already be blocked, or a very shallow corner barrier may immediately cut off all progress. After those easy cases, the remaining closed boards are indexed by an interior barrier depth. Once that depth is fixed, the leftover rows and columns can be permuted freely, which is why factorial terms dominate the final answer.
The C++, Python, and Java implementations all evaluate the same exact identity:
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)\sum_{k=0}^{n-4} k! \qquad (n\ge 3), $$
together with
$$ f(n)=0 \qquad (n\le 2). $$
The large negative factorial terms remove the dominant closed families. The constant correction \(2\) and the tail term \((n-3)\sum_{k=0}^{n-4}k!\) add back the configurations that were removed too often when the barrier families overlap. For the actual computation, this identity is the whole story: once it is known, there is no need to inspect individual paths.
Define the factorial prefix sum
$$ S_m=\sum_{k=0}^{m} k!. $$
Then the formula becomes
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)S_{n-4}\pmod{1008691207}. $$
So the entire computation consists of two tasks:
$$ \text{compute } S_{n-4}, \qquad \text{and compute } (n-3)!, (n-2)!, (n-1)!, n! \pmod{1008691207}. $$
This is exactly why the implementations can stay linear and use constant extra memory.
For \(n=5\), the prefix sum is
$$ S_1=0!+1!=1+1=2. $$
Substituting into the exact identity gives
$$ \begin{aligned} f(5) &=5!-2\cdot 4!-3!-2!+2+2(0!+1!) \\ &=120-48-6-2+2+4 \\ &=70. \end{aligned} $$
This matches the standard small checkpoint. The same formula also gives \(f(3)=2\), which is the smallest nontrivial open case.
The implementations treat the problem as pure modular arithmetic. They first handle the small base case \(n\le 2\), where the answer is \(0\). For \(n\ge 3\), they maintain one running factorial and one running sum of factorials.
The first pass accumulates
$$ 0!+1!+\cdots+(n-4)! \pmod{1008691207}. $$
Then the same running factorial is continued through the last four multiplications so that the implementation obtains \((n-3)!\), \((n-2)!\), \((n-1)!\), and \(n!\) modulo the given prime. Those values are substituted directly into the closed formula, and the result is normalized back into the standard modular range.
The C++ implementation also performs a small brute-force verification for tiny \(n\): it enumerates permutations, checks path existence with a grid dynamic program, and confirms that the formula matches exact counting before evaluating the large target.
The running time is \(O(n)\) modular multiplications, because the algorithm makes one forward pass from \(1\) up to \(n\). The extra memory usage is \(O(1)\), since only a few integers are stored for the current factorial, the factorial prefix sum, and the final expression. That scaling is exactly what makes \(n=10^8\) practical.
Auf einem \(n\times n\)-Brett ist in jeder Zeile genau ein Feld blockiert und in jeder Spalte ebenfalls genau ein Feld. Deshalb wird jede Stellung durch eine Permutation \(p\in S_n\) beschrieben: In Zeile \(i\) liegt das blockierte Feld in Spalte \(p_i\). Eine Stellung heißt offen, wenn es einen Weg vom linken oberen zum rechten unteren Feld gibt, der nur nach rechts oder unten geht und nie ein blockiertes Feld betritt.
Mit \(f(n)\) bezeichnen wir die Anzahl solcher offenen Stellungen. Gesucht ist \(f(10^8)\) modulo \(1008691207\). Die Implementierungen durchsuchen das riesige Brett nicht direkt, sondern verwenden eine exakte kombinatorische Identität, die alles auf Fakultäten und eine Fakultätssumme reduziert.
Es gibt insgesamt \(n!\) Permutationsstellungen. Also muss man mathematisch nur verstehen, welche Permutationen jeden monotonen Weg sicher zerstören.
Wähle eine Permutation \(p=(p_1,\dots,p_n)\). Dann sind die blockierten Felder
$$ (1,p_1),(2,p_2),\dots,(n,p_n). $$
Da alle Spaltenwerte verschieden sind, ist das blockierte Muster genau eine Permutationsmatrix verbotener Felder. Dadurch hat das Problem viel mehr Struktur als ein allgemeines Hindernisproblem auf einem Gitter.
Weil ein zulässiger Weg nur rechts und unten gehen darf, ist nicht die konkrete Geometrie jedes einzelnen Feldes entscheidend, sondern die relative Lage dieser blockierten Zellen. Genau deshalb kann die Zählung in eine reine Permutationsformel umgeschrieben werden.
Statt offene Bretter direkt zu konstruieren, ist es bequemer, die geschlossenen Bretter zu klassifizieren. Dort verhindert eine Barriere jedes monotone Erreichen der rechten unteren Ecke. Diese geschlossenen Fälle lassen sich nach der Tiefe der ersten wirksamen Barriere ordnen.
Die einfachsten Familien entstehen an den Ecken: Das Startfeld kann blockiert sein, das Zielfeld kann blockiert sein, oder eine sehr flache Eckbarriere schneidet den Weg sofort ab. Wenn diese Randfälle abgezogen sind, bleiben innere Barrieren übrig, deren Beitrag nur noch davon abhängt, wie viele Zeilen und Spalten danach frei permutiert werden können. Darum treten in der Endformel fast nur Fakultäten auf.
Alle drei Implementierungen werten dieselbe exakte Formel aus:
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)\sum_{k=0}^{n-4} k! \qquad (n\ge 3), $$
zusammen mit
$$ f(n)=0 \qquad (n\le 2). $$
Die großen negativen Fakultätsterme entfernen die dominierenden geschlossenen Familien. Die Korrektur \(2\) und der Summand \((n-3)\sum_{k=0}^{n-4}k!\) addieren genau die Konfigurationen wieder hinzu, die wegen überlappender Barrierefamilien zu oft subtrahiert wurden. Für das Programm ist diese Formel bereits die gesamte Mathematik.
Definiere
$$ S_m=\sum_{k=0}^{m} k!. $$
Dann lautet die Berechnung schlicht
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)S_{n-4}\pmod{1008691207}. $$
Man braucht also nur
$$ S_{n-4},\quad (n-3)!,\quad (n-2)!,\quad (n-1)!,\quad n! $$
modulo \(1008691207\). Damit verschwindet jede Notwendigkeit für eine Pfadsuche auf dem eigentlichen Brett.
Hier ist
$$ S_1=0!+1!=1+1=2. $$
Eingesetzt in die Formel ergibt das
$$ \begin{aligned} f(5) &=5!-2\cdot 4!-3!-2!+2+2(0!+1!) \\ &=120-48-6-2+2+4 \\ &=70. \end{aligned} $$
Das ist genau der bekannte Kontrollwert. Ebenso liefert die Formel \(f(3)=2\).
Die Implementierungen behandeln das Problem als reine Modulo-Arithmetik. Zunächst wird der Basisfall \(n\le 2\) abgefangen. Für größere \(n\) wird eine laufende Fakultät aufgebaut und parallel die Summe
$$ 0!+1!+\cdots+(n-4)! \pmod{1008691207} $$
akkumuliert. Danach wird dieselbe laufende Fakultät noch bis \(n\) weitergeführt, damit \((n-3)!\), \((n-2)!\), \((n-1)!\) und \(n!\) verfügbar sind.
Am Ende setzt die Implementierung diese Werte direkt in die geschlossene Formel ein und normalisiert das Resultat in den Standardbereich des Moduls. Die C++-Variante enthält zusätzlich einen Brute-Force-Test für kleine \(n\), bei dem alle Permutationen durchlaufen und per Gitter-DP geprüft werden.
Die Laufzeit beträgt \(O(n)\), weil genau ein linearer Vorwärtsdurchlauf benötigt wird. Der Zusatzspeicher ist \(O(1)\), da nur wenige Ganzzahlen für die laufende Fakultät, die Fakultätssumme und den Endausdruck gehalten werden. Darum ist sogar \(n=10^8\) noch praktikabel.
\(n\times n\) tahtada her satırda tam bir engelli kare ve her sütunda da tam bir engelli kare vardır. Bu nedenle her tahta, \(p\in S_n\) permütasyonu ile temsil edilir; satır \(i\) için engelli kare sütun \(p_i\) olur. Eğer sol üstten sağ alta sadece sağ ve aşağı hareketleriyle, engelli karelere basmadan bir yol bulunabiliyorsa konum açık sayılır.
\(f(n)\), açık konumların sayısı olsun. Amaç \(f(10^8)\) değerini \(1008691207\) modunda bulmaktır. Buradaki kritik fikir, büyük tahtada yol aramamak; bunun yerine problemi tam bir kombinatorik formüle indirgemektir.
Toplam yerleşim sayısı \(n!\) olduğundan, gerçek matematiksel iş hangi permütasyonların her monoton yolu zorunlu olarak kapattığını anlamaktır.
Bir \(p=(p_1,\dots,p_n)\) permütasyonu seçelim. O zaman engelli kareler
$$ (1,p_1),(2,p_2),\dots,(n,p_n) $$
olur. Sütunlar tekrarlanmadığı için bu desen, yasak karelerden oluşan bir permütasyon matrisi gibidir.
Yol yalnızca sağa ve aşağı gidebildiğinden, problem genel bir engel araması olmaktan çıkar ve engellerin göreli sıralanışını sayma problemine dönüşür. Bu da kapalı formülün neden var olabildiğini açıklar.
Doğrudan açık tahtaları saymak yerine, kapalı tahtaları düşünmek daha kolaydır. Kapalı bir tahtada, sol üstte erişilebilen bölge ile sağ alttaki bölge arasında etkili bir bariyer oluşur. Bu kapalı durumlar, ilk etkili bariyerin ne kadar sığ veya derin olduğuna göre sınıflandırılabilir.
En kolay kapalı aileler köşe kaynaklıdır: başlangıç karesi engellenmiş olabilir, bitiş karesi engellenmiş olabilir ya da çok sığ bir köşe bariyeri hemen her yolu kesebilir. Daha derin iç bariyerlerde ise katkı yalnızca bariyer sabitlendikten sonra serbest kalan satır ve sütun sayısına bağlı olur. Bu nedenle son formülde faktöriyel terimler baskındır.
C++, Python ve Java uygulamalarının hepsi aynı tam kimliği hesaplar:
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)\sum_{k=0}^{n-4} k! \qquad (n\ge 3), $$
ve ayrıca
$$ f(n)=0 \qquad (n\le 2). $$
Büyük negatif faktöriyel terimler baskın kapalı aileleri çıkarır. \(2\) sabiti ile \((n-3)\sum_{k=0}^{n-4}k!\) düzeltmesi ise, bariyer aileleri birbiriyle örtüştüğünde fazla eksiltilen durumları geri ekler. Gerçek hesaplama için gereken bütün matematik budur.
Bu noktada uzun toplamı tek bir sembolle toplamak yeterlidir; böylece kapalı formül doğrudan uygulanabilir hale gelir ve hesaplamanın hangi ara değerlere indirgendiği açıkça görülür.
$$ S_m=\sum_{k=0}^{m} k! $$
tanımını yapalım. O zaman
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)S_{n-4}\pmod{1008691207}. $$
Dolayısıyla yapılacak iş sadece şunları bulmaktır:
$$ S_{n-4},\quad (n-3)!,\quad (n-2)!,\quad (n-1)!,\quad n! \pmod{1008691207}. $$
Böylece büyük tahtada hiçbir yol araması veya permütasyon taraması gerekmez.
Bu durumda
$$ S_1=0!+1!=1+1=2. $$
Formüle yerleştirirsek
$$ \begin{aligned} f(5) &=5!-2\cdot 4!-3!-2!+2+2(0!+1!) \\ &=120-48-6-2+2+4 \\ &=70. \end{aligned} $$
Bu, küçük ölçekte bilinen kontrol değeridir. Aynı formül \(f(3)=2\) sonucunu da verir.
Uygulamalar problemi tamamen modüler aritmetik olarak ele alır. Önce \(n\le 2\) durumu için doğrudan \(0\) döndürülür. Daha büyük \(n\) için bir akan faktöriyel değeri tutulur ve aynı anda
$$ 0!+1!+\cdots+(n-4)! \pmod{1008691207} $$
toplanır. Ardından aynı faktöriyel zinciri birkaç adım daha ilerletilerek \((n-3)!\), \((n-2)!\), \((n-1)!\) ve \(n!\) mod değerleri elde edilir.
Son aşamada bu değerler kapalı formüle yerleştirilir ve sonuç standart mod aralığına normalize edilir. C++ uygulaması ayrıca küçük \(n\) değerlerinde tüm permütasyonları deneyip ızgara DP'si ile yol varlığını test eden ek bir brute-force doğrulaması da yapar.
Algoritma \(1\) ile \(n\) arasında tek bir ileri geçiş yaptığı için zaman karmaşıklığı \(O(n)\)'dir. Ek bellek ihtiyacı \(O(1)\)'dir; yalnızca birkaç tamsayı tutulur. Bu ölçeklenme sayesinde \(n=10^8\) gibi bir değer pratik olarak hesaplanabilir.
En un tablero \(n\times n\), hay exactamente una casilla bloqueada en cada fila y exactamente una casilla bloqueada en cada columna. Por eso cada tablero queda determinado por una permutación \(p\in S_n\): en la fila \(i\), la casilla bloqueada está en la columna \(p_i\). Una posición es abierta si existe un camino desde la esquina superior izquierda hasta la inferior derecha usando solo movimientos a la derecha y hacia abajo, sin pisar ninguna casilla bloqueada.
Si \(f(n)\) es el número de tableros abiertos, hay que calcular \(f(10^8)\) módulo \(1008691207\). La idea clave es que las implementaciones no buscan caminos en el tablero gigante: usan una identidad combinatoria exacta que reduce todo a factoriales y a una suma prefija de factoriales.
Como el número total de configuraciones es \(n!\), el verdadero problema matemático consiste en describir qué permutaciones fuerzan el fracaso de todo camino monótono.
Sea \(p=(p_1,\dots,p_n)\). Entonces las casillas bloqueadas son
$$ (1,p_1),(2,p_2),\dots,(n,p_n). $$
Como las columnas bloqueadas son todas distintas, el patrón de obstáculos es una matriz de permutación de celdas prohibidas. Eso da mucha rigidez estructural al problema.
Un camino admisible solo puede moverse a la derecha o hacia abajo. Por lo tanto, lo esencial no es una exploración geométrica completa del tablero, sino el orden relativo de esas celdas bloqueadas. Esa es la razón por la que aparece una fórmula cerrada.
Resulta más natural clasificar los tableros cerrados, es decir, aquellos donde toda ruta monótona queda destruida. Esos tableros se pueden ordenar según la profundidad de la primera barrera efectiva que separa la región alcanzable del noroeste de la región inaccesible del sudeste.
Las familias cerradas más simples aparecen cerca de las esquinas: la casilla inicial puede estar bloqueada, la casilla final puede estar bloqueada, o puede surgir muy pronto una barrera de esquina. Después de esas familias dominantes, las barreras internas restantes se indexan por una profundidad. Fijada esa profundidad, las filas y columnas sobrantes pueden permutarse libremente, y por eso los factoriales dominan la respuesta final.
Las implementaciones en C++, Python y Java evalúan exactamente la misma identidad:
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)\sum_{k=0}^{n-4} k! \qquad (n\ge 3), $$
junto con
$$ f(n)=0 \qquad (n\le 2). $$
Los grandes términos factoriales negativos eliminan las familias cerradas principales. La corrección \(2\) y el término \((n-3)\sum_{k=0}^{n-4}k!\) vuelven a sumar los casos que habían sido restados demasiadas veces cuando varias familias de barrera se superponen. Una vez conocida esta identidad, no hace falta inspeccionar caminos individuales.
Definimos
$$ S_m=\sum_{k=0}^{m} k!. $$
Entonces la expresión queda
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)S_{n-4}\pmod{1008691207}. $$
Por tanto, basta calcular
$$ S_{n-4},\quad (n-3)!,\quad (n-2)!,\quad (n-1)!,\quad n! \pmod{1008691207}. $$
Esa es exactamente la reducción que aprovecha la implementación: nada de enumerar permutaciones grandes ni de hacer DP sobre el tablero real.
En este caso
$$ S_1=0!+1!=1+1=2. $$
Sustituyendo en la identidad exacta se obtiene
$$ \begin{aligned} f(5) &=5!-2\cdot 4!-3!-2!+2+2(0!+1!) \\ &=120-48-6-2+2+4 \\ &=70. \end{aligned} $$
Ese valor coincide con el punto de comprobación pequeño. La misma fórmula también da \(f(3)=2\).
Las implementaciones trabajan enteramente con aritmética modular. Primero resuelven el caso base \(n\le 2\), donde la respuesta es \(0\). Para \(n\ge 3\), mantienen un factorial acumulado y una suma acumulada de factoriales.
En la primera fase se calcula
$$ 0!+1!+\cdots+(n-4)! \pmod{1008691207}. $$
Luego se prolonga el mismo factorial acumulado unas pocas multiplicaciones más para disponer de \((n-3)!\), \((n-2)!\), \((n-1)!\) y \(n!\) módulo el primo dado. Con esos valores se evalúa la expresión cerrada y se normaliza el resultado final.
La versión en C++ además incluye una verificación por fuerza bruta para \(n\) pequeño: enumera todas las permutaciones, comprueba la existencia del camino con una programación dinámica sobre la cuadrícula y confirma que la fórmula coincide con el conteo exacto.
El tiempo es \(O(n)\), porque solo se hace un recorrido lineal desde \(1\) hasta \(n\). La memoria extra es \(O(1)\), ya que solo se guardan unas pocas variables enteras para el factorial actual, la suma prefija y la fórmula final. Ese coste es precisamente lo que hace viable el caso \(n=10^8\).
在一个 \(n\times n\) 的棋盘上，每一行恰好有一个被封锁的格子，每一列也恰好有一个被封锁的格子。因此，整个棋盘可以由一个排列 \(p\in S_n\) 完全描述：第 \(i\) 行被封锁的位置在第 \(p_i\) 列。若存在一条从左上角走到右下角的路径，并且这条路径只允许向右或向下移动，同时从不经过被封锁的格子，那么这个局面就称为 开放。
记开放局面的数量为 \(f(n)\)。题目要求计算 \(f(10^8)\bmod 1008691207\)。真正关键的地方在于，程序并不会在如此巨大的棋盘上做路径搜索；它使用的是一个精确的组合恒等式，把问题完全化成若干阶乘和一个阶乘前缀和。
由于每个合法障碍布局都对应一个排列，所以总局面数就是 \(n!\)。因此，数学上的核心问题并不是“如何在棋盘上找路”，而是“哪些排列会强制所有单调路径都失败”。
取一个排列 \(p=(p_1,\dots,p_n)\)。那么被封锁的格子正是
$$ (1,p_1),(2,p_2),\dots,(n,p_n). $$
因为每一列只出现一次，所以这些障碍点构成了一张排列矩阵。这样一来，问题就不再是一般性的“带障碍网格搜索”，而是一个结构非常规整的排列计数问题。
又因为允许的路径只能向右或向下，所以真正重要的是这些障碍点的相对顺序，而不是整个 \(n^2\) 个格子的逐格搜索。这正是本题能够出现闭式公式的根本原因。
直接构造开放局面并不方便。更容易处理的是 封闭 局面，也就是所有单调路径都被挡住的局面。对这类局面，可以按照“第一道真正起作用的屏障有多深”来分类。
最容易描述的封闭情形发生在角落附近：起点本身可能被封锁，终点本身可能被封锁，或者在很浅的位置就出现了把可达区域切断的角落屏障。把这些显而易见的家族剥离之后，剩下的是由内部屏障深度控制的局面。一旦屏障深度固定，剩余的行和列就可以自由排列，所以最终答案自然会以阶乘项为主。
C++、Python 和 Java 三个实现都计算同一个精确公式：
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)\sum_{k=0}^{n-4} k! \qquad (n\ge 3), $$
并且还有边界情形
$$ f(n)=0 \qquad (n\le 2). $$
其中，前面的几个大负号阶乘项负责扣除最主要的封闭家族；常数修正 \(2\) 与尾项 \((n-3)\sum_{k=0}^{n-4}k!\) 则把那些因为多个屏障家族重叠而被多减的局面重新加回来。对实际程序而言，只要接受这条恒等式，后面的工作就全部是模运算，不再需要逐个判断路径。
定义
$$ S_m=\sum_{k=0}^{m} k!. $$
于是对于 \(n\ge 3\)，可以把公式写成
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)S_{n-4}\pmod{1008691207}. $$
这说明整个问题只剩下以下几个量：
$$ S_{n-4},\quad (n-3)!,\quad (n-2)!,\quad (n-1)!,\quad n! \pmod{1008691207}. $$
一旦这些量算出来，答案就能直接代入得到。换句话说，真正的大规模输入并不需要做棋盘动态规划，更不需要枚举排列。
当 \(n=5\) 时，有
$$ S_1=0!+1!=1+1=2. $$
代入闭式可得
$$ \begin{aligned} f(5) &=5!-2\cdot 4!-3!-2!+2+2(0!+1!) \\ &=120-48-6-2+2+4 \\ &=70. \end{aligned} $$
这正好得到已知的小规模校验值。类似地，这个公式还会给出 \(f(3)=2\)，也就是最小的非平凡开放情形。
三个实现都把问题当成纯粹的模算术问题来做。首先处理 \(n\le 2\) 的边界情形，此时答案直接为 \(0\)。对更大的 \(n\)，程序维护一个“当前阶乘”和一个“阶乘前缀和”。
第一阶段累计
$$ 0!+1!+\cdots+(n-4)! \pmod{1008691207}. $$
随后，继续沿用同一个运行中的阶乘值，再往后乘几步，依次得到 \((n-3)!\)、\((n-2)!\)、\((n-1)!\) 和 \(n!\) 在模 \(1008691207\) 下的值。最后把这些量直接代入闭式，必要时再把结果标准化到非负模区间。
C++ 实现还额外包含一个小规模暴力校验：它会枚举很小的排列规模，用网格动态规划判断路径是否存在，并验证闭式结果与精确计数完全一致，然后才计算大目标。
时间复杂度是 \(O(n)\)，因为算法只是从 \(1\) 到 \(n\) 做一次线性前进。额外空间复杂度是 \(O(1)\)，因为只保存了当前阶乘、阶乘和以及最终表达式所需的少量整数。正因为复杂度如此紧凑，\(n=10^8\) 才具有可计算性。
На доске \(n\times n\) в каждой строке заблокирована ровно одна клетка, и в каждом столбце тоже заблокирована ровно одна клетка. Поэтому любая позиция однозначно задается перестановкой \(p\in S_n\): в строке \(i\) запрещенная клетка стоит в столбце \(p_i\). Позиция называется открытой, если существует путь из левого верхнего угла в правый нижний, который идет только вправо и вниз и не проходит через заблокированные клетки.
Пусть \(f(n)\) обозначает число открытых позиций. Нужно вычислить \(f(10^8)\) по модулю \(1008691207\). Важная идея состоит в том, что реализации не ищут путь на гигантской доске напрямую. Вместо этого используется точная комбинаторная формула, сводящая задачу к факториалам и одной префиксной сумме факториалов.
Так как общее число допустимых расстановок равно \(n!\), математическая часть задачи состоит в том, чтобы понять, какие именно перестановки гарантированно уничтожают любой монотонный путь.
Выбираем перестановку \(p=(p_1,\dots,p_n)\). Тогда заблокированные клетки имеют вид
$$ (1,p_1),(2,p_2),\dots,(n,p_n). $$
Поскольку номера столбцов не повторяются, мы получаем матрицу перестановки из запрещенных клеток. Благодаря этой жесткой структуре задача сильно упрощается по сравнению с произвольным набором препятствий.
Разрешенный путь может идти только вправо и вниз, поэтому существенно не абсолютное положение всех \(n^2\) клеток, а относительный порядок заблокированных позиций. Именно поэтому здесь вообще возникает замкнутая формула.
Удобнее классифицировать не открытые, а закрытые позиции, в которых любой монотонный путь невозможен. Такие позиции естественно группировать по глубине первого эффективного барьера, отделяющего достижимую северо-западную область от недостижимой юго-восточной.
Самые простые закрытые семьи возникают около углов: стартовая клетка может быть заблокирована, конечная клетка может быть заблокирована, либо очень неглубокий угловой барьер сразу перекрывает продвижение. После выделения этих случаев оставшиеся внутренние барьеры нумеруются глубиной. Когда глубина зафиксирована, оставшиеся строки и столбцы можно переставлять свободно, и именно поэтому в ответе доминируют факториалы.
Все три реализации вычисляют одну и ту же точную формулу:
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)\sum_{k=0}^{n-4} k! \qquad (n\ge 3), $$
а также
$$ f(n)=0 \qquad (n\le 2). $$
Крупные отрицательные факториальные слагаемые удаляют основные закрытые семьи. Поправка \(2\) и хвостовой член \((n-3)\sum_{k=0}^{n-4}k!\) возвращают те конфигурации, которые были вычтены слишком много раз из-за перекрытия нескольких барьерных семейств. Для программы это и есть вся нужная математика: после этой формулы остается только модульная арифметика.
Обозначим
$$ S_m=\sum_{k=0}^{m} k!. $$
Тогда для \(n\ge 3\) имеем
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)S_{n-4}\pmod{1008691207}. $$
Следовательно, задача сводится к вычислению величин
$$ S_{n-4},\quad (n-3)!,\quad (n-2)!,\quad (n-1)!,\quad n! \pmod{1008691207}. $$
После этого ответ получается подстановкой в готовую формулу. Ни динамического программирования по большой доске, ни перебора перестановок в реальном случае не требуется.
Здесь
$$ S_1=0!+1!=1+1=2. $$
Подставляем в формулу:
$$ \begin{aligned} f(5) &=5!-2\cdot 4!-3!-2!+2+2(0!+1!) \\ &=120-48-6-2+2+4 \\ &=70. \end{aligned} $$
Получается известная контрольная величина. Та же формула дает \(f(3)=2\), то есть первый нетривиальный случай.
Реализации рассматривают задачу как чистую модульную арифметику. Сначала обрабатывается малый базовый случай \(n\le 2\), где ответ равен нулю. Для больших \(n\) поддерживаются текущий факториал и текущая сумма факториалов.
На первом этапе накапливается
$$ 0!+1!+\cdots+(n-4)! \pmod{1008691207}. $$
Затем тот же текущий факториал продолжается еще на несколько шагов, чтобы получить \((n-3)!\), \((n-2)!\), \((n-1)!\) и \(n!\) по модулю. После этого выражение из закрытой формулы собирается напрямую, а результат нормализуется в стандартный диапазон остатков.
В реализации на C++ также есть небольшая brute-force-проверка: для маленьких \(n\) перебираются все перестановки, существование пути проверяется обычной динамикой по сетке, и тем самым подтверждается совпадение формулы с точным подсчетом.
Время работы равно \(O(n)\), потому что требуется один линейный проход от \(1\) до \(n\). Дополнительная память равна \(O(1)\), так как хранятся только несколько целых значений для текущего факториала, суммы и итогового выражения. Именно такая компактность делает случай \(n=10^8\) вычислимым.
على لوحة \(n\times n\)، توجد خانة محجوبة واحدة بالضبط في كل صف وخانة محجوبة واحدة بالضبط في كل عمود. لذلك يمكن تمثيل كل وضعية بترتيب \(p\in S_n\)، بحيث تكون الخانة المحجوبة في الصف \(i\) عند العمود \(p_i\). تسمى الوضعية مفتوحة إذا وُجد مسار من الزاوية العلوية اليسرى إلى الزاوية السفلية اليمنى يستخدم فقط الحركات إلى اليمين وإلى الأسفل ولا يمر عبر أي خانة محجوبة.
إذا رمزنا بعدد الوضعيات المفتوحة بـ \(f(n)\)، فالمطلوب هو حساب \(f(10^8)\) بترديد \(1008691207\). الفكرة الأساسية هي أن التنفيذ لا يبحث عن المسار على اللوحة العملاقة مباشرة، بل يعتمد على متطابقة توافقية دقيقة تختزل المسألة إلى مضروبات عددية ومجموع تراكمي للمضروبات.
بما أن عدد جميع الترتيبات الممكنة يساوي \(n!\)، فإن المهمة الرياضية الحقيقية هي فهم أي التبديلات تجعل كل مسار أحادي الاتجاه مستحيلاً.
لنأخذ ترتيبًا \(p=(p_1,\dots,p_n)\). عندئذ تكون الخانات المحجوبة هي
$$ (1,p_1),(2,p_2),\dots,(n,p_n). $$
ولأن الأعمدة المحجوبة جميعها مختلفة، فإن نمط العوائق يشكل مصفوفة تبديل من الخانات الممنوعة. هذا يمنح المسألة بنية قوية جدًا مقارنة بمسألة عوائق عامة على شبكة.
وبما أن المسار المسموح لا يتحرك إلا إلى اليمين أو إلى الأسفل، فإن المهم هو الترتيب النسبي لهذه الخانات المحجوبة، لا فحص جميع خلايا اللوحة واحدة واحدة. لهذا السبب تظهر صيغة مغلقة في الحل.
من الأسهل تصنيف الوضعيات المغلقة، أي التي تمنع كل مسار أحادي الاتجاه. يمكن تنظيم هذه الوضعيات بحسب عمق أول حاجز فعّال يفصل المنطقة الممكن الوصول إليها في الركن الشمالي الغربي عن المنطقة غير الممكن الوصول إليها في الجنوب الشرقي.
أبسط العائلات المغلقة تظهر قرب الزوايا: قد تكون خانة البداية نفسها محجوبة، أو خانة النهاية محجوبة، أو قد يظهر حاجز زاوي ضحل يقطع التقدم مبكرًا جدًا. بعد التخلص من هذه العائلات الأساسية، تبقى حواجز داخلية تُفهرس بعمقها. وما إن يثبت هذا العمق حتى يمكن ترتيب الصفوف والأعمدة المتبقية بحرية، ولهذا تهيمن حدود المضروب على الصيغة النهائية.
تنفيذات C++ و Python و Java كلها تحسب المتطابقة نفسها تمامًا:
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)\sum_{k=0}^{n-4} k! \qquad (n\ge 3), $$
ومعها الحالة الحدية
$$ f(n)=0 \qquad (n\le 2). $$
الحدود العاملية السالبة الكبيرة تطرح العائلات المغلقة الرئيسية. أما التصحيح \(2\) والحد \((n-3)\sum_{k=0}^{n-4}k!\) فيضيفان من جديد الحالات التي طُرحت أكثر من مرة بسبب تداخل عائلات الحواجز. وبمجرد معرفة هذه المتطابقة، يتحول الحل كله إلى حسابات معيارية فقط.
نعرف
$$ S_m=\sum_{k=0}^{m} k!. $$
وعندئذ تصبح الصيغة
$$ f(n)=n!-2(n-1)!-(n-2)!-(n-3)!+2+(n-3)S_{n-4}\pmod{1008691207}. $$
إذن المطلوب حساب
$$ S_{n-4},\quad (n-3)!,\quad (n-2)!,\quad (n-1)!,\quad n! \pmod{1008691207}. $$
بعد ذلك يمكن تعويض هذه القيم مباشرة في الصيغة المغلقة. لذلك لا حاجة في الإدخال الحقيقي إلى تعداد التبديلات أو إلى برمجة ديناميكية على اللوحة نفسها.
لدينا هنا
$$ S_1=0!+1!=1+1=2. $$
وبالتعويض نحصل على
$$ \begin{aligned} f(5) &=5!-2\cdot 4!-3!-2!+2+2(0!+1!) \\ &=120-48-6-2+2+4 \\ &=70. \end{aligned} $$
وهذه هي قيمة التحقق الصغيرة المعروفة. كما تعطي الصيغة أيضًا \(f(3)=2\)، وهو أصغر مثال غير بديهي لوضعية مفتوحة.
تتعامل التنفيذات مع المسألة على أنها حسابات معيارية خالصة. في البداية تُعالج الحالة \(n\le 2\) مباشرة لأن الجواب فيها هو \(0\). بعد ذلك يُحفَظ مضروب جارٍ ومجموع جارٍ للمضروبات.
في المرحلة الأولى يُحسب
$$ 0!+1!+\cdots+(n-4)! \pmod{1008691207}. $$
ثم يُتابَع المضروب نفسه عدة خطوات إضافية للحصول على \((n-3)!\) و\((n-2)!\) و\((n-1)!\) و\(n!\) تحت الترديد نفسه. وفي النهاية تُركَّب هذه القيم في الصيغة المغلقة ويُعاد تطبيع الناتج إلى المجال المعياري القياسي.
تتضمن نسخة C++ أيضًا فحصًا صغيرًا بالقوة الغاشمة: فهي تعد جميع التبديلات للأحجام الصغيرة، وتتحقق من وجود المسار ببرمجة ديناميكية على الشبكة، ثم تؤكد أن الصيغة المغلقة تطابق العد الدقيق قبل الانتقال إلى القيمة الكبيرة.
التعقيد الزمني هو \(O(n)\)، لأن الخوارزمية تحتاج إلى مرور خطي واحد من \(1\) حتى \(n\). أما الذاكرة الإضافية فهي \(O(1)\)، إذ لا تُخزَّن إلا بضعة أعداد صحيحة تمثل المضروب الحالي، والمجموع التراكمي، والتعبير النهائي. وهذا بالضبط ما يجعل الحالة \(n=10^8\) قابلة للحساب.