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

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