wa80 求调

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
const int MAXN = 305;
const int base = 11451;
unsigned long long dpow[MAXN];
unsigned long long pref[MAXN][MAXN], suff[MAXN][MAXN];
char str[MAXN];
long double mtx[MAXN][MAXN], p2[MAXN];
int main() {
	srand(time(NULL));
	dpow[0] = 1; p2[0] = 1;
	int n, m; scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) dpow[i] = dpow[i - 1] * base;
	for (int i = 1; i <= m; i++) p2[i] = p2[i - 1] / 2;
	for (int i = 1; i <= n; i++) {
		scanf("%s", str + 1);
		for (int j = 1; j <= m; j++) {
			pref[i][j] = pref[i][j - 1] * base + str[j] - 'A';
		}
		for (int j = m; j; j--) {
			suff[i][j] = suff[i][j + 1] + (str[j] - 'A') * dpow[m - j];
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < m; k++) {
				if (suff[j][k + 1] == pref[1][m - k]) mtx[i][j] += p2[k];
				if (suff[j][k + 1] == pref[i + 1][m - k]) mtx[i][j] -= p2[k];
			}
		}
	}
	mtx[n][n + 1] = 1;
	for (int j = 1; j <= n; j++) mtx[n][j] = 1;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= n + 1; j++) {
//			printf("%Lf ", mtx[i][j]);
//		}
//		puts("");
//	}
	for (int i = 1; i < n; i++) {
		int swp = i;
		for (int j = i + 1; j <= n; j++) {
			if (mtx[j][i] > mtx[swp][i]) swp = j;
		}
		for (int j = i; j <= n + 1; j++) {
			swap(mtx[i][j], mtx[swp][j]);
		}
		if (mtx[i][i] == 0) continue;
		for (int j = i + 1; j <= n; j++) {
			if (mtx[j][i] == 0) continue;
			long double tm = mtx[j][i] / mtx[i][i]; mtx[j][i] = 0;
			for (int k = i + 1; k <= n + 1; k++) {
				mtx[j][k] -= mtx[i][k] * tm;
			}
		}
//		for (int i = 1; i <= n; i++) {
//			for (int j = 1; j <= n + 1; j++) {
//				printf("%Lf ", mtx[i][j]);
//			}
//			puts("");
//		}
	}
	for (int i = n; i > 1; i--) {
		mtx[i][n + 1] /= mtx[i][i]; mtx[i][i] = 1;
		for (int j = i - 1; j; j--) {
			mtx[j][n + 1] -= mtx[j][i] * mtx[i][n + 1]; mtx[j][i] = 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%.10Lf\n", mtx[i][n + 1]);
	}
	return 0;
}