矩阵快速幂优化dp-程序员宅基地

技术标签: 算法  线性代数  动态规划  


构造矩阵快速幂优化线性递推式

遇到某些线性递推式,我们可以设法构造成矩阵乘积的形式,
像斐波那契数列 f[i]=f[i-1]+f[i-2] ,写成矩阵乘积的好处就是,
由于矩阵乘积具有结合律,我们可以用快速幂来优化。

(矩阵的构造一般不难,把转移矩阵写出来,左边的方阵很好求)

难点还是在于dp的递推式。

另外要注意,运算只要满足结合律,就可以使用快速幂,像max,min,加减乘除都可以。

举个max的例子:
在这里插入图片描述
转移方程很容易写出来:
在这里插入图片描述
但是这样时间复杂度是O(n * m * m)

我们重新定义矩阵乘法c[i][j]=max(a[i][k]+b[k][j])
,把递推式写成矩阵乘法的形式:
在这里插入图片描述
然后就可以用快速幂了。

在这里插入图片描述

POJ3734

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
//#pragma GCC optimize(2)
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define re register
const int maxn = 1e4 + 10;
const int mx = 40;
const int mod = 10007;
const ll inf = 34359738370;
const int INF = 1e9 + 7;
const double pi = acos(-1.0);
//n个格子染色 4种颜色 求染完后1 3有偶数个的方案数
//a[i] b[i] c[i] 表示染完i个 1 3都为偶数 有一个是偶数 都是奇数 
//a[i]=b[i-1]*1+a[i-1]*2
//b[i]=b[i-1]*2+c[i-1]*2+a[i-1]*2
//c[i]=c[i-1]*2+b[i-1]
//写成矩阵乘法的形式 用矩阵快速幂优化

//a[1]=2 b[1]=2 c[1]=0
struct matrix
{
    
    int m[3][3];
    void init()
    {
    
        memset(m,0,sizeof m);
        m[0][0]=1;
        m[1][1]=1;
        m[2][2]=1;
    }
    inline matrix operator * (const matrix &f)const 
    {
    
        matrix ans;
        memset(ans.m,0,sizeof ans.m);
        for(int i=0;i<3;i++)
        {
    
            for(int j=0;j<3;j++) 
            {
    
                for(int k=0;k<3;k++)
                    ans.m[i][j]=(ans.m[i][j]+m[i][k]*f.m[k][j]%mod)%mod;
            }
        }
        return ans;
    }
}mat;

matrix ksm(matrix a,int n) 
{
    
    matrix ret;
    ret.init();
    while(n)
    {
    
        if(n&1) ret=ret*a;
        a=a*a;
        n>>=1;
    }
    return ret;
}
int n;
int main()
{
    
    int t;cin>>t;
    while(t--) 
    {
    
        scanf("%d",&n);
        mat.m[0][0]=2,mat.m[0][1]=1,mat.m[0][2]=0;
        mat.m[1][0]=2,mat.m[1][1]=2,mat.m[1][2]=2;
        mat.m[2][0]=0,mat.m[2][1]=1,mat.m[2][2]=2;
        mat=ksm(mat,n-1);
        int sum=mat.m[0][0]*2%mod+mat.m[0][1]*2%mod;
        cout<<sum%mod<<'\n';
    }
    return 0;
}

Buses Gym - 101473H

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
//#pragma GCC optimize(2)
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define re register
const int maxn = 1e4 + 10;
const int mx = 105;
const int mod = 1000000;
const ll inf = 34359738370;
const int INF = 1e9 + 7;
const double pi = acos(-1.0);
//车队由大车和小车组成 大车10米 小车5米 分别有B A种颜色可以涂  给定车队长度n 问所有可能的涂色方案数
//f[i]=a*f[i-5]+b*f[i-10] 
//由于只有5的倍数才有用 n/=5 f[i]=a*f[i-1]+b*f[i-2]
//边界f[1]=a f[0]=1
//都是n a b都是1e15级别
//矩阵快速幂
struct matrix
{
    
    ll mt[2][2];
    void init()
    {
    
        memset(mt,0,sizeof mt);
        for(int i=0;i<2;i++) mt[i][i]=1;
    }
    matrix operator *(const matrix &f)const 
    {
    
        matrix ans;
        memset(ans.mt,0,sizeof ans.mt);
        for(int i=0;i<2;i++)
        {
    
            for(int j=0;j<2;j++)
            {
    
                for(int k=0;k<2;k++)
                {
    
                    ans.mt[i][j]=(ans.mt[i][j]+mt[i][k]*f.mt[k][j]%mod)%mod;
                }
            }
        }
        return ans;
    }
}ei;//ei 转移矩阵
ll n,a,b;
matrix ksm(matrix x,ll q) 
{
    
    matrix ret;
    ret.init();
    while(q) 
    {
    
        if(q&1) ret=ret*x;
        x=x*x;
        q>>=1;
    }
    return ret;
}
int main()
{
       
    cin>>n>>a>>b;
    a%=mod,b%=mod;
    ei.mt[0][0]=a,ei.mt[0][1]=b;
    ei.mt[1][0]=1,ei.mt[1][1]=0;
    ei=ksm(ei,n/5-1);
    ll ans=ei.mt[0][0]*a%mod+ei.mt[0][1]%mod;
    printf("%06lld\n",ans%mod);
    return 0;
}   

