Nu aveti permisiuni pentru a descarca fisierul grader_test7.in
Diferente pentru warm-up-2019/solutii/shoturi intre reviziile #81 si #80
Nu exista diferente intre titluri.
Diferente intre continut:
@3*dp[i-1][j-3]+2*dp[i-1][j-2]+1*dp[i-1][j-1]@| Se observă că, inmulţind $suma_de_suma$ cu <tex>hazard[i]</tex>, obţinem rezlultatul pentru $dp[i][j]$.
Cum $suma$ şi $suma_de_suma$ sunt calculate in timpul parcurgerii cu $j$, complexitatea este <tex>O(N*K)</tex>.
**Cod c++**
==code(cpp)|
dp[1][0]=1;
for(i=1; i<=k; i++)
dp[1][i]=(1LL*i*hazard[1])%MOD;
for(i=2; i<=n; i++)
{
dp[i][0]=1;
suma=1;
suma_de_suma=1;
for(j=1; j<=k; j++)
{
dp[i][j]+=(1LL*suma_de_suma*hazard[i]+dp[i-1][j])%MOD;
suma=(suma+dp[i-1][j])%MOD;
suma_de_suma=(suma_de_suma+suma)%MOD;
}
}
==
Cum $suma$ şi $suma_de_suma$ sunt calculate in timpul parcurgerii cu $j$, complexitatea este <tex>O(N*K)</tex>.
