Herausforderung von Dwango Qualifying C --Kill / Death Um zu lösen, wird die Summe zu einem bestimmten Wert (positiv). Wir brauchten die Anzahl der Ganzzahlspalten und die Anzahl der eindeutigen Kombinationen davon. Beide können in einem zweidimensionalen Array mit $ O (nm) $ aufgelistet werden, wenn die Länge der Ganzzahlzeichenfolge $ n $ und die Summe $ m $ beträgt.
Als Beispiel● ● ● ●Kann zum Beispiel in drei Fächer unterteilt werden● ● | ● | ●Es kann ausgedrückt werden als.
Dies ist eine Frage, wo $ n-1 $ | bei $ m + n-1 $ platziert werden soll, und die Anzahl der Kombinationen beträgt $ _ {n-1 + m} C _ {n- Es wird mit 1} $ berechnet, und in diesem Beispiel gibt es $ _6 C _2 = 15 $.
4 0 0
3 0 1
3 1 0
2 0 2
2 1 1
2 2 0
1 0 3
1 1 2
1 2 1
1 3 0
0 0 4
0 1 3
0 2 2
0 3 1
0 4 0
Da die Berechnung von $ _n C _r $ abhängig von der Art und Weise, wie der Wert verwendet wird, einige Zeit in Anspruch nimmt, kann in einigen Fällen eine Beschleunigung durch Aufzählung der Anzahl ganzzahliger Zeichenfolgen erreicht werden. Hier wird die folgende allmähliche Gleichung verwendet. $ P (n, m) $ ist die Anzahl der ganzzahligen Spalten mit der Länge $ n $ und der Summe $ m $.
P(n,m)=
\begin{cases}
1 & (n,m=0)\\
P(n-1,m) & (m=0, 1 \leq n) \\
P(n-1,m)+P(n,m-1) & (1 \leq m, 1 \leq n) \\
0 & (otherwise)
\end{cases}
Die Anzahl der Ganzzahlspalten, deren Summe bis zum $ i $ -ten Element genau $ j $ beträgt, ist die Anzahl der Ganzzahlspalten, deren Summe beim $ i-1 $ -ten Element genau $ j $ beträgt (dh das $ i $ -te Element ist (Wenn $ 0 $) und die Anzahl der ganzzahligen Spalten, deren Summe genau $ j-1 $ bis zum $ i $ -ten Element ist. Es kann wie folgt implementiert werden.
P = []
cur = [0]*(m+1)
cur[0] = 1
for i in range(1, n+1):
for j in range(1, m+1):
cur[j] += cur[j-1]
P.append(cur.copy())
Aufzählung einer Ganzzahlzeichenfolge von $ P (2,4) $
4 0 0
#Bis hierher ist P.(1,4)
0 4 0
3 1 0
2 2 0
1 3 0
#Bis hierher ist P.(2,4)
Wenn Sie nun $ 1 $ von allen zweiten Elementen einer Ganzzahlzeichenfolge subtrahieren, deren Länge durch genau $ 2 $ dargestellt werden kann
0 3
3 0
2 1
1 2
Und wir erhalten eine ganzzahlige Zeichenfolge von $ P (2,3) $. Wenn Sie dagegen $ 1 $ zu allen zweiten Elementen von $ P (2,3) $ hinzufügen, beträgt das zweite Element $ 0 $ oder mehr, sodass die Summe, die durch genau $ 2 $ Länge dargestellt werden kann, $ 4 $ beträgt. Sie erhalten eine Ganzzahlzeichenfolge.
Ermitteln Sie die Anzahl der eindeutigen Kombinationen der zuvor aufgeführten Ganzzahlzeichenfolgen, wobei dieselben Kombinationen in unterschiedlicher Reihenfolge ausgeschlossen sind. $ C (n, m) $ ist eine Kombination von $ n $ ganzen Zahlen, die $ m $ ergibt und durch die folgende allmähliche Gleichung berechnet wird.
C(n,m)=
\begin{cases}
1 & (n,m=0)\\
C(n-1,m) & (m < n, 1 \leq n) \\
C(n-1,m)+C(n,m-n) & (n \leq m, 1 \leq n) \\
0 & (otherwise)
\end{cases}
Die Anzahl der ganzzahligen Spalten bis zum $ i $ -ten Element, dessen Summe genau $ j $ ist, ist die Anzahl der ganzzahligen Spalten, deren Summe genau $ j $ am $ i-1 $ -ten Element ist (dh das $ i $ -te Element ist (Wenn $ 0 $) und die Anzahl der ganzzahligen Spalten, deren Summe genau $ ji $ bis zum $ i $ -ten Element ist. Es kann wie folgt implementiert werden.
C = []
cur = [0]*(m+1)
cur[0] = 1
for i in range(1, n+1):
for j in range(i, m+1):
cur[j] += cur[j-i]
C.append(cur.copy())
Wenn Sie $ C (3,4) $ aufzählen,
4 0 0
#Bis hierher ist C.(1,4)
2 2 0
3 1 0
#Bis hierher ist C.(2,4)
2 1 1
#Bis hierher ist C.(3,4)
Wird sein. Übrigens, wenn Sie * verwenden, um eine Kombination von ganzen Zahlen darzustellen, deren Länge genau $ 2 $ und deren Summe $ 4 $ beträgt.
2 * *
2 * *
0
3 * * *
1 *
0
Wenn Sie dies transponieren und lesen
2 2
* *
* *
2 1 1
* * *
*
Daher kann eine Kombination von ganzen Zahlen mit einer Länge von genau $ 2 $ und einer Summe von $ 4 $ als eine Kombination von ganzen Zahlen beliebiger Länge mit einem Maximalwert von $ 2 $ und einer Summe von $ 4 $ gelesen werden. Hier ist zu sehen, dass die Kombination von ganzen Zahlen nach der Translokation immer mit $ 2 $ beginnt und danach durch die Kombination von ganzen Zahlen von $ C (2,4-2) = C (2,2) $ dargestellt werden kann.
Recommended Posts