Editing 3828 - D Caesar Queries

==Cerința==
După ce Julius Caesar l-a învins pe Pompey în bătălia de la Pharsalus , acesta decide să țină un festin în cinstea soldaților săi loilai . El are q scenarii posibile pt oaspeți definite printr o pereche (n,k) care înseamnă că fiecare dintre cei n invitați pot alege unul dintre cele k feluri de mâncare . Deoarece Julius Caesar a plătit cei mai buni bucătari pentru a prepara mancarea , el își dorește ca fiecare fel de mâncare să fi fost ales de minimum un invitat. O configurație este un șir de n numere a , al i-lea soldat a ales felul a(i) . Câte configurații distincte există care să îndeplinească cerințele marelui Julius Caesar ? Două șiruri sunt distincte dacă diferă prin cel puțin o poziție.

==Date de intrare==
Fișierul de intrare caesar.in conține pe prima linie un număr q care reprezintă numărul de scenarii la care trebuie să răspundeți urmate de q linii , pe fiecare aflându-se o pereche (n , k) reprezentatnd numărul de invitați , respectiv numărul de feluri de mâncare disponibile.

==Date de ieșire==
Fișierul de ieșire caesar.out conține pe q linii răspunsul pentru fiecare scenariu modulo 666013.

==Restricții și precizări==
Q <= 100.000 , N <= 2000 K <= 2000 pentru orice query.
Pentru 20 puncte  Q = 1.
Pentru alte 20 de puncte  N , K <= 200.
Exemplu:
caesar.in

1
2 2
caesar.out

2
caesar.in

1
5 4
caesar.out

240
==Explicație==
În primul exemplu , dacă notăm cu 1 primul fel de mâncare și cu 2 al doilea fel de mâncare , atunci configurațiile bune sunt : 12 și 21 ( primul soldat poate alege ori primul ori al doilea fel de mâncare , iar al doilea alege felul de mâncare pe care nu l-a ales primul soldat pentru că toate felurile de mâncare să fie alese de cel puțin un soldat )
==Rezolvare==
<syntaxhighlight lang="python3" line="1">
MOD = 666013

def numar_configuratii(n, k):

   total_aranjamente = pow(k, n, MOD)
   aranjamente_fara_un_fel = pow(k-1, n, MOD)
   rezultat = (total_aranjamente - aranjamente_fara_un_fel) % MOD
   return rezultat

if __name__ == "__main__":

   # Citim numărul de scenarii
   q = int(input())
   # Pentru fiecare scenariu, citim valorile și calculăm rezultatul
   for _ in range(q):
       n, k = map(int, input().split())
       rezultat = numar_configuratii(n, k)
       print(rezultat)

python caesar.py
</syntaxhighlight>