频道栏目
首页 > 考试 > 其他 > 正文
字符串的数量 V2 dp+矩阵乘法解析
2017-10-27 09:50:43         来源:beginend  
收藏   我要投稿

字符串的数量 V2 dp+矩阵乘法解析。

用N个不同的字符(编号1 - N),组成一个字符串,有如下要求:
(1) 对于编号为i的字符,如果2 * i > n,则该字符可以作为结尾字符。如果不作为结尾字符而是中间的字符,则该字符后面可以接任意字符。
(2) 对于编号为i的字符,如果2 * i <= n,则该字符不可以作为结尾字符。作为中间字符,那么后面接的字符编号一定要 >= 2 * i。
问有多少长度为M且符合条件的字符串,由于数据很大,只需要输出该数Mod 10^9 + 7的结果。
例如:N = 2,M = 3。则abb, bab, bbb是符合条件的字符串,剩下的均为不符合条件的字符串。
2 <= N <= 10^6, 2 <= M <= 10^18

分析

唉最近净刷些水题。
求出每个长度满足条件的字符串数量,然后矩阵优化一下dp即可。

代码

#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;

const int MOD=1000000007;

int n,s[1000005][21];
LL m;

struct Matrix
{
    int a[25][25];

    void clear(int n)
    {
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                a[i][j]=0;
    }

    void unit(int n)
    {
        clear(n);
        for (int i=1;i<=n;i++) a[i][i]=1;
    }
}a;

void mul(Matrix &c,Matrix a,Matrix b)
{
    c.clear(20);
    for (int i=1;i<=20;i++)
        for (int k=1;k<=20;k++)
            for (int j=1;j<=20;j++)
                (c.a[i][j]+=(LL)a.a[i][k]*b.a[k][j]%MOD)%=MOD;
}

Matrix ksm(Matrix x,LL y)
{
    Matrix ans;ans.unit(20);
    while (y)
    {
        if (y&1) mul(ans,ans,x);
        mul(x,x,x);y>>=1;
    }
    return ans;
}

int main()
{
    scanf("%d%lld",&n,&m);
    for (int i=n;i>=1;i--)
        if (i*2>n) s[i][1]=s[i+1][1]+1;
        else for (int j=1;j<=20;j++) s[i][j]=s[i*2][j-1]+s[i+1][j],s[i][j]-=s[i][j]>=MOD?MOD:0;
    for (int i=1;i<=20;i++) a.a[20-i+1][20]=s[1][i];
    for (int i=1;i<=19;i++) a.a[i+1][i]=1;
    a=ksm(a,m);
    printf("%d",a.a[20][20]);
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:编程开发练习题——match
下一篇:开发中王室联邦(DFS)问题解析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站