Take all lattice points on the boundary of an \(N\times N\) square and list them in cyclic order. These points form a polygon with
$$m=4N$$
vertices. The problem asks for the number of maximal non-crossing cut systems allowed by the square-cutting rules, with the final result reported modulo \(10^8\).
The code explicitly builds the boundary in clockwise order:
1. bottom side from \((0,0)\) to \((N,0)\),
2. right side from \((N,1)\) to \((N,N)\),
3. top side from \((N-1,N)\) to \((0,N)\),
4. left side from \((0,N-1)\) to \((0,1)\).
This gives exactly \(4N\) distinct boundary lattice points. Joining consecutive points in that cyclic order produces a simple polygon.
Two vertices may always be connected if they are adjacent on the polygon boundary. Those are just polygon edges.
For non-adjacent vertices, the code uses a geometric rule:
1. if both endpoints lie on the same side of the square and are not adjacent, the chord is forbidden,
2. otherwise the chord is allowed.
So a long segment sliding along one square side is illegal, while a segment connecting different square sides is legal.
Once all legal cuts are viewed as non-crossing chords of the boundary polygon, a maximal family of such chords decomposes the polygon into faces. If any face had more than three sides, one more non-crossing legal chord could still be inserted inside that face, contradicting maximality.
Therefore every maximal non-crossing admissible cut system is exactly a triangulation of the boundary polygon using only allowed diagonals.
This is the key reduction: the original cutting problem becomes a polygon-triangulation count with a forbidden-diagonal mask.
Let \(dp[i][j]\) be the number of valid triangulations of the chain of vertices
$$v_i,v_{i+1},\dots,v_j,$$
where indices are taken in the linear order of the opened polygon. If the closing edge \((i,j)\) is forbidden, then
$$dp[i][j]=0.$$
Otherwise we choose the third vertex \(k\) of the triangle adjacent to edge \((i,j)\). This splits the region into two smaller subpolygons, giving
$$dp[i][j]=\sum_{k=i+1}^{j-1} dp[i][k]\;dp[k][j]\pmod{10^8}.$$
This is the standard Catalan-style triangulation recurrence, except that forbidden diagonals force many subproblems to be zero.
If \(j=i+1\), the chain contains only one polygon edge and no area to triangulate, so
$$dp[i][i+1]=1.$$
This is the neutral multiplicative base that makes the recurrence work for larger intervals.
The program contains four exact checks:
$$C(1)=2,\qquad C(2)=30,\qquad C(3)=604,\qquad C(4)=12168.$$
The case \(N=1\) is especially instructive. The boundary polygon is just a square, and both diagonals connect different square sides, so both are allowed. A square has exactly two triangulations, which explains \(C(1)=2\).
The larger values \(30,604,12168\) verify that the admissibility mask and the interval DP agree with the intended geometry for nontrivial boundary sizes.
The DP is filled by interval length. When computing all states with fixed length \(\ell=j-i\), every transition only reads states of smaller lengths. Therefore two states of the same length never depend on one another.
This is why the code can split all intervals of a fixed length across multiple threads without race conditions on the mathematical data dependency graph.
build_boundary(n) creates the \(4N\) polygon vertices.
same_side(a,b,n) checks whether two vertices lie on the same physical side of the square. Using that, the code fills an allowed matrix for every pair of vertices.
count_triangulations(n, threads) runs the interval DP modulo
$$M=10^8.$$
It computes short intervals first, then longer ones, and finally returns dp[0][m-1], the number of admissible triangulations of the full polygon.
The command-line interface supports -n N, -t THREADS, and --no-validate.
There are \(O(m^2)\) intervals with \(m=4N\), and each interval tries \(O(m)\) split points, so the runtime is
$$O(m^3)=O(N^3).$$
The DP table and admissibility matrix each use \(O(m^2)=O(N^2)\) memory.
Die Gitterpunkte auf dem Rand eines \(N\times N\)-Quadrats werden zyklisch angeordnet. Dadurch entsteht ein Polygon mit
$$m=4N$$
Ecken. Gesucht ist die Anzahl maximaler nichtschneidender zulässiger Schnitte, modulo \(10^8\).
Der Code erzeugt die Randpunkte im Uhrzeigersinn. Insgesamt entstehen genau \(4N\) verschiedene Punkte, also ein einfaches Polygon.
Nachbarpunkte auf dem Polygonrand sind immer erlaubt. Für nichtadjazente Punkte gilt:
1. liegen beide auf derselben Quadratseite, ist die Verbindung verboten,
2. liegen sie auf verschiedenen Quadratseiten, ist die Verbindung erlaubt.
Ein maximales System nichtschneidender zulässiger Sehnen zerlegt das Randpolygon in Flächen. Hätte eine Fläche mehr als drei Seiten, könnte man darin noch eine weitere zulässige nichtschneidende Sehne einziehen. Das widerspricht der Maximalität.
Also entspricht jedes maximale Schnittsystem genau einer Triangulierung mit erlaubten Diagonalen.
Sei \(dp[i][j]\) die Anzahl zulässiger Triangulierungen der Kette \(v_i,\dots,v_j\). Ist die abschließende Kante \((i,j)\) verboten, dann ist
$$dp[i][j]=0.$$
Sonst wählt man den dritten Eckpunkt \(k\) des an \((i,j)\) angrenzenden Dreiecks und erhält
$$dp[i][j]=\sum_{k=i+1}^{j-1}dp[i][k]\,dp[k][j]\pmod{10^8}.$$
Für \(j=i+1\) gibt es keinen Innenraum zu triangulieren, daher
$$dp[i][i+1]=1.$$
Der Code validiert
$$C(1)=2,\qquad C(2)=30,\qquad C(3)=604,\qquad C(4)=12168.$$
Bei \(N=1\) ist das Randpolygon ein Quadrat. Beide Diagonalen verbinden verschiedene Quadratseiten und sind deshalb erlaubt; ein Quadrat hat genau zwei Triangulierungen.
Die DP wird nach Intervalllänge aufgebaut. Zustände gleicher Länge lesen nur kürzere Intervalle und hängen daher nicht voneinander ab. Genau deshalb können Intervalle gleicher Länge sicher auf Threads verteilt werden.
build_boundary(n) erzeugt die \(4N\) Eckpunkte. same_side erkennt, ob zwei Punkte auf derselben Quadratseite liegen. Damit wird die Matrix allowed aufgebaut.
count_triangulations berechnet die Intervall-DP modulo
$$M=10^8$$
und liefert am Ende dp[0][m-1].
Die Kommandozeile unterstützt -n N, -t THREADS und --no-validate.
Mit \(m=4N\) gibt es \(O(m^2)\) Intervalle und pro Intervall \(O(m)\) mögliche Trennpunkte. Daher ist die Laufzeit \(O(m^3)=O(N^3)\), der Speicher \(O(m^2)=O(N^2)\).
\(N\times N\) karenin sınırındaki kafes noktaları çevresel sırayla yazıldığında
$$m=4N$$
köşeli bir çokgen elde edilir. Problem, izin verilen kesme kuralları altında oluşan maksimal, kesişmeyen kesim sistemlerinin sayısını \(10^8\) modunda istemektedir.
Kod sınır noktalarını saat yönünde üretir: alt kenar, sağ kenar, üst kenar, sol kenar. Böylece tam olarak \(4N\) farklı sınır noktası oluşur ve bunlar basit bir çokgen verir.
Çokgenin komşu köşeleri arasındaki kenarlar her zaman izinlidir. Komşu olmayan iki nokta için kural şudur:
1. iki uç aynı kare kenarı üzerinde ise bağlantı yasaktır,
2. iki uç farklı kare kenarlarında ise bağlantı serbesttir.
Yani aynı kare kenarı üzerinde uzanan uzun “kesmeler” yapılamaz; gerçek iç kesmeler farklı kenarları bağlamalıdır.
İzinli ve kesişmeyen her kesim, sınır çokgeninin bir kirişidir. Böyle kirişlerin maksimal bir kümesi çokgeni alt yüzlere böler. Eğer bu yüzlerden biri üçgenden büyük olsaydı, o yüzün içine bir kiriş daha eklenebilirdi; bu da maksimal olma durumuna aykırıdır.
Dolayısıyla problem, yasak köşegen maskeli bir çokgen üçgenleme sayımına indirgenir.
\(dp[i][j]\), \(v_i,\dots,v_j\) zincirinin geçerli üçgenleme sayısı olsun. Eğer \((i,j)\) kapanış kenarı yasaksa
$$dp[i][j]=0$$
olur. Aksi halde, \((i,j)\) kenarına komşu üçgenin üçüncü köşesi \(k\) seçilerek
$$dp[i][j]=\sum_{k=i+1}^{j-1} dp[i][k]\;dp[k][j]\pmod{10^8}$$
bağıntısı elde edilir. Bu, Catalan tipindeki standart çokgen üçgenleme bağıntısıdır; fark, bazı köşegenlerin en baştan yasak olmasıdır.
\(j=i+1\) olduğunda içeride üçgenlenecek bir alan yoktur, bu yüzden
$$dp[i][i+1]=1$$
alınır.
Program şu dört değeri kontrol eder:
$$C(1)=2,\qquad C(2)=30,\qquad C(3)=604,\qquad C(4)=12168.$$
\(N=1\) durumu özellikle öğreticidir. Bu durumda sınır çokgeni bir kareden ibarettir ve iki köşegenin ikisi de farklı kare kenarlarını bağladığı için izinlidir. Bir karenin tam iki üçgenlemesi vardır; bu da \(C(1)=2\)'yi açıklar.
DP, aralık uzunluğuna göre doldurulur. Sabit bir uzunluktaki tüm durumlar yalnızca daha kısa aralıklara bakar; aynı uzunluktaki başka bir duruma bağımlılık yoktur. Bu yüzden aynı uzunluk katmanındaki aralıklar thread'lere güvenle dağıtılabilir.
build_boundary(n) ile \(4N\) köşe üretilir. same_side iki noktanın karenin aynı kenarında olup olmadığını test eder. Bu bilgiyle allowed matrisi doldurulur.
count_triangulations aralık DP'sini
$$M=10^8$$
modunda hesaplar ve sonunda tüm çokgen için sonucu veren dp[0][m-1] değerini döndürür.
Komut satırı seçenekleri: -n N, -t THREADS, --no-validate.
\(m=4N\) için \(O(m^2)\) aralık vardır ve her aralıkta \(O(m)\) bölme noktası denenir. Toplam süre \(O(m^3)=O(N^3)\), bellek kullanımı \(O(m^2)=O(N^2)\) olur.
Los puntos de la frontera de un cuadrado \(N\times N\), listados en orden cíclico, forman un polígono con
$$m=4N$$
vértices. Se pide contar los sistemas máximos de cortes no cruzados permitidos por la geometría del problema, módulo \(10^8\).
El código recorre la frontera en sentido horario y obtiene exactamente \(4N\) puntos distintos. Al unir consecutivos se obtiene un polígono simple.
Los lados del polígono siempre se permiten. Para vértices no adyacentes:
1. si ambos están en el mismo lado del cuadrado, la cuerda está prohibida,
2. si están en lados distintos, la cuerda está permitida.
Un conjunto maximal de cuerdas admisibles y no cruzadas divide el polígono en caras. Si alguna cara tuviera más de tres lados, todavía se podría añadir otra cuerda no cruzada dentro de ella. Eso contradice la maximalidad.
Por tanto, el problema se reduce a contar triangulaciones del polígono con una máscara de diagonales prohibidas.
Sea \(dp[i][j]\) el número de triangulaciones válidas de la cadena \(v_i,\dots,v_j\). Si la arista de cierre \((i,j)\) está prohibida, entonces
$$dp[i][j]=0.$$
Si está permitida, elegimos el tercer vértice \(k\) del triángulo adyacente a \((i,j)\) y obtenemos
$$dp[i][j]=\sum_{k=i+1}^{j-1}dp[i][k]\,dp[k][j]\pmod{10^8}.$$
Cuando \(j=i+1\), no hay área interior que triangular, así que
$$dp[i][i+1]=1.$$
El programa comprueba
$$C(1)=2,\qquad C(2)=30,\qquad C(3)=604,\qquad C(4)=12168.$$
El caso \(N=1\) es el más claro: el polígono es un cuadrado, ambas diagonales conectan lados distintos del cuadrado y por tanto son válidas; un cuadrado tiene exactamente dos triangulaciones.
La DP se rellena por longitud de intervalo. Todas las transiciones de una longitud fija solo leen intervalos más cortos. Por eso los estados de la misma longitud pueden repartirse entre hilos sin dependencia matemática entre ellos.
build_boundary construye los \(4N\) vértices. same_side decide si dos puntos están en el mismo lado físico del cuadrado, y con ello se llena la matriz allowed.
count_triangulations ejecuta la DP módulo
$$M=10^8$$
y devuelve dp[0][m-1].
La interfaz admite -n N, -t THREADS y --no-validate.
Con \(m=4N\), hay \(O(m^2)\) intervalos y \(O(m)\) puntos de división por intervalo. El tiempo total es \(O(m^3)=O(N^3)\) y la memoria \(O(m^2)=O(N^2)\).
把 \(N\times N\) 正方形边界上的格点按循环顺序列出来，会得到一个有
$$m=4N$$
个顶点的多边形。题目要求统计所有满足规则的“最大不相交切割系统”的数量，并对 \(10^8\) 取模。
代码按顺时针顺序走完四条边，得到恰好 \(4N\) 个不同的边界点，把相邻点连起来后就得到一个简单多边形。
多边形的边总是允许。对不相邻顶点：
1. 若两点位于正方形的同一条边上，则这条弦被禁止，
2. 若两点位于不同边上，则这条弦允许。
把所有合法切割看成边界多边形中的不相交弦后，一个极大的合法弦集合会把多边形分成若干面。若其中某一面有超过三条边，那么还可以在这面内部再加入一条不相交合法弦，这与“极大”矛盾。
因此，每个最大不相交切割系统都恰好对应于一个只使用允许对角线的三角剖分。
设 \(dp[i][j]\) 表示链 \(v_i,\dots,v_j\) 的合法三角剖分数量。若闭合边 \((i,j)\) 本身不允许，则
$$dp[i][j]=0.$$
若允许，则选择与边 \((i,j)\) 相邻三角形的第三个顶点 \(k\)，递推式为
$$dp[i][j]=\sum_{k=i+1}^{j-1}dp[i][k]\;dp[k][j]\pmod{10^8}.$$
当 \(j=i+1\) 时，链内部没有面积需要继续剖分，所以
$$dp[i][i+1]=1.$$
程序内置了四个精确检查：
$$C(1)=2,\qquad C(2)=30,\qquad C(3)=604,\qquad C(4)=12168.$$
\(N=1\) 最直观：此时边界多边形就是一个正方形，两条对角线都连接不同的方形边，因此都允许；而正方形恰有两种三角剖分。
DP 按区间长度递增填表。固定长度的一层只会读取更短区间的结果，因此同一层内的状态彼此没有依赖关系。这正是代码可以把同长度区间分配给多个线程的原因。
build_boundary 构造 \(4N\) 个顶点。same_side 用来判断两个点是否在正方形的同一物理边上，并据此填充 allowed 矩阵。
count_triangulations 在
$$M=10^8$$
模下运行区间 DP，并返回 dp[0][m-1]。
命令行选项包括 -n N、-t THREADS 和 --no-validate。
当 \(m=4N\) 时，有 \(O(m^2)\) 个区间，每个区间尝试 \(O(m)\) 个分割点，因此总时间为 \(O(m^3)=O(N^3)\)，空间为 \(O(m^2)=O(N^2)\)。
Граничные узлы квадрата \(N\times N\), перечисленные по кругу, образуют многоугольник с
$$m=4N$$
вершинами. Требуется посчитать число максимальных непересекающихся допустимых разрезов по модулю \(10^8\).
Код проходит по четырём сторонам квадрата по часовой стрелке и получает ровно \(4N\) различных граничных точек. Последовательное соединение этих точек даёт простой многоугольник.
Рёбра многоугольника допустимы всегда. Для не соседних вершин действует правило:
1. если обе точки лежат на одной стороне квадрата, хорда запрещена,
2. если точки лежат на разных сторонах, хорда разрешена.
Максимальное множество допустимых непересекающихся хорд разбивает многоугольник на грани. Если бы какая-то грань имела больше трёх сторон, внутрь неё можно было бы провести ещё одну допустимую хорду. Это противоречит максимальности.
Значит, задача сводится к подсчёту триангуляций многоугольника с маской запрещённых диагоналей.
Пусть \(dp[i][j]\) обозначает число допустимых триангуляций цепочки \(v_i,\dots,v_j\). Если замыкающая хорда \((i,j)\) запрещена, то
$$dp[i][j]=0.$$
Иначе выбирается третий вершина \(k\) треугольника, прилегающего к \((i,j)\), и получается
$$dp[i][j]=\sum_{k=i+1}^{j-1}dp[i][k]\,dp[k][j]\pmod{10^8}.$$
При \(j=i+1\) внутренней области нет, поэтому
$$dp[i][i+1]=1.$$
Программа проверяет
$$C(1)=2,\qquad C(2)=30,\qquad C(3)=604,\qquad C(4)=12168.$$
Случай \(N=1\) особенно прост: многоугольник есть квадрат, обе его диагонали соединяют разные стороны квадрата и потому допустимы. У квадрата ровно две триангуляции.
Таблица DP заполняется по длине интервала. Состояния фиксированной длины читают только более короткие интервалы, поэтому между ними нет зависимостей. Именно поэтому интервалы одной длины можно безопасно раздавать разным потокам.
build_boundary строит \(4N\) вершин. same_side определяет, лежат ли две точки на одной физической стороне квадрата. На основе этого заполняется матрица allowed.
count_triangulations выполняет интервальный DP по модулю
$$M=10^8$$
и в конце возвращает dp[0][m-1].
Поддерживаются параметры -n N, -t THREADS и --no-validate.
При \(m=4N\) существует \(O(m^2)\) интервалов, и для каждого перебирается \(O(m)\) точек разреза. Итого время \(O(m^3)=O(N^3)\), память \(O(m^2)=O(N^2)\).
إذا رتبنا نقاط الشبكة على حدود مربع \(N\times N\) ترتيبًا دائريًا، حصلنا على مضلع له
$$m=4N$$
رؤوس. المطلوب هو عدّ جميع أنظمة القطع المسموحة غير المتقاطعة التي تكون عظمى، ثم أخذ الناتج بتعديل \(10^8\).
يمر الكود على أضلاع المربع الأربعة بترتيب دائري ويولد بالضبط \(4N\) نقاط حدية مختلفة. وصل هذه النقاط بالتتابع يعطي مضلعًا بسيطًا.
أضلاع المضلع مسموحة دائمًا. أما بين رأسين غير متجاورين فالقانون هو:
1. إذا كانا على الضلع نفسه من أضلاع المربع فالوصل ممنوع،
2. إذا كانا على ضلعين مختلفين فالوصل مسموح.
إذا أخذنا مجموعة عظمى من الأوتار المسموحة غير المتقاطعة، فإنها تقسم المضلع إلى مناطق. ولو كانت إحدى هذه المناطق ذات أكثر من ثلاثة أضلاع، لأمكن إدخال وتر إضافي غير متقاطع داخلها. وهذا يناقض العظمى.
إذن المسألة تكافئ عدّ تثليثات المضلع مع وجود قناع للأقطار الممنوعة.
لتكن \(dp[i][j]\) عدد التثليثات المسموحة للسلسلة \(v_i,\dots,v_j\). إذا كان الوتر \((i,j)\) ممنوعًا، فإن
$$dp[i][j]=0.$$
أما إذا كان مسموحًا، فنختار الرأس الثالث \(k\) للمثلث الملاصق للضلع \((i,j)\)، فنحصل على
$$dp[i][j]=\sum_{k=i+1}^{j-1}dp[i][k]\,dp[k][j]\pmod{10^8}.$$
عندما \(j=i+1\) لا توجد مساحة داخلية تحتاج إلى تثليث، لذا
$$dp[i][i+1]=1.$$
يتحقق البرنامج من القيم
$$C(1)=2,\qquad C(2)=30,\qquad C(3)=604,\qquad C(4)=12168.$$
في حالة \(N=1\) يكون المضلع مجرد مربع، وكلا قطريه يصل بين ضلعين مختلفين من أضلاع المربع، ولذلك كلاهما مسموح. والمربع له تثليثان بالضبط.
تملأ DP حسب طول الفاصل. الحالات ذات الطول نفسه تعتمد فقط على فواصل أقصر، ولا تعتمد على بعضها بعضًا. لهذا يمكن توزيع فواصل الطول الواحد على عدة خيوط تنفيذ بأمان.
build_boundary يبني الرؤوس \(4N\). وتحدد الدالة same_side ما إذا كانت نقطتان تقعان على الضلع الفيزيائي نفسه من المربع. وبناءً على ذلك تُملأ مصفوفة allowed.
count_triangulations يشغل DP على الفواصل بتعديل
$$M=10^8$$
ويعيد في النهاية القيمة dp[0][m-1].
تدعم الواجهة الوسائط -n N و-t THREADS و--no-validate.
عندما \(m=4N\)، يوجد \(O(m^2)\) فاصلًا، ولكل فاصل \(O(m)\) نقاط فصل ممكنة. لذا يكون الزمن \(O(m^3)=O(N^3)\)، والذاكرة \(O(m^2)=O(N^2)\).