# Cameradeisegreti

**URL:** <https://forum.olinfo.it/t/cameradeisegreti/6086>\
**Category:** Aiuto\
**Created:** [5 Marzo 2020, 8:34am UTC](https://forum.olinfo.it/t/cameradeisegreti/6086 "2020-03-05T08:34:17Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![AlessioZeni](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/e8c25b/32.png) [@AlessioZeni](https://forum.olinfo.it/u/AlessioZeni)\
**Post date:** [5 Marzo 2020, 8:34am UTC](https://forum.olinfo.it/t/cameradeisegreti/6086/1 "2020-03-05T08:34:17Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![porcelli](https://forum.olinfo.it/user_avatar/forum.olinfo.it/porcelli/32/668_2.png) [@porcelli](https://forum.olinfo.it/u/porcelli)\
**Post date:** [5 Marzo 2020, 10:48am UTC](https://forum.olinfo.it/t/cameradeisegreti/6086/2 "2020-03-05T10:48:31Z")

</div>

il problema sembrerebbe richiedere algoritmi di moltiplicazione veloce come karatsuba o o schonage per scomposizione intendi uno di questi metodi?

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [5 Marzo 2020, 7:54pm UTC](https://forum.olinfo.it/t/cameradeisegreti/6086/3 "2020-03-05T19:54:20Z")

</div>

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 😜

---

<div class="post-metadata">

**Author:** ![guass](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/90db22/32.png) [@guass](https://forum.olinfo.it/u/guass)\
**Post date:** [30 Marzo 2020, 4:01pm UTC](https://forum.olinfo.it/t/cameradeisegreti/6086/4 "2020-03-30T16:01:22Z")

</div>

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

```auto
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;
}

```

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [30 Marzo 2020, 5:32pm UTC](https://forum.olinfo.it/t/cameradeisegreti/6086/5 "2020-03-30T17:32:04Z")

</div>

Non è esattamente quello che ho scritto, devi prima calcolare p(x).