Perhatikan potongan program berikut:
A := 0
for i := C to D do
A :=(A+i) mod 5
output (A)Jika output yang muncul di layar adalah 3 dan nilai variabel C dan D hanya boleh berada di antara 0..255, ada berapa banyak kemungkinan pasangan nilai C dan D yang menghasilkan output tersebut?
A. 2
B. 5
C. 1326
D. 2652
E. 5253
karena mod 5, a dan c hanya bisa memiliki nilai 0,1,2,3,4.
Kita compute prefix sumnya
KITA BISA ambil dari range c ke d hanya jika pref[d]-pref[c]==3;
nah , kalo nilainya cuma 0,1,2,3,4 . prefix sum nya juga berulang ,cuma memiliki nilai 0,1,3,1,0 . ada sebanyak 51 pola berulang.
bagi kasus :
-saat pola ke 1 : 3 bisa dipasangkan dengan 0 pertama. =1
-saat pola ke 2 : 3 bisa dipasangkan dengan 3 0 pertama. =3
....
-saat pola ke 51 : 3 bisa dipasangkan dengan (51)*2-1 0 pertama = 101
jadi total ada 2601 ( HITUNG PAKE SN)
KASUS KEDUA yaitu jika pref[d]==pref[c]==3 , hal ini sudah memenuhi jadi ditambah lagi 51 .
=2601+51= 2652
Masuk untuk menulis jawaban