HNOI2008GT考试题解

我们先简化一下问题,比如我们把字符集变成3,可以先来看下长度为3,字符串为10的答案。我们可以想到构一棵决策树,叶节点就是所有的方案,如果一个树上一个节点到根的路径上构成的字符串中有一个子串匹配就把这个点涂黑。如图是这个例子的决策树:

我们用一个补集思想,考虑对于每一个子树中叶节点被染黑的个数,我们发现其只跟前面至多有多少个字符连成的字符串是原串前缀以及树的高度有关,因此我们可以定义动态规划的状态f[i][j]表示高度为i,前面至多有j个字符连成的字符串是原串前缀的子树中被染黑的叶节点的个数。然后我们考虑转移,对于每一个节点,有
$f[i][j]=\displaystyle\sum_{k=0}^{9}f[i-1][p[j][k]]$
这里面p[i][j]表示匹配到第i个位置下一个位置为k时应该去的位置,对于一般情况,只需要搞个AC自动机把它的每条边指向的节点记下来即可,特别的,由于一个节点被染黑后其所有子孙全部要染黑,所以对于任意p[m][j]都为m。然后把这个东西倒一下弄个矩阵乘法就可以了。

#include<bits/stdc++.h>
int next[25],p[25][15],s[25],n,m,mod;
void get_next(const int& n){
    next[0]=-1;
    for(int i=1;i<=n;++i){
        int j=next[i-1];
        while(j!=-1&&s[j+1]!=s[i]) j=next[j];
        next[i]=j+1;
    }
    for(int j=0;j<=9;++j) p[0][j]=(s[1]==j)?1:0;
    for(int i=1;i<n;++i)
        for(int j=0;j<=9;++j)
            p[i][j]=(s[i+1]==j)?(i+1):p[next[i]][j];
    for(int j=0;j<=9;++j) p[n][j]=n;
}
class Matrix{
    public:
        int matrix[25][25];
        Matrix& operator*=(Matrix y){
            int z[25][25];
            for(int i=0;i<=m;++i)
                for(int j=0;j<=m;++j){
                    z[i][j]=0;
                    for(int k=0;k<=m;++k)
                        z[i][j]=(z[i][j]+matrix[i][k]*y.matrix[k][j])%mod;
                }
            for(int i=0;i<=m;++i)
                for(int j=0;j<=m;++j)
                    matrix[i][j]=z[i][j];
            return *this;
        }
        void print(){
            for(int i=0;i<=m;++i){
                puts("");
                for(int j=0;j<=m;++j)
                    printf("%d ",matrix[i][j]);
            }
            puts("");
        }
}ans,ie;
void fast_power_matrix(int x){
    for(int i=0;(1<<i)<=x;++i){
        if((x&(1<<i>0) ans*=ie;
        ie*=ie;
    }
}
int fast_power_int(int x){
    int ret=1,pow=10;
    for(int i=0;(1<<i)<=x;++i){
        if((x&(1<<i>0) ret=(ret*pow)%mod;
        pow=(pow*pow)%mod;
    }
    return ret;
} 
char str[25];
int main(){
    scanf("%d%d%d",&n,&m,&mod); 
    scanf("%s",str+1);
    for(int i=1;i<=m;++i) s[i]=str[i]-'0';
    get_next(m);
    for(int i=0;i<=m;++i)
        for(int j=0;j<=m;++j)
            ans.matrix[i][j]=(i==0&&j==m)?1:0;
    for(int i=0;i<=m;++i)
        for(int j=0;j<=m;++j)
            ie.matrix[i][j]=0;
    for(int i=0;i<=m;++i)
        for(int k=0;k<=9;++k)
            ++ie.matrix[p[i][k]][i];
    fast_power_matrix(n);
    int top=fast_power_int(n);
    printf("%d",(top-ans.matrix[0][0]+mod)%mod);
    return 0;
}

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注