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

h1. 'Solutia':jc2023/solutii/omida problemei 'Salutare Jupane':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 incerca sa tratam suma independent pe fiecare prefix al descompunerii. Astfel vom fixa prefixul de lungime $t$ si 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 ca suma din $phi(i)$ pentru toti divizorii lui $n$ este chiar $n$, unde $phi(i)$ reprezinta numarul de numere prime cu $i$ mai mici decat $i$. Astfel in loc sa calculam suma din gcd, vom calcula suma din $phi(x)$ cu $x | gcd$.

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

Sa fixam $x$, si sa numaram cate descompuneri ale lui $n$ au $k$ termeni si prefixul de lungime $t$ are gcdul multiplu de $x$. Putem face acest lucru pur si simplu numarand descompunerile lui $n/x^t^$ in $k$ termeni, lucru care poate fi facut cu usurinta considerand fiecare factor prim independent si inmultind raspunsurile. Daca un factor prim are exponent $e$, atunci avem nevoie de numarul de solutii 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 obtine complexitatea din subtitlu, folosim memoizare pentru a nu calcula descompunerile de mai multe ori decat este necesar si observam ca pentru orice $x > 1$, acesta poate contribui doar in $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 in care calculam raspunsul pentru un prefix. Sa presupunem ca $n=p{~1~}^e{~1~}^·p{~2~}^e{~2~}^·...·p{~l~}^e{~l~}^$. Vom folosi $dp[i] = suma tututor gcdurilor considerand doar primii i factori primi$. Observam ca $dp[i] = dp[i-1]·(suma tuturor gcdurilor cand consideram doar factorul prim curent)$, intrucat pentru orice $gcd$ care poate fi obtinut doar cu factorul prim curent, acesta poate fi cuplat cu orice $gcd$ vechi, deci in final doar inmultim raspunsurile pentru fiecare factor prim separat. Acum putem folosi solutia de dinainte, doar ca nu mai trebuie sa consideram toti divizorii, ci doar cei care sunt puteri ale unui numar prim, in total $log$ astfel de numere.