Pour les débutants des professionnels de la compétition. Atcoder, qui a participé l'autre jour, a appris à réduire la quantité de calcul DP et a été très impressionné, alors j'ai pris une note.
Il y a des carrés constitués de N carrés alignés dans une ligne, et les carrés sont numérotés 1, 2,…, N dans l'ordre à partir de la gauche. M. Takahashi, qui habite sur cette place, se trouve actuellement sur la case 1 et tente de se rendre sur la case N en répétant le mouvement par la méthode décrite plus loin. Un entier K de 10 ou moins et K intervalles [L1, R1], [L2, R2],…, [LK, RK] qui n'ont pas de partie commune Est donnée, et soit S l'ensemble de la somme de ces intervalles. Cependant, l'intervalle [l, r] représente un ensemble d'entiers supérieurs ou égaux à l et inférieurs ou égaux à r.
--Lorsque dans la cellule i, sélectionnez un entier dans S (disons d) et passez à la cellule i + d. Cependant, ne vous déplacez pas en dehors du carré.
Pour Takahashi, trouvez le reste de la division du nombre de façons d'aller à la messe N par 998244353.
À première vue, il semble être résolu avec le simple DP suivant! Ça ressemble à ça.
dp [i]: nombre de façons de se déplacer pour atteindre la position i
dp[i] = \sum_{s \in S}dp[i-s]
Cependant, dans ce cas, le nombre de mises à jour (N) x le nombre d'éléments (N) de la table dp nécessite la quantité de calcul de N ^ 2, et il ne peut pas être passé avec une erreur TLE.
Notant que l'élément de S est donné sous forme de section et que les sections n'ont pas de partie commune, Le mouvement dans la section [Li, Ri] est considéré comme la somme de certaines sections du DP. Exemple: pour l'intervalle [1, 5], dp [i] = dp [i-1] + dp [i-2] + ... + dp [i-5] En utilisant cela, la table DP peut être réécrite comme suit.
dp[i] = \sum_{lr \in S}\sum_{j \in [l,r]}(dp[i-j])
(Une section incluse dans lr: S)
Si vous essayez de trouver la somme des intervalles dans l'accélération ①, le montant du calcul est N, donc le montant du calcul reste N ^ 2 dans son ensemble. Par conséquent, en utilisant le concept de somme cumulative, le calcul de la somme d'intervalle est accéléré.
La somme cumulée est la somme des valeurs du premier élément à un élément spécifique d'une séquence. En utilisant la somme cumulée, vous pouvez calculer la somme des intervalles sur la colonne numérique comme suit.
(Somme des intervalles de i à j de la séquence L) = ([Somme cumulée jusqu'à j] - [Somme cumulée jusqu'à i])
Avec cette méthode, toute somme d'intervalles peut être calculée dans un temps fixe, et la quantité totale de calcul peut être supprimée à NK. Exprimant la somme cumulée en sdp, DP est le suivant.
dp[i] = \sum_{lr \in S}(sdp[i-lr[r] - sdp[i-lr[l])
C'est une implémentation par python. La valeur initiale de dp (dp [0]) est 1 car c'est le nombre de façons d'arriver à la première place.
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 #table dp
sdp = [0] * (N+1) #Somme cumulée des tables dp
#Réglez la valeur initiale de DP
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)
C'était une bonne question d'apprendre deux concepts: le calcul DP à l'aide d'intervalles et l'accélération à l'aide de la somme cumulée. En ce qui concerne le problème D, non seulement vous pouvez implémenter un DP simple, mais vous devez également être conscient de la quantité de calcul.
Recommended Posts