ACM训练赛赛后补题:Happy Necklace(思维+递推+矩阵快速幂)

题目描述:
在这里插入图片描述
在这里插入图片描述
分析

这道题很容易就可以定性为动态规划,需要能够推出递推公式;然后观察发现n太大了,最多只能接收O(logn)的复杂度,这样的复杂度,实现的方式就是矩阵快速幂。

首先题目所说的是这一串项链里面的任何一个长度为素数的子串,都必须满足红色珠子的个数大于等于蓝色珠子的个数,那么我们可以粗略的将dp数组的状态定义为两个,f[i][j],其中i表示当前链子的长度为i,j表示这一串链子的最后一个元素(即下标i)的颜色(0表示蓝色,1表示红色)
容易得知:

(1)f[i][1]=f[i-1][1]+f[i-1][0],不论前一个珠子是红色还是蓝色,只要放上红色珠子都是可以的;
(2)f[i][0]=f[i-2][1]。可以这样想,想要在这里放上蓝色珠子,那么显然前两个元素都得是红色的珠子,因为不管是长度为2还是长度为3都必须要是红珠子数量>=蓝珠子数量,可以看做是长度为i-2,且最后一个元素为红色珠子的基础上,再加上“红蓝”这样的情况。
这里其实是有一些思维的,具体体现在,当我们在加入一个蓝色珠子的时候,前面的长度为素数的子串情况明明有很多,但是我们只考虑了长度为2的情况,这是因为,除了2以外的所有的素数,都是奇数,既然前面满足了限定条件,那么可以推断红色珠子的数量一定大于蓝色珠子的数量,因此我们只需要考虑i-2这个情况,其他的任何情况加上蓝色珠子都会满足“素数长度的子串中红色数量>=蓝色数量”。

接下来记录ans[i]=f[i][0]+f[i][1],易得
ans[i]=f[i-2][1]+f[i-1][1]+f[i-1][0]=(f[i-3][1]+f[i-3][0])+(f[i-1][1]+f[i-1][0])
=ans[i-3]+ans[i-1]

因此最后这题我们的总递推公式就记为:

f[n]=f[n-1]+f[n-3]

但是我们可以发现这题的范围太大了,也不可能开这么大数组,而且常规的递推下去是会超时的,因此考虑矩阵快速幂来实现加速,复杂度是O(logn),轻松过掉这道题。

因此我们构造一下这个矩阵,通过递推公式易得:
在这里插入图片描述

可以用快速幂的降幂思维(logn),容易得知,当幂次为奇数的时候,直接乘以这个3*3矩阵即可进入下一级别,当为偶数的时候,需要将2个原3*3矩阵先进行相乘,因为乘法运算律同样适用于矩阵,只要矩阵的相乘合理即可,不多解释了,推一下就行。

接下来就是我们的初始化问题,初始的矩阵应该设置为(f[3],f[2],f[1]),f[1]本身不存在,但是我们可以根据递推公式对其进行构造,由于f[4]=f[3]+f[1],推出f[1]=2,如此初始化即可。

