Cod sursa(job #2579050)

Utilizator sipdavSipos David Oliver sipdav Data 11 martie 2020 21:26:11
Problema Lista lui Andrei Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("nrcuv.in");
ofstream out("nrcuv.out");

const int MOD = 104659;

int n, m, dp[1005][1005];
bool ap[2010][2010];

void read()
{
    in>>n>>m;
    char a, b;
    int x, y;
    for(int i = 1;i <= m;i++)
    {
        in>>a>>b;
        x = a - 'a';
        y = b - 'a';
        x++;
        y++;
        ap[x][y] = ap[y][x] = 1;
    }
}

void solve()
{
    for(int i = 1;i <= 26;i++)
        dp[i][1] = 1;
    for(int i = 2;i <= n;i++)
    {
        for(int j = 1;j <= 26;j++)
        {
            for(int k = 1;k <= 26;k++)
            {
                if(!ap[k][j])
                    dp[j][i] += dp[k][i - 1];
                dp[i][j] %= MOD;
            }
        }
    }
    int rez = 0;
    for(int i = 1;i <= 26;i++)
        rez = (rez + dp[i][n] % MOD) % MOD;
    rez = rez % MOD;
    out<<rez<<'\n';
}

int main()
{
    read();
    solve();
    return 0;
}