Cod sursa(job #2378834)

Utilizator mariusn01Marius Nicoli mariusn01 Data 12 martie 2019 17:46:56
Problema Lista lui Andrei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
/// D[i][j] = numarul de cuvinte de lungime i terminate cu litera j (j = 0, 1, 2, ... 25)
/// D[i][j] = suma din D[i-1][k] daca k,j pot fi asa una dupa alta
/// Cum notez ca literele i si j pot sau nu sa se succeada ?
/// O matrice in care A[i][j] = 1 sau 0 dupa cum i,j pot sau nu sa apara una dupa alta in aceasta ordine
#include <fstream>

using namespace std;
int n, m, i, MOD = 104659, j, k;
char x, y;
int a[26][26];
int D[1001][26];
int main () {
    ifstream fin ("nrcuv.in");
    ofstream fout("nrcuv.out");
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        a[y-'a'][x-'a'] = 1;
        a[x-'a'][y-'a'] = 1;
    }

    /// initializare pentru lungimea 1
    for (i=0;i<=25;i++)
        D[1][i] = 1; /// se numara sirul format doar din litera respectiva

    for (i=2;i<=n;i++) {
        /// numaram siruri de lungime i
        for (j=0;j<=25;j++) {
            /// numaram siruri de lungime i terminate cu litera j
            D[i][j] = 0;
            for (k=0;k<=25;k++) {
                /// ne gandim ca punem litera j la finalul unui sir
                /// de lungime i-1 terminat cu litera k
                if (a[k][j] != 1) {
                    D[i][j] += D[i-1][k];
                    D[i][j] %= MOD;
                }
            }
        }
    }
    int s = 0;
    for(i=0;i<=25;i++)
        s+=D[n][i];
    fout<<s%MOD;
    return 0;
}