On donne deux séquences d'entiers de longueur $n$, $B=[b_1,\ldots,b_n]$ et $C=[c_1,\ldots,c_n]$. Pour une séquence d'entiers positifs ou nuls $D=[d_1,\ldots,d_n]$, soit $S(D)$ l'ensemble des indices $i$ tels que $d_i=0$. On définit
$$ f(D)=\sum_{i\in S(D)}b_i,\qquad g(D)=\prod_{i\in S(D)}c_i. $$
En particulier, si $S(D)$ est vide, $f(D)=0$ et $g(D)=1$.
Xiao L possède une séquence d'entiers strictement positifs $A=[a_1,\ldots,a_n]$. Il peut la modifier ainsi :
- Choisir deux indices voisins $i,j$ de $A$, c'est-à-dire $1\le i,j\le n$ et $|i-j|=1$. Si $a_i\le a_j$, remplacer $a_j$ par $a_j-a_i$ et simultanément $a_i$ par $0$.
Il peut effectuer autant d'opérations qu'il le souhaite, y compris aucune. Parmi toutes les séquences $D$ accessibles depuis $A$, il souhaite connaître la valeur maximale de $f(D)$ ainsi que la somme des $g(D)$. Aidez-le à calculer ces deux valeurs. Formellement, si $T(A)$ est l'ensemble de toutes les séquences accessibles par ces opérations, calculez $\max_{D\in T(A)}f(D)$ et $\sum_{D\in T(A)}g(D)$. Cette somme pouvant être grande, calculez seulement son reste modulo $1\,000\,000\,007$.
Entrée
Les données sont lues dans le fichier sequence.in.
Ce problème comporte plusieurs cas de test.
La première ligne contient deux entiers positifs ou nuls $c,t$, respectivement le numéro du test et le nombre de cas de test. La valeur $c=0$ indique un exemple.
Les cas sont ensuite donnés successivement. Pour chaque cas :
La première ligne contient un entier strictement positif $n$, la longueur des séquences.
La deuxième contient $n$ entiers strictement positifs $a_1,\ldots,a_n$, la séquence $A$.
La troisième contient $n$ entiers $b_1,\ldots,b_n$, la séquence $B$.
La quatrième contient $n$ entiers strictement positifs $c_1,\ldots,c_n$, la séquence $C$.
Sortie
Écrivez la sortie dans le fichier sequence.out.
Pour chaque cas, affichez une seule ligne de deux entiers : $\max_{D\in T(A)}f(D)$, puis $\sum_{D\in T(A)}g(D)$ modulo $1\,000\,000\,007$. Attention : le maximum de $f(D)$ ne doit pas être réduit modulo $1\,000\,000\,007$.
Ce problème comporte deux questions. Répondre correctement à l'une d'elles donne des points partiels ; consultez la section « Sous-tâches » pour les règles précises.
Exemples
Entrée 1
0 3 3 5 6 6 3 6 9 1 2 3 6 1 1 4 5 1 4 -1 1 -1 1 -2 2 1 1 1 1 1 1 8 4 2 4 2 2 2 4 4 -2 4 9 -3 4 8 7 8 1 1 1 1 1 1 1 1
Sortie 1
15 10 1 18 37 48
Remarque
Cet exemple contient trois cas de test.
Pour le premier, les quatre séquences suivantes sont accessibles :
- $D=[5,6,6]$, $f(D)=0$, $g(D)=1$ ;
- $D=[0,1,6]$, $f(D)=3$, $g(D)=1$ ;
- $D=[5,0,0]$, $f(D)=6+9=15$, $g(D)=2\times3=6$ ;
- $D=[0,0,5]$, $f(D)=3+6=9$, $g(D)=1\times2=2$.
Ainsi, $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$, et $\sum_{D\in T(A)}g(D)=1+1+6+2=10$.
Exemple 2
Voir sequence/sequence2.in et sequence/sequence2.ans dans le répertoire des candidats.
Cet exemple respecte les contraintes des tests $3,4$.
Exemple 3
Voir sequence/sequence3.in et sequence/sequence3.ans dans le répertoire des candidats.
Cet exemple respecte les contraintes des tests $5,6$.
Exemple 4
Voir sequence/sequence4.in et sequence/sequence4.ans dans le répertoire des candidats.
Cet exemple respecte les contraintes du test $7$.
Exemple 5
Voir sequence/sequence5.in et sequence/sequence5.ans dans le répertoire des candidats.
Cet exemple respecte les contraintes des tests $11,12$.
Exemple 6
Voir sequence/sequence6.in et sequence/sequence6.ans dans le répertoire des candidats.
Cet exemple respecte les contraintes des tests $16\sim18$.
Contraintes
Soit $N$ la somme des $n$ sur tous les cas d'un même test. Pour toutes les données :
- $1\le t\le20$ ;
- $1\le n\le5000$, $N\le4\times10^4$ ;
- Pour tout $1\le i\le n$, $1\le A_i\le10^9$ ;
- Pour tout $1\le i\le n$, $-10^9\le B_i\le10^9$ ;
- Pour tout $1\le i\le n$, $1\le C_i\le10^9$.
| Numéros des tests | $n\le$ | $N\le$ | Propriété particulière |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | Aucune |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | Aucune | ||
| 7 | $500$ | $10^3$ | A |
| $8\sim10$ | B | ||
| $11,12$ | Aucune | ||
| 13 | $3500$ | $3\times10^4$ | A |
| $14,15$ | B | ||
| $16\sim18$ | Aucune | ||
| $19,20$ | $5000$ | $4\times10^4$ |
Propriété particulière A : $A_1=A_2=\cdots=A_n=1$.
Propriété particulière B : pour tout $1\le i\le n$, les $A_i$ sont générés indépendamment et uniformément au hasard dans $[1,10^9]$.
Sous-tâches
Pour chaque test :
- Répondre correctement à $\max_{D\in T(A)}f(D)$ pour tous les cas rapporte 40 % des points du test.
- Répondre correctement à $\sum_{D\in T(A)}g(D)$ modulo $1\,000\,000\,007$ pour tous les cas rapporte 60 % des points du test.
Attention : même si vous ne répondez qu'à une des deux questions, vous devez afficher les deux entiers au format demandé, correspondant respectivement aux deux réponses.