# Spring Carnival (colors)

**URL:** <https://forum.olinfo.it/t/spring-carnival-colors/8560>\
**Category:** Aiuto\
**Created:** [27 Ottobre 2023, 5:21pm UTC](https://forum.olinfo.it/t/spring-carnival-colors/8560 "2023-10-27T17:21:01Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![gengu](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/e68b1a/32.png) [@gengu](https://forum.olinfo.it/u/gengu)\
**Post date:** [27 Ottobre 2023, 5:21pm UTC](https://forum.olinfo.it/t/spring-carnival-colors/8560/1 "2023-10-27T17:21:01Z")

</div>

Salve a tutti, ho provato questo problema ma la mia soluzione ottiene solo 26 punti e non capisco il perchè visto che non trovo controesempi ☹ .  
Se qualcuno può darmi una mano grazie mille 🙂 .  
Allego l’algoritmo che ho pensato qui sotto:

```auto
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

// constraints
#define MAXN 200000
#define MAXK 100000000
#define MOD 1000000007

// input data
int N, K;
int V[MAXN];

int main() {
    // uncomment the following lines if you want to read/write from files
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    assert(2 == scanf("%d%d", &N, &K));
    for (int i = 0; i < N; i++) {
        assert(1 == scanf("%d", &V[i]));
    }

    int x = 1, newColor = 0;
    int conta[MAXN] = {0};

    for (int i = 0; i < N; i++)
    {
        if(V[i] == 0){
            x=(x*(K-newColor))%MOD;
            newColor++;
        }
        else{
            x = (x*conta[V[i]-1])%MOD;
            conta[V[i]-1]--;
        }
        conta[V[i]]++;
    }
    

    printf("%d\n", x); // print the result

    return 0;
}

```

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [27 Ottobre 2023, 7:09pm UTC](https://forum.olinfo.it/t/spring-carnival-colors/8560/2 "2023-10-27T19:09:27Z")

</div>

L’errore è nelle istruzioni `x=(x*(K-newColor))%MOD;`, `x = (x*conta[V[i]-1])%MOD;`, infatti quei due prodotti possono generare un overflow essendo `x` di tipo `int` (nota che il modulo viene applicato dopo il calcolo del prodotto, quindi il prodotto intermedio va in overflow). Il modo più semplice per sistemare è dichiare `x` di tipo `long long`