ZOJ 2619： Generator

类型：概率 + 解方程组（高斯消元法） + KMP（好吧其实我用的是暴力~）
题意：你可以等概率的选择大写字母里的前n个字母，在纸上写啊写，一直到出现给定的字符串。问写的字母个数的期望。
思路：

期望递推法。（不过这里推出了个环……）
下一个状态是看现在这个串，加上一个字母之后，能匹配到原串的哪里。（就是KMP里面的失配数组，写字符串的过程，就是一边写一边匹配）
不过我KMP不太熟悉，就直接暴力了。。
推完后发现，推出了一个环。怎么办，只能用高斯消元法来解这个方程组了。
这题比较特殊，经过证明（我不会= =）可以得到，答案必定为整数。
高斯消元法用double精度卡死（样例都过不了），用分数还是WA（可能溢出了），最后纯用long long 终于过了它。。。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

char str[100];
char tmpstr[100]; 

long long matrix[100][100];

int check() {
    int res = 0;
    for (int i = 0; tmpstr[i]; i++) {
        bool ok = true;
        for (int j = 0; tmpstr[j+i]; j++) {
            if (str[j] != tmpstr[j+i]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            res = strlen(tmpstr) - i;
            break;
        }
    }
    return res;
}

bool gauss(int row, int col) {
    for (int i = 0; i < row; i++) {
        int k = -1;
        for (int j = i; j < row; j++) {
            if (matrix[j][i] != 0) {
                k = j;
                break;
            }
        }
        if (k == -1) return false;
        for (int j = 0; j < col; j++) {
            swap(matrix[i][j],matrix[k][j]);
        }
        if (matrix[i][i] < 0) {
            for (int j = 0; j < col; j++) {
                matrix[i][j] *= -1;
            }
        }
        for (int j = 0; j < row; j++) {
            if (j == i) continue;
            if (matrix[j][i] == 0) continue;
            if (matrix[j][i] < 0) {
                for (int k = 0; k < col; k++) {
                    matrix[j][k] *= -1;
                }
            }
            long long gcdnum = __gcd(matrix[i][i], matrix[j][i]);
            long long lcanum = matrix[i][i]/gcdnum*matrix[j][i];
            long long jmul = lcanum / matrix[j][i];
            long long imul = lcanum / matrix[i][i];
            for (int k = 0; k < col; k++) {
                matrix[j][k] = matrix[j][k]*jmul - matrix[i][k] * imul;
            }
        }
    }
    return true;
}

void print(int len) {
    puts("--------");
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len+1; j++) {
            printf("%lld ", matrix[i][j]);
        }puts("");
    }
}

int main() {
    int t;
    scanf("%d", &t);
    for (int cas = 1; cas <= t; cas++) {
        if (cas != 1) puts("");
        printf("Case %d:
", cas);

        int n;
        scanf("%d%s", &n, str);
        int len = strlen(str);

        //计算dp[0]~dp[len-1] len条方程
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len+1; j++) matrix[i][j] = 0;
            matrix[i][i] = -n;
            matrix[i][len] = -n;
            sprintf(tmpstr, "%s", str);
            tmpstr[i+1] = 0;
            for (int j = 0; j < n; j++) {
                tmpstr[i] = 'A'+j;
                if (check() != len) matrix[i][check()]++;
            }
        }
        //print(len);
        if (!gauss(len, len+1)) puts("ERROR");
        //print(len);
        //printf("%lld(%lld/%lld)
", matrix[0][len]/matrix[0][0], matrix[0][len], matrix[0][0]);
        printf("%lld
", matrix[0][len]/matrix[0][0]);
    }
    return 0;
}