BZOJ1009 [HNOI2008]GT考试

2015.03.04 15:59 Wed| 4 visits oi_2015| 2015_刷题日常| Text

Solution

看数据范围,矩阵乘法无疑。

用 f[i][j] 表示前 i 位准考证号上匹配到不吉利数字的 j 位的方案数。

构造矩阵 mat[i][j] 表示长度为 i 的前缀转移到长度为 j 的前缀所能加数字的种数。可以用暴力(KMP / AC自动机)求出。最后直接简单矩阵乘法就可以求出答案。

Code

#include <bits/stdc++.h>
using namespace std;

int n, m, mod, ans, pre[22]; char s[22];

struct matrix
{
    int s; int t[22][22];

    matrix(int _s = 0) : s(_s) { memset(t, 0, sizeof t); }

    friend matrix operator *(const matrix &a, const matrix &b)
    {
        matrix re(a.s);
        for (int i = 0; i < re.s; ++i)
            for (int j = 0; j < re.s; ++j)
                for (int k = 0; k < re.s; ++k)
                    re.t[i][j] = (re.t[i][j] + a.t[i][k] * b.t[k][j]) % mod;
        return re;
    }

    matrix &operator *=(const matrix &x){ return *this = *this * x; }

    friend matrix pow(matrix m, int t)
    {
        matrix re(m.s);
        for (int i = 0; i < re.s; ++i)
            re.t[i][i] = 1;
        while (t)
        {
            if (t & 1) re *= m;
            t >>= 1; m *= m;
        }
        return re;
    }

    friend ostream &operator <<(ostream &out, const matrix &x)
    {
        for (int i = 0; i < x.s; ++i)
            for (int j = 0; j < x.s; ++j)
                out << x.t[i][j] << " \n"[j == x.s - 1];
        return out;
    }
};

void kmp(char str[])
{
    int fix = 0;
    for (int i = 2; str[i]; ++i)
    {
        while (fix && str[fix + 1] != str[i])
            fix = pre[fix];
        if (str[fix + 1] == str[i]) ++fix;
        pre[i] = fix;
    }
}

int main()
{
    scanf("%d%d%d%s", &n, &m, &mod, s + 1);
    kmp(s);
    matrix mat(m);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j <= 9; ++j)
        {
            int x = i;
            while (x && j != s[x + 1] - '0') x = pre[x];
            if (j == s[x + 1] - '0') ++mat.t[i][x + 1];
            else ++mat.t[i][0];
        }
    mat = pow(mat, n);
    for(int i=0; i<m; ++i)
        ans += mat.t[0][i];
    cout << ans % mod << endl;
}