Cod sursa(job #202139)

Utilizator slayer4uVictor Popescu slayer4u Data 6 august 2008 12:31:51
Problema Lista lui Andrei Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <stdio.h>

long n, m, i, j, k, num, sum, c[1024][2048], x[1024][2048];
char a, b;

int main()
{
	freopen ("nrcuv.in", "rt", stdin);
	freopen ("nrcuv.out", "wt", stdout);

	scanf("%ld %ld\n", &n, &m);
	for (i = 1; i <= m; ++i)
	{
		scanf("%c %c\n", &a, &b);
		c[a - 'a' + 1][b - 'b' + 1] = c[b - 'b' + 1][a - 'a' + 1] = 1;
	}

	for (i = 1; i <= 26; ++i)
		x[1][i] = 1;

	for (i = 2; i <= n; ++i)
	{
		for (j = 1; j <= 26; ++j)
		{
			num = 0;
			for (k = 1; k <= 26; ++k)
				if (!c[j][k])
					num += x[i - 1][k], num %= 104659;
			x[i][j] = num;
		}
	}

	sum = 0;
	for (i = 1; i <= 26; ++i)
		sum += x[n][i], sum %= 104659;

	printf("%ld\n", sum);

	return 0;
}