CF222E Decoding Genome

某种DNA,长度不超过1e15,可以由'a''z','A''Z'52种字母组成,有k对(x,y)表示y不能出现在x的下一位,给出n m k,计算一共有多少种DNA序列。

首先不管n的范围想出一个dp递推式:

dp[n][j]表示长度为n,结尾是j字符的合法DNA数量

dp[n][j]=Σdp[n-1][k]*mp[k][j] (枚举k,如果k后面能接j,mp[k][j]==1,否则0)

这是一个线性的递推式,而且mp的范围不大,试试能否写成矩阵乘积的形式,

写出来发现是这样的:
在这里插入图片描述
最终结果就是左边矩阵元素之和,而由于初始矩阵每个元素都是1,所以我们求出转移矩阵的n-1次方,再把所有元素加起来就能得到最终答案。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
//#pragma GCC optimize(2)
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define re register
const int maxn = 1e4 + 10;
const int mx = 105;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9 + 7;
const double pi = acos(-1.0);
ll n;
int m,k;
struct matr
{
    
    ll ax[55][55];
    void init()
    {
    
        memset(ax,0,sizeof ax);
        for(int i=0;i<55;i++) ax[i][i]=1;
    }
    matr operator *(const matr &f)const 
    {
    
        matr ans;
        memset(ans.ax,0,sizeof ans.ax);
        for(int i=1;i<=m;i++)
        {
    
            for(int j=1;j<=m;j++)
            {
    
                for(int k=1;k<=m;k++)
                {
    
                    ans.ax[i][j]=(ans.ax[i][j]+ax[i][k]*f.ax[k][j]%mod)%mod;
                }
            }
        }
        return ans;
    }
}ei;
matr ksm(matr x,ll b)
{
    
    matr ret;ret.init();
    while(b) 
    {
    
        if(b&1) ret=ret*x;
        x=x*x;
        b>>=1;
    }
    return ret;
}
inline int getid(char _)
{
    
    if('a'<=_ && _<='z') return _-'a'+1;
    else return _-'A'+27;
}
int mp[55][55];//不能连续出现的对
int main()
{
    
    scanf("%lld %d %d",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
    
        for(int j=1;j<=m;j++) mp[i][j]=1;//初始都能出现
    }
    for(int i=1;i<=k;i++)
    {
    
        char s[5];scanf("%s",s);
        int x=getid(s[0]),y=getid(s[1]);
        mp[x][y]=0;
    }
    for(int i=1;i<=m;i++)
    {
    
        for(int j=1;j<=m;j++)
        {
    
            ei.ax[i][j]=mp[j][i];//转移矩阵ax是mp的转置
        }
    }
    ei=ksm(ei,n-1ll);
    ll ans=0;
    for(int i=1;i<=m;i++)
    {
    
        for(int j=1;j<=m;j++) ans=(ans+ei.ax[i][j])%mod;
    }
    cout<<ans<<'\n';
    return 0;

}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_46030630/article/details/120236732

智能推荐

Java编程:删除 List 元素的三种正确方法_java synchronized list 元素删除-程序员宅基地

文章浏览阅读942次。删除 List 中的元素会产生两个问题:删除元素后 List 的元素数量会发生变化;对 List 进行删除操作可能会产生并发问题;_java synchronized list 元素删除

D语言游戏编程(11):D语言基础之模板和混入(mixin)技术_d语言 模板实例化-程序员宅基地

