Spring Carnival (colors)

Aiuto
1

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 :frowning: .
Se qualcuno può darmi una mano grazie mille :slight_smile: .
Allego l’algoritmo che ho pensato qui sotto:

#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;
}
2

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