Тренировка-2006-03-12 - Решение на C

от Съзтезателно програмиране

Задачата е на практика математическа. Най-важното наблюдение е, че редът на буквите в една дума не е съществен, т.е. нужна ни е само хистограмата на думата - коя буква колко пъти се среща. Нека началната дума представим с вектора

<math>v = \begin{pmatrix}\alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_k \end{pmatrix}</math>, където <math>\alpha_i</math> е броят на срещанията на i-тата буква в началната дума (i = 0 <=> броят срещания на буквата 'a').

Нека запишем хистограмите на всяка "заместваща" дума в колоните на матрицата A:

<math>A = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,k} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,k} \\ \vdots \\ a_{k,1} & a_{k,2} & \cdots & a_{k,k} \end{pmatrix}</math>, където <math>a_{i,j}</math> е броят букви i, които се генерират при едно заместване на буквата j със съответната й дума.

Лесно се вижда, че A.v е вектор-стълб, представляващ хистограмата на думата, която се получава от началната дума след заместване на всичките й букви със съответните им заместващи думи. Оттук по индукция следва, че в задачата се пита съдържанието на вектора x, където:

<math>x = A^m . v</math>

Оттук нататък задачата е лесна, като се използва бързия алгоритъм за повдигане на степен (тъй като m е до 10^9).

Примерно решение на C++

/* TASK: Replacement
   Author: Veselin Georgiev
*/
#include <iostream>
using namespace std;

#define MOD 987654321

int m, k;
char s[10000000];

class matrix {
	long long a[26][26];
	int n,m;
public:
	matrix(int _n, int _m, int fill = 1)
	{
		n = _n; m = _m; memset(a, 0, sizeof(a));
		if (n == m) 
			for (int i = 0; i < n; i++) a[i][i] = fill;
	}
	matrix operator *(const matrix &b)
	{
		matrix res(n, b.m, 0);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < b.m; j++)
				for (int k = 0; k < b.n; k++) {
					res.a[i][j] += (a[i][k] * b.a[k][j]);
					res.a[i][j] %= (long long) MOD;
				}
		return res;
	}
	void insert_column(char *s)
	{
		for (int i = 0; i < n; i++) a[i][m] = 0;
		m++;
		for (int i = 0; s[i]; i++)
			a[s[i]-'a'][m-1]++;
	}
	int index(int i, int j) const { return a[i][j]; }
};

matrix power(const matrix & A, int exponent)
{
	matrix id(k, k);
	matrix mul = A;
	for (unsigned i = 1; i; i <<= 1) {
		if (i & m) id = id * mul;
		mul = mul * mul;
	}
	return id;
}

int main(void)
{
	while (1) {
		cin >> m >> k;
		if (k == 0) break;
		cin >> s;
		matrix init(k, 0);
		init.insert_column(s);
		matrix A(k, 0);
		for (int i = 0; i < k; i++)
		{
			cin >> s;
			A.insert_column(s);
		}
		matrix B = power(A, m);
		matrix res = B * init;
		for (int i = 0; i < k-1; i++)
			cout << res.index(i, 0) << " ";
		cout << res.index(k-1, 0) << endl;
		
	}
	return 0;
}