代码如下:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=1e9+7;
struct Matrix{
    ll a[5][5];
    Matrix(){memset(a,0,sizeof(a));}
};
inline Matrix Mul(Matrix a,Matrix b){
    Matrix temp;
    for(int i=1;i<=3;++i)
        for(int j=1;j<=3;++j)
            for(int k=1;k<=3;++k)
                temp.a[i][j]=(temp.a[i][j]+(a.a[i][k]*b.a[k][j])%MOD)%MOD;
    return temp;
}
inline int fun(ll n){
    Matrix ans,res;
    ans.a[1][1]=4;ans.a[1][2]=3;ans.a[1][3]=2;
    res.a[1][1]=res.a[1][2]=res.a[2][3]=res.a[3][1]=1;
    while(n){//快速幂思想
        if(n&1)ans=Mul(ans,res);
        res=Mul(res,res);
        n>>=1;
    }
    return ans.a[1][1];
}
int main(){
    int t;cin>>t;
    while(t--){
        ll n;scanf("%lld",&n);
        if(n==2)printf("3\n");
        else if(n==3)printf("4\n");
        else printf("%d\n",fun(n-3));
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/1309.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

77.qt qml-QianWindow-V1版本界面讲解

上章介绍: 76.qt qml-QianWindow开源炫酷界面框架简介(支持白色暗黑渐变自定义控件均以适配) 界面如下所示: 代码结构如下所示:

大学四年..就混了毕业证的我,出社会深感无力..辞去工作,从头开始

时间如白驹过隙&#xff0c;一恍就到了2023年&#xff0c;今天最于我来说是一个值得纪念的日子&#xff0c;因为我收获了今年的第一个offer背景18年毕业&#xff0c;二本。大学四年&#xff0c;也就将就混了毕业证和学位证。毕业后&#xff0c;并未想过留在湖南&#xff0c;就回…

西安石油大学C语言期末重点知识点总结

大一学生一周十万字爆肝版C语言总结笔记 是我自己在学习完C语言的一次总结&#xff0c;尽管会有许多的瑕疵和不足&#xff0c;但也是自己对C语言的一次思考和探索&#xff0c;也让我开始有了写作博客的习惯和学习思考总结&#xff0c;争取等我将来变得更强的时候再去给它优化出…

计算机组成原理笔记——计算机性能指标(CPI、IPS、MIPS等)

计算机系统的性能评价有两种指标&#xff0c;分别为非时间指标和时间指标。 非时间指标 机器字长总线宽度主存容量、存储带宽CPU内核数 时间指标 主频、周频、外频、倍频CPI、IPCMIPS、MFLOPSCPU执行时间 非时间指标 &#xff08;1&#xff09;机器字长 机器一次能处理的二…

复制带随机指针的复杂链表

目录一、题目题目链接二、题目分析三、解题思路四、解题步骤4.1 复制结点并链接到对应原节点的后面4.2 处理复制的结点的随机指针random4.3 分离复制的链表结点和原链表结点并重新链接成为链表五、参考代码六、总结一、题目题目链接 ​​​​ ​ 题目链接&#xff1a;https://…

IDEA搭建vue-cli | vue-router | 排错思路、Webpack、Axios、周期、路由、异步、重定向

&#x1f497;wei_shuo的个人主页 &#x1f4ab;wei_shuo的学习社区 &#x1f310;Hello World &#xff01; Vue.js概述 Vue 是一套用于构建用户界面的渐进式JavaScript框架。 与其它大型框架不同的是&#xff0c;Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层…

C语言数据结构初阶(6)----链表常见OJ题

CSDN的uu们&#xff0c;大家好&#xff01;编程能力的提高不仅需要学习新的知识&#xff0c;还需要大量的练习。所以&#xff0c;C语言数据结构初阶的第六讲邀请uu们一起来看看链表的常见oj题目。移除链表元素原题链接&#xff1a;203. 移除链表元素 - 力扣&#xff08;Leetcod…

ENVI_IDL:批量获取影像文件各个波段的中值并输出为csv文件

01 实验数据诸多.float后缀的影像文件(但以ENVI默认格式存储)02 实验思路迭代循环所有影像文件所在的文件夹&#xff0c; 获取每一个float后缀的影像文件&#xff0c;并对每一个影像文件进行循环&#xff0c;获取循环文件的每一个波段影像的中值&#xff0c;最后将其输出为csv文…

设计模式之单例模式~

设计模式包含很多&#xff0c;但与面试相关的设计模式是单例模式&#xff0c;单例模式的写法有好几种&#xff0c;我们主要学习这三种—饿汉式单例&#xff0c;懒汉式单例、登记式单例,这篇文章我们主要学习饿汉式单例 单例模式&#xff1a; 满足要点&#xff1a; 私有构造 …

改进YOLO系列 | CVPR2023最新 PConv | 提供 YOLOv5 / YOLOv7 / YOLOv7-tiny 模型 YAML 文件

DWConv是Conv的一种流行变体,已被广泛用作许多神经网络的关键构建块。对于输入 I ∈ R c h w I \in R^{c \times h \times w} I∈

用chatgpt写insar地质灾害的论文,重复率只有1.8%,chatgpt4.0写论文不是梦

突发奇想&#xff0c;想用chatgpt写一篇论文&#xff0c;并看看查重率&#xff0c;结果很惊艳&#xff0c;说明是确实可行的&#xff0c;请看下图。 下面是完整的文字内容。 InSAR (Interferometric Synthetic Aperture Radar) 地质灾害监测技术是一种基于合成孔径雷达…

GPT-4,终于来了!

就在昨天凌晨&#xff0c;OpenAI发布了多模态预训练大模型GPT-4。 这不昨天一觉醒来&#xff0c;GPT-4都快刷屏了&#xff0c;不管是在朋友圈还是网络上都看到了很多信息和文章。 GPT是Generative Pre-trained Transformer的缩写&#xff0c;也即生成型预训练变换模型的意思。…

jupyter的安装和使用

目录 ❤ Jupyter Notebook是什么&#xff1f; notebook jupyter 简介 notebook jupyter 组成 网页应用 文档 主要特点 ❤ jupyter notebook的安装 notebook jupyter 安装有两种途径 1.通过Anaconda进行安装 2.通过pip进行安装 启动jupyter notebook ❤ jupyter …

5G(NR)信道带宽和发射带宽---频率资源

前言 查看此文之前建议先看看这篇 5G(NR)频率资源划分_nr运营商频段划分_达帮主的博客-CSDN博客NR频率有上面几个划分 &#xff0c;可以使用低于1GHz的频端&#xff0c;既可以使用高于30GHz高频端。使用频端高于30GHz那我们称之为高频或者毫米波。使用毫米波是5G网络区别于4G…

蓝桥冲刺31天之317

在这个时代&#xff0c;我们总是在比较&#xff0c;觉得自己不够好 其实不必羡慕别人的闪光点 每个人都是属于自己的限量版 做你喜欢并且擅长的事&#xff0c;做到极致 自然会找到自己独一无二的价值 鸟不跟鱼比游泳&#xff0c;鱼不跟鸟比飞翔 你我各有所长 A&#xff1a;组队…

【数学基础】你还不理解最大似然估计吗?一篇文章带你快速了解掌握

&#x1f4da;引言 &#x1f64b;‍♂️作者简介&#xff1a;生鱼同学&#xff0c;大数据科学与技术专业硕士在读&#x1f468;‍&#x1f393;&#xff0c;曾获得华为杯数学建模国家二等奖&#x1f3c6;&#xff0c;MathorCup 数学建模竞赛国家二等奖&#x1f3c5;&#xff0c…

JAVA并发编程之锁

1、乐观锁和悲观锁 1.1、悲观锁 认为自己在使用数据的时候一定有别的线程来修改数据&#xff0c;因此在获取数据的时候会加锁&#xff0c;确保数据不会别的线程修改。synchronized关键字和Lock的实现类都是悲观锁。适合写操作多的场景&#xff0c;先加锁可以保证写操作时数据…

leetcode刷题之回文链表

目录 做题思路 代码实现 1.找到链表的中间节点 2.反转中间节点之后的链表 3.判断倒置的后半部分的链表是否等于前半部分的链表 整体代码展示 总结&#xff1a; 这里是题目链接。 这道题目的意思是&#xff1a;判断该链表中后半部分倒置是否跟前半部分相同&#xff0c;如…

java 每日一练 (8)

文章目录1. 单选题2. 编程题1. 单选题 1. 下列选项中关于 java 中 super 关键字的说法正确的是 () A&#xff1a; super 关键字是在子类对象内部指代父类对象的引用. B &#xff1a; super 关键字不仅可以指代子类的直接父类&#xff0c;还可以直接指代父类的父类. C &#…

API-Server的监听器Controller的List分页失效

前言 最近做项目&#xff0c;还是K8S的插件监听器&#xff08;理论上插件都是通过API-server通信&#xff09;&#xff0c;官方的不同写法居然都能出现争议&#xff0c;争议点就是对API-Server的请求的耗时&#xff0c;说是会影响API-Server。实际上通过源码分析两着有差别&am…
最新文章