Codeforces Round 113 (Div. 2)E. Tetrahedron(dp、递推)

文章目录

  • 题面
  • 链接
  • 题意
  • 题解
  • 代码
  • 总结

题面

image

链接

E. Tetrahedron

题意

从一个顶点出发走过路径长度为n回到出发点的方案总数

题解

考虑dp
f [ i ] [ 0 ∣ 1 ∣ 2 ∣ 3 ] f[i][0|1|2|3] f[i][0∣1∣2∣3]:走了i步,现在在j点的方案总数
转移:
f [ i ] [ 0 ] = f [ i − 1 ] [ 1 ] + f [ i − 1 ] [ 2 ] + f [ i − 1 ] [ 3 ] f[i][0]=f[i-1][1]+f[i-1][2]+f[i-1][3] f[i][0]=f[i1][1]+f[i1][2]+f[i1][3]
f [ i ] [ 1 ] = f [ i − 1 ] [ 0 ] + f [ i − 1 ] [ 2 ] + f [ i − 1 ] [ 3 ] f[i][1]=f[i-1][0]+f[i-1][2]+f[i-1][3] f[i][1]=f[i1][0]+f[i1][2]+f[i1][3]
f [ i ] [ 2 ] = f [ i − 1 ] [ 0 ] + f [ i − 1 ] [ 1 ] + f [ i − 1 ] [ 3 ] f[i][2]=f[i-1][0]+f[i-1][1]+f[i-1][3] f[i][2]=f[i1][0]+f[i1][1]+f[i1][3]
f [ i ] [ 3 ] = f [ i − 1 ] [ 0 ] + f [ i − 1 ] [ 1 ] + f [ i − 1 ] [ 2 ] f[i][3]=f[i-1][0]+f[i-1][1]+f[i-1][2] f[i][3]=f[i1][0]+f[i1][1]+f[i1][2]

代码

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_backusing namespace std;
const int mod=1e9+7;
int dp[3][5];
void solve()
{int n;cin>>n;dp[0][0]=1;rep(i,1,n){int u=i&1,v=(i-1)&1;dp[u][0]=(dp[v][1]+dp[v][2]+dp[v][3])%mod;dp[u][1]=(dp[v][0]+dp[v][2]+dp[v][3])%mod;dp[u][2]=(dp[v][0]+dp[v][1]+dp[v][3])%mod;dp[u][3]=(dp[v][0]+dp[v][1]+dp[v][2])%mod;}cout<<dp[n&1][0]<<endl;
}signed main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);int _;
//	cin>>_;
//	while(_--)solve();return 0;
}

总结

一定要开long long,容易忘直接 d e f i n e l o n g l o n g i n t define long long int definelonglongint
爆空间开滚动数组优化。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux进程间通信】用管道实现简单的进程池、命名管道

【Linux进程间通信】用管道实现简单的进程池、命名管道 目录 【Linux进程间通信】用管道实现简单的进程池、命名管道为什么要实现进程池&#xff1f;代码实现命名管道创建一个命名管道 理解命名管道匿名管道与命名管道的区别命名管道的打开规则 作者&#xff1a;爱写代码的刚子…

【C语言进阶】深度剖析数据在内存中的存储--上

1. C语言中的数据类型的简单介绍 注&#xff1a;C99标准里面&#xff0c;定义了bool类型变量。这时&#xff0c;只要引入头文件stdbool.h &#xff0c;就能在C语言里面正常使用bool类型。 1.1 在C语言中各类型所占内存空间的大小如下 char类型的数据类型大小为1字节即8比特位。…

蓝桥杯每日一题------背包问题(三)

前言 之前求的是在特点情况下选择一些物品让其价值最大&#xff0c;这里求的是方案数以及具体的方案。 背包问题求方案数 既然要求方案数&#xff0c;那么就需要一个新的数组来记录方案数。动态规划步骤如下&#xff0c; 定义dp数组 第一步&#xff1a;缩小规模。考虑n个物品…

云原生容器化-4 Docker仓库

1.Docker仓库 1.1 Docker Hub docker仓库用于存放docker镜像&#xff0c;可以分为公用和私有两种。Docker Hub是全球公用的仓库&#xff0c;因服务器在国外&#xff0c;国内基本不可以&#xff1b;一般需要配置阿里、腾讯等加速器。公司内部而言&#xff0c;可以搭建私有的Do…

使用 devc++ 开发 easyx 实现 Direct2D 交互

代码为 codebus 另一先生的 文案 EasyX 的三种绘图抗锯齿方法 - CodeBus 这里移植到 devc 移植操作如下&#xff1a; 调用dev 的链接库方式&#xff1a; project -> project option -> 如图所示 稍作修改的代码。 #include <graphics.h> #include <d2d1.…

【数据结构】13:表达式转换(中缀表达式转成后缀表达式)

思想&#xff1a; 从头到尾依次读取中缀表达式里的每个对象&#xff0c;对不同对象按照不同的情况处理。 如果遇到空格&#xff0c;跳过如果遇到运算数字&#xff0c;直接输出如果遇到左括号&#xff0c;压栈如果遇到右括号&#xff0c;表示括号里的中缀表达式已经扫描完毕&a…

C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统(2)折线图显示

