[TJOI2019]甲苯先生的字符串——矩阵乘法+递推

电玩女神 2022-01-13 04:27 252阅读 0赞

# 题目链接： #

[\[TJOI2019\]甲苯先生的字符串][TJOI2019]

我们用一个$26\*26$的$01$矩阵记录任意两个字符是否能相邻。

设$f\[i\]\[j\]$表示处理完前$i$个字符，第$i$个字符为$j$的方案数。

可以发现将$f\[i\]$这个$1\*26$的矩阵与$26\*26$的$01$矩阵相乘即可得到$f\[i+1\]$的矩阵。

直接将$01$矩阵矩乘即可。

注意题目中要求的不能相邻是指不能按原顺序相邻，即$s1$中有$ab$但$s2$中可以有$ba$。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<vector>
    #include<bitset>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int mod=1000000007;
    struct lty
    {
        int a[27][27];
        lty(){memset(a,0,sizeof(a));}
        lty operator *(const lty &x)const
        {
            lty res=lty();
            for(int i=1;i<=26;i++)
            {
                for(int j=1;j<=26;j++)
                {
                    for(int k=1;k<=26;k++)
                    {
                        res.a[i][j]=(res.a[i][j]+1ll*a[i][k]*x.a[k][j]%mod)%mod;
                    }
                }
            }
            return res;
        }
    };
    int vis[27][27];
    char s[100010];
    ll n;
    lty ans;
    lty quick(ll n)
    {
        lty s=lty();
        for(int i=1;i<=26;i++)
        {
            s.a[i][i]=1;
        }
        while(n)
        {
            if(n&1)
            {
                s=s*ans;
            }
            n>>=1;
            ans=ans*ans;
        }
        return s;
    }
    int main()
    {
        scanf("%lld",&n);
        scanf("%s",s+1);
        int len=strlen(s+1);
        for(int i=2;i<=len;i++)
        {
            vis[s[i-1]-'a'+1][s[i]-'a'+1]=1;
        }
        for(int i=1;i<=26;i++)
        {
            for(int j=1;j<=26;j++)
            {
                ans.a[i][j]=1-vis[i][j];
            }
        }
        lty res=quick(n-1);
        int ret=0;
        for(int i=1;i<=26;i++)
        {
            for(int j=1;j<=26;j++)
            {
                ret=(ret+res.a[i][j])%mod;
            }
        }
        printf("%d",ret);
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10828056.html

[TJOI2019]: https://loj.ac/problem/3104