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"> 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>