h1. 'Solutia':jc2023/solutii/omida problemei 'Omida Mincinoasa':problema/omidamincinoasa

h1. 'Soluţia':jc2023/solutii/jupanul problemei 'Salutare Jupâne':problema/jupanul

Pentru inceput, observam ca $C(n,i)·i^k^$ inseamna de fapt sa alegem un subsir de lungime $i$ a multimii ${1,2,3,...,n}$, si dupa aceea sa alegem o tupla de lungime $k$ din subsirul respectiv. In acest fel, numaram toate perechile de tipul $(subsir,tupla)$, dar acest lucru este echivalent cu a numara perechi de tipul $(tupla, subsir)$. Observam in continuare ca pentru a alege un subsir care acopera o tupla de valori depinde doar de numarul de valori distincte $x$ din tupla, iar numarul de moduri sa alegem subsirul este $2^n-x^$. Astfel daca vom gasi un mod prin care sa calculam numarul de tuple cu $x$ valori distincte, am rezolvat problema.

Vom încerca să tratăm suma independent pe fiecare prefix al descompunerii. Astfel, vom fixa prefixul de lungime $t$ şi vom calcula suma din gcd(a{1}, a{2}, ..., a{t}) pentru toate descompunerile lui $n$.

h2. Subtask 6: k ≤ 500

h2. Solutie in $O(m·nrdiv·log)$

Putem folosi urmatoarea dinamica pentru a numara tuple: $dp[i][j] = numarul de tuple de lungime i care contin toate valorile din [1,j]$. Ca recurenta, sa spunem ca tupla noastra contine $k > 1$ valori egale cu $j$, atunci $dp[i][j] += dp[i-k][j-1]·C(i,k)$.

Este cunoscut că suma din $phi(i)$ pentru toţi divizorii lui $n$ este chiar $n$, unde $phi(i)$ reprezintă numărul de numere prime cu $i$ mai mici decât $i$. Astfel, în loc să calculăm suma din gcd, vom calcula suma din $phi(x)$ cu $x | gcd$.

Prin urmare, am rezolvat acest subtask in $O(k^3^)$.

Să fixăm $x$ şi să numărăm câte descompuneri ale lui $n$ au $k$ termeni şi prefixul de lungime $t$ are gcd-ul multiplu de $x$. Singura condiţie impusă este că primii $t$ termeni din descompunere să fie multipli de $x$, deci trebuie să numărăm descompunerile lui $n/x^t$ în $k$ termeni, lucru care poate fi făcut cu uşurinţă considerând fiecare factor prim independent şi înmulţind răspunsurile. Dacă un factor prim are exponent $e$, atunci avem nevoie de numărul de soluţii ale $b{1} + b{2} + ... + b{k} = e$, deci vom folosi "stars and bars":https://cp-algorithms.com/combinatorics/stars_and_bars.html.

O implementare bazata pe aceasta idee poate fi vazuta "aici":https://www.infoarena.ro/job_detail/3147762?action=view-source.

Pentru a obţine complexitatea din subtitlu, folosim memoizare pentru a nu calcula descompunerile de mai multe ori decât este necesar şi observăm că pentru orice $x > 1$, acesta poate contribui doar în $log$ prefixe.

h2. Subtask 7: k ≤ 5000

h2. Solutie in $O(m·log^2^)$

Observam ca dinamica de mai sus numara functii surjective definite pe ${1,2,3,...,k}$ cu valori in ${1,2,3,...,j}$. Numararea acestor functii este un lucru cunoscut, o putem face prin diverse metode, solutia oficiala se foloseste de "numere Stirling de speta a 2-a":https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind, cu o complexitate finala de $O(maxk^2^ + t·k)$.
 
O implementare bazata pe aceasta idee poate fi vazuta "aici":https://www.infoarena.ro/job_detail/3147763?action=view-source.

Vom schimba modul în care calculăm răspunsul pentru un prefix. Să presupunem că $n=p{~1~}^e{~1~}^·p{~2~}^e{~2~}^·...·p{~l~}^e{~l~}^$. Vom folosi $dp[i] = suma tuturor gcd-urilor considerând doar primii i factori primi$. Observăm că $dp[i] = dp[i-1]·(suma tuturor gcd-urilor când considerăm doar factorul prim curent)$, întrucât orice $gcd$ care poate fi obţinut doar cu factorul prim curent poate fi cuplat cu orice $gcd$ vechi, deci în final doar înmulţim răspunsurile pentru fiecare factor prim separat. Acum putem folosi soluţia de dinainte, doar că nu mai trebuie să considerăm toţi divizorii, ci doar cei care sunt puteri ale unui număr prim, în total $log$ astfel de numere.