文章浏览阅读3.7k次。 D语言通过模板,很好的支持泛型编程。与C++的模板相比较,各有优略。总体上说,D语言的模板在很多方面还是很方便的。 D语言还支持模板的混入(mixin),简单的讲就是把模板实例化之后,将模板中的代码插入到当前的位置。这是一个非常方便的工具! 具体的,请看下面的演示代码。import std.stdio;void main()...{ tryTemplate();_d语言 模板实例化

目标 linux 服务器提权,史上最全Linux提权后获取敏感信息方法 (zhuan)-程序员宅基地

文章浏览阅读364次。(Linux)的提权是怎么一回事:收集 – 枚举,枚举和一些更多的枚举。过程 – 通过数据排序,分析和确定优先次序。搜索 – 知道搜索什么和在哪里可以找到漏洞代码。适应 – 自定义的漏洞,所以它适合。每个系统的工作并不是每一个漏洞“都固定不变”。尝试 – 做好准备,试验和错误。系统类型系统是什么版本?cat /etc/issuecat /etc主机上有哪些工作计划?crontab -lls -al..._linux服务器被提权如何解决

Device token 什么时候会发生变化_苹果手机恢复出厂设置token会不会变-程序员宅基地

文章浏览阅读5.8k次。stackoverflow 针对Device token 什么时候会发生变化有个很棒的解答。在一台设备中, device token 是系统级别的,不同 App 获得的 device token 是相同的。假如我的手机安装了 Angry Bird 和 Evernote ,这两个应用获得 device token 一模一样。device token 并不会因为单个 app 的_苹果手机恢复出厂设置token会不会变

IO流——文件操作流之字符输入流FileReader-程序员宅基地

文章浏览阅读1.9k次。package com.io.ioDemo;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;//字符流读文件public class FileReaderDemo { public static void mai_字符输入流filereader

Linux深入理解_深入理解linux系统-程序员宅基地

文章浏览阅读1.8w次,点赞14次,收藏12次。一、背景: 翻看着差不多去年这时候写的《痴迷Linux(一)—初识篇》不禁感慨时光飞逝,转眼间已一年闪过。。。回想这一年与Linux交往之路,发现与她也仅仅是停留在表面上的!回想原因:自己现在还没到和她深交的阶段(正所谓距离产生美嘛)同时由于一些原因(比如:这次实训、装服务器等)自己也并一直和她有来往。 这次实训是学校为大三计算机专业安排历时三天;主要讲课内容: ①..._深入理解linux系统

随便推点

关系型数据库和非关系型数据库的区别与联系_谈谈关系型数据库与非关系型数据库的联系和区别-程序员宅基地

文章浏览阅读2.2k次。数据库一、概念数据库是以一定方式储存在一起、能与多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。数据库管理系统是一种操纵和管理数据库的大型软件,用于建立、使用和维护数据库,简称DBMS。它对数据库进行统一的管理和控制,以保证数据库的安全性和完整性。二、分类关系型数据库NOSQL三、NoSQL与关系型数据库的区别存储方式传统的关系型数..._谈谈关系型数据库与非关系型数据库的联系和区别

基于Eureka的微服务注册与使用_eureka注册其他机器的微服务-程序员宅基地

文章浏览阅读253次。承接上一章,项目还是使用之前的两个已经创建好的spring boot项目!这一节主要是学习Eureka的注册和使用!跟上一章一样,我们在父模块下继续创建一个module,这次创建一个Eureka项目!第一,先创建一个Eureka项目,并成功启动1,new module2,创建一个Eureka项目,跟上一节有一点点的小区别,注意一下3,直接下一步下一步到结束,完了删除多余的文..._eureka注册其他机器的微服务

VCS dump 波形的函数_vcs $dumpports-程序员宅基地

文章浏览阅读2.1k次。当使用VCS 仿真是,如果需要dump 波形,可以使用:1,fsdbdumpfile xxx.fsdb或者使用fsdbAutoSwitchDumpfile < size> name < barksize>2, 通过fsdbDumpvars < depth> 设置波形深度,默认设置0 全dump;_vcs $dumpports

XamarinAndroid组件教程设置自定义子元素动画(一)_xamarin imageview 动画-程序员宅基地

文章浏览阅读202次。XamarinAndroid组件教程设置自定义子元素动画(一)如果在RecyclerViewAnimators.Animators中没有所需要的动画效果,就可以自定义一个。此时,需要让自定义的动画继承BaseItemAnimator抽象类。【示例1-2】下面以RecylerViewAnimatorsItemAnimator项目为基础,在RecylerView子元素进行添加/删除操作时,实现透明动画..._xamarin imageview 动画

【BZOJ】【P2395】【Balkan 2011】【Timeismoney】【题解】【最小乘积生成树】_最小乘积生成树 注释-程序员宅基地

文章浏览阅读1.3k次。传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2395其实还不太会写……Code:#include#include#includeusing namespace std;typedef long long LL;struct edge{ int u,v,w,c,t; bool operator<(const edg_最小乘积生成树 注释

《Linux杂记》查看Linux内核版本的命令_uname -a 读的哪的内容-程序员宅基地

文章浏览阅读2.1k次。方法一: 命令: uname -a 作用: 查看系统内核版本号及系统名称。方法二: 命令: cat /proc/version 作用: 查看目录”/proc”下version的信息,也可以得到当前系统的内核版本号及系统名称 补充说明:   /proc文件系统,它不是普通的文件系统,而是系统内核的映像,也就是说,该目录中的文件是存放在系统内存之中的,它以文件系统的方式为访..._uname -a 读的哪的内容

推荐文章

热门文章

相关标签