对上一篇的工作C学习笔记 | 基于Qt框架开发实时成绩显示排序系统1-CSDN博客继续优化&#xff0c;增加一个显示运动员每组成绩的折线图。 1&#xff09;在Qt Creator的项目文件&#xff08;.pro文件&#xff09;中添加对Qt Charts模块的支持&#xff1a; QT charts 2&#xf…

STM32WLE5JC

Sub-GHz 无线电介绍 sub-GHz无线电是一种超低功耗sub-GHz无线电&#xff0c;工作在150-960MHz ISM频段。 在发送和接收中采用LoRa和&#xff08;G&#xff09;FSK调制&#xff0c;仅在发送中采用BPSK/(G)MSK调制&#xff0c;可以在距离、数据速率和功耗之间实现最佳权衡。 这…

微软 CMU - Tag-LLM:将通用大语言模型改用于专业领域

文章目录 一、前言二、主要内容三、总结 &#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 一、前言 论文地址&#xff1a;https://arxiv.org/abs/2402.05140 Github 地址&#xff1a;https://github.com/sjunhongshen/Tag-LLM 大语言模型&#xff08…

Ubuntu Desktop - scrolling (Terminal 缓存更多终端历史输出内容)

Ubuntu Desktop - scrolling [Terminal 缓存更多终端历史输出内容] 1. ubuntu-14.04.5-desktop-amd64.iso2. ubuntu-16.04.3-desktop-amd64.isoReferences Terminal -> 右键 Profiles -> Profile Preferences 1. ubuntu-14.04.5-desktop-amd64.iso 2. ubuntu-16.04.3-de…

理解JAVA命名和目录接口(JNDI)

理解JAVA命名和目录接口(JNDI) 考虑访问网站的场景,Web用户要求记住四字节的IP地址而不是有意义的名称。例如,假设Web用户用123.23.3.123而不是hotmail.com访问hotmail网站。在这种情形下,Web用户难以记住不同的IP地址来访问不同的网站。因此,要使其变得对Web用户简单方…

【开源】SpringBoot框架开发APK检测管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 开放平台模块2.3 软件档案模块2.4 软件检测模块2.5 软件举报模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 开放平台表3.2.2 软件档案表3.2.3 软件检测表3.2.4 软件举报表 四、系统展示五、核心代…

基于RBF神经网络的自适应控制器simulink建模与仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1自适应控制器 4.2 RBF神经网络模型 5.完整程序 1.程序功能描述 在simulink中&#xff0c;使用S函数编写基于RBF神经网络的自适应控制器&#xff0c;然后实现基于RBF神经网络的自适应控制…

HCIA-HarmonyOS设备开发认证V2.0-3.2.轻量系统内核基础-任务管理

目录 一、任务管理1.1、任务状态1.2、任务基本概念1.3、任务管理使用说明1.4、任务开发流程1.5、任务管理接口 坚持就有收获 一、任务管理 从系统角度看&#xff0c;任务是竞争系统资源的最小运行单元。任务可以使用或等待CPU、使用内存空间等系统资源&#xff0c;并独立于其它…

【多模态】27、Vary | 通过扩充图像词汇来提升多模态模型在细粒度感知任务(OCR等)上的效果

文章目录 一、背景二、方法2.1 生成 new vision vocabulary2.1.1 new vocabulary network2.1.2 Data engine in the generating phrase2.1.3 输入的格式 2.2 扩大 vision vocabulary2.2.1 Vary-base 的结构2.2.2 Data engine2.2.3 对话格式 三、效果3.1 数据集3.2 图像细粒度感…

双场板功率GaN HEMT电容模型以精确模拟开关行为

标题&#xff1a;Capacitance Modeling in Dual Field-Plate Power GaN HEMT for Accurate Switching Behavior&#xff08;TED.16年&#xff09; 摘要 本文提出了一种基于表面电位的紧凑模型&#xff0c;用于模拟具有栅极和源极场板&#xff08;FP&#xff09;结构的AlGaN/G…

【Python网络编程之Ping命令的实现】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;Python开发技术 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; Python网络编程之Ping命令的实现 代码见资源&#xff0c;效果图如下一、实验要求二、协议原理2…

redis-sentinel(哨兵模式)

目录 1、哨兵简介:Redis Sentinel 2、作用 3、工作模式 4、主观下线和客观下线 5、配置哨兵模式 希望能够帮助到大家&#xff01;&#xff01;&#xff01; 1、哨兵简介:Redis Sentinel Sentinel(哨兵)是用于监控redis集群中Master状态的工具&#xff0c;其已经被集成在re…

问山海——天涯海角——桃花渊boss攻击顺序

文章目录 桃花渊代码代码解读代码执行结果攻击顺序示意图 桃花渊 规划击杀各个boss顺序。 副本持续时间为30分钟&#xff0c;每个地方的boss被打死后&#xff0c;需要一定时间才能重新刷新。 只考虑其中两种boss&#xff0c;龟将和龟龙。各有四个。 其中我从一个boss地点到…

CentOS 7.9安装Tesla M4驱动、CUDA和cuDNN

正文共&#xff1a;1333 字 21 图&#xff0c;预估阅读时间&#xff1a;2 分钟 上次我们在Windows上尝试用Tesla M4配置深度学习环境&#xff08;TensorFlow识别GPU难道就这么难吗&#xff1f;还是我的GPU有问题&#xff1f;&#xff09;&#xff0c;但是失败了。考虑到Windows…