Für Anfänger von Wettkampfprofis. Atcoder, an dem ich neulich teilgenommen habe, hat gelernt, wie man den Umfang der DP-Berechnung reduziert, und war sehr beeindruckt, also habe ich mir eine Notiz gemacht.
Es gibt Quadrate, die aus N in einer Reihe angeordneten Quadraten bestehen, und die Quadrate sind in der Reihenfolge von links mit 1, 2,…, N nummeriert. Herr Takahashi, der auf diesem Platz lebt, befindet sich derzeit auf Platz 1 und versucht, auf Platz N zu gelangen, indem er die Bewegung nach der später beschriebenen Methode wiederholt. Eine ganze Zahl K von 10 oder weniger und K Intervalle [L1, R1], [L2, R2],…, [LK, RK], die keinen gemeinsamen Teil haben Ist gegeben, und sei S die Summe dieser Intervalle. Das Intervall [l, r] repräsentiert jedoch eine Menge von ganzen Zahlen, die größer oder gleich l und kleiner oder gleich r sind.
--Wenn Sie in Zelle i eine Ganzzahl aus S auswählen (sagen wir d) und gehen Sie zu Zelle i + d. Bewegen Sie sich jedoch nicht außerhalb des Platzes.
Teilen Sie für Takahashi den Rest der Division der Anzahl der Wege zur Messe N durch 998244353.
Auf den ersten Blick scheint es mit dem folgenden einfachen DP gelöst zu werden! Es sieht so aus.
dp [i]: Anzahl der Bewegungsmöglichkeiten, um Position i zu erreichen
dp[i] = \sum_{s \in S}dp[i-s]
In diesem Fall erfordert die Anzahl der Aktualisierungen (N) x die Anzahl der Elemente (N) der dp-Tabelle jedoch den Rechenaufwand von N ^ 2 und kann nicht mit einem TLE-Fehler übergeben werden.
Unter Hinweis darauf, dass das Element von S als Abschnitt angegeben ist und dass die Abschnitte keinen gemeinsamen Teil haben, Die Bewegung in dem Abschnitt [Li, Ri] wird als die Summe bestimmter Abschnitte in der DP betrachtet. Beispiel: Für das Intervall [1, 5] ist dp [i] = dp [i-1] + dp [i-2] + ... + dp [i-5] Auf diese Weise kann die DP-Tabelle wie folgt umgeschrieben werden.
dp[i] = \sum_{lr \in S}\sum_{j \in [l,r]}(dp[i-j])
(Ein Abschnitt in lr: S enthalten)
Wenn Sie versuchen, die Summe der Intervalle in der Beschleunigung ① zu finden, ist der Berechnungsbetrag N, sodass der Berechnungsbetrag insgesamt N ^ 2 bleibt. Daher wird unter Verwendung des Konzepts der kumulativen Summe die Berechnung der Intervallsumme beschleunigt.
Die kumulative Summe ist die Summe der Werte vom ersten Element zu einem bestimmten Element in einer Sequenz. Mit der kumulierten Summe können Sie die Intervallsumme in der Zahlenspalte wie folgt berechnen.
(Summe der Intervalle von i bis j der Sequenz L) = ([Kumulative Summe bis j] - [Kumulative Summe bis i])
Mit dieser Methode kann jede beliebige Summe von Intervallen in einer festen Zeit berechnet werden, und der Gesamtbetrag der Berechnung kann auf NK unterdrückt werden. DP drückt die kumulative Summe in sdp wie folgt aus.
dp[i] = \sum_{lr \in S}(sdp[i-lr[r] - sdp[i-lr[l])
Es ist eine Implementierung von Python. Der Anfangswert von dp (dp [0]) ist 1, da dies die Anzahl der Wege ist, um zum ersten Platz zu gelangen.
N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]
mod = 998244353
S = []
for k in range(K):
for i in range(LR[k][0], LR[k][1] + 1):
S.append(i)
dp = [0] * N #dp Tabelle
sdp = [0] * (N+1) #
#Stellen Sie den Anfangswert von DP ein
dp[0] = 1
sdp[1] = 1
for n in range(1, N):
for lr in LR:
left = max(0, n - lr[1])
right = max(0, n - lr[0] + 1)
dp[n] += sdp[right] - sdp[left]
dp[n] %= mod
sdp[n+1] = (sdp[n] + dp[n]) % mod
res = dp[N-1]
print(res)
Es war eine gute Frage, zwei Konzepte zu lernen: DP-Berechnung mit Intervallen und Beschleunigung mit kumulativer Summe. Wenn es um das D-Problem geht, können Sie nicht nur einen einfachen DP implementieren, sondern auch den Rechenaufwand kennen.
Recommended Posts