Buongiorno, sto provando a risolvere il problema “cameradeisegreti”, ma a parte l’ovvio algoritmo di complessità N^2 non mi viene in mente altro. Tra i tag c’è un “divide et impera”, ma in qualsiasi ordine si svolge il prodotto delle somme bisogna sempre fare N^2 prodotti. Ho provato a scomporlo con dei polinomi x vedere se succede qualcosa di interessante, ma nulla che possa accelerare l’algoritmo. Idee?
il problema sembrerebbe richiedere algoritmi di moltiplicazione veloce come karatsuba o o schonage per scomposizione intendi uno di questi metodi?
Questo è probabilmente il più difficile esercizio della piattaforma, ma se vuoi ancora provarci, sia \ p(x)=\prod_{i=0}^{N-1} (x+R_i), puoi facilmente verificare che il risultato è \ \prod_{i=0}^{N-1} p(B_i) e come vedi bastano N moltiplicazioni 
1 Mi Piace
Ciao scusa per l’ignoranza, sono abbastanza nuovo, ma ho provato a trasformare in codice quello che hai scritto e mi esce comunque una soluzione quadratica, quindi che va fuori tempo.
Il codice è questo
int p(int x, vi& r) {
ll res = 1;
for(int i = 0; i < r.size(); i++)
res = (res * (x + r[i])) % mod;
return (int)res;
}
int solve(int n, vi r, vi b) {
ll res = 1;
for(int i = 0; i < n; i++)
res = (res * p(b[i], r)) % mod;
return (int)res;
}
Non è esattamente quello che ho scritto, devi prima calcolare p(x).