原神启动(递推,矩阵)

2024-01-22 23:52
文章标签 启动 矩阵 递推 原神

本文主要是介绍原神启动(递推,矩阵),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Part 1. 引子

求有多少 1 ∼ n 1\sim n 1n的排列,满足:

  • 进行 k k k轮原神排序后变为升序

具体的,一轮原神排序的定义为:

  • 指针 i i i [ 1 , n ) [1,n) [1,n)的顺序正序遍历,如果 a i > a i + 1 a_i>a_{i+1} ai>ai+1,则交换 a i a_i ai a i + 1 a_{i+1} ai+1
  • 指针 i i i ( 1 , n ] (1,n] (1,n]的顺序逆序遍历,如果 a i − 1 > a i a_{i-1}>a_i ai1>ai,则交换 a i − 1 a_{i-1} ai1 a i a_{i} ai

1 ≤ n ≤ 1 0 18 , 0 ≤ k ≤ 1 0 5 1\le n\le 10^{18},0\le k\le 10^5 1n1018,0k105

Part 2

首先转化成对 01 01 01序列排序,发现每次操作等价于将最左边的 1 1 1和最右边的 0 0 0进行交换,然后转二分图匹配模型,设 f i , j f_{i,j} fi,j表示决策了前 i i i个左部点和右部点,左部点和右部点分别有 j j j个点未匹配的方案数。转移如下:

f i , j = { f i − 1 , j − 1 + ( 2 j + 1 ) f i − 1 , j + ( j + 1 ) 2 f i − 1 , j + 1 0 ≤ j ≤ k 0 j > k f_{i,j}=\begin{cases}f_{i-1,j-1}+(2j+1)f_{i-1,j}+(j+1)^2f_{i-1,j+1}&0\le j\le k\\0&j>k\end{cases} fi,j={fi1,j1+(2j+1)fi1,j+(j+1)2fi1,j+100jkj>k

可能你看不懂上面的递推式是怎么来的,这是本题的难点之一,但是我们先略过这一部分。

考虑写出转移矩阵 A A A,那么答案就是 A n v A^nv Anv。注意到转移可以写成 k + 1 k+1 k+1阶矩阵,有结论:对于向量 v v v的任意一维,存在相同 k + 1 k+1 k+1阶递推式。

证明:考虑找出矩阵 A A A的特征多项式 ∑ c i A i = 0 \sum c_iA^i=0 ciAi=0,记 j j j处的答案向量为 f j f_j fj,则:

∑ c i A i f j = 0 \sum c_iA^if_j=0 ciAifj=0

考虑向量的任意一维(比如说这道题要求的是 f n , 0 f_{n,0} fn,0),则:

∑ c i f j + i , 0 = 0 \sum c_if_{j+i,0}=0 cifj+i,0=0

这样我们自然而然的得到了线性递推式。

现在考虑求特征多项式,即 det ( λ I − A ) \text{det}(\lambda I-A) det(λIA)。注意到其只在主对角线和副对角线上有值,记 d n d_n dn表示对应 n n n阶行列式的答案,展开得到:

d n = ( x − 2 n − 1 ) d n − 1 + ( n − 1 ) 2 d n − 2 d_n=(x-2n-1)d_{n-1}+(n-1)^2d_{n-2} dn=(x2n1)dn1+(n1)2dn2

注意这不是常系数齐次线性递推,而是若干矩阵的乘积:

M i = [ 0 ( i − 1 ) 2 1 x − 2 i − 1 ] M_i=\begin{bmatrix}0&(i-1)^2\\1&x-2i-1\end{bmatrix} Mi=[01(i1)2x2i1]

现在要求 ∏ i = 1 k + 1 M i \prod_{i=1}^{k+1}M_i i=1k+1Mi,可以直接分治求,复杂度 O ( k log ⁡ 2 k ) O(k\log^2 k) O(klog2k)

最后用著名的 Bostan-Mori 算法求解常系数齐次线性递推的第 n n n项即可。

如果你不会这个

简单练习题:[ABC300Ex] Fibonacci: Revisited

总复杂度 O ( k log ⁡ k log ⁡ n + k log ⁡ 2 k ) O(k\log k\log n+k\log^2 k) O(klogklogn+klog2k)

代码:

//很抱歉这份代码咕掉了。只能期待Hagasei-Chan给出的std了。

Part 3

还有一个题的递推式大概是这样的:

f i , 0 = f i − a , 0 + f i − a , 2 + f i − a , 3 f i , 1 = f i − b , 1 + f i − b , 2 + f i − b , 3 f i , 2 = f i − c , 0 + f i − c , 1 + f i − c , 2 f i , 3 = f i − d , 0 + f i − d , 1 + f i − d , 3 f_{i,0}=f_{i-a,0}+f_{i-a,2}+f_{i-a,3}\\ f_{i,1}=f_{i-b,1}+f_{i-b,2}+f_{i-b,3}\\ f_{i,2}=f_{i-c,0}+f_{i-c,1}+f_{i-c,2}\\ f_{i,3}=f_{i-d,0}+f_{i-d,1}+f_{i-d,3} fi,0=fia,0+fia,2+fia,3fi,1=fib,1+fib,2+fib,3fi,2=fic,0+fic,1+fic,2fi,3=fid,0+fid,1+fid,3

现在要求 f n , 0 + f n , 1 + f n , 2 + f n , 3 f_{n,0}+f_{n,1}+f_{n,2}+f_{n,3} fn,0+fn,1+fn,2+fn,3

可以考虑写成生成函数的形式然后硬解方程,这样解出来应该是封闭形式,可以直接上 Bostan-Mori 。

但是其实这玩意也可以写成矩阵转移的形式,然后暴力展开行列式。因为有值的地方很少所以也是可行的。

Part 4

总结:我是属于连递推式都看不出来的那种

bot题谁做啊?bot题谁做啊?bot题谁做啊?bot题谁做啊?

这篇关于原神启动(递推,矩阵)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/634621

相关文章

Android里面的Service种类以及启动方式

《Android里面的Service种类以及启动方式》Android中的Service分为前台服务和后台服务,前台服务需要亮身份牌并显示通知,后台服务则有启动方式选择,包括startService和b... 目录一句话总结:一、Service 的两种类型:1. 前台服务(必须亮身份牌)2. 后台服务(偷偷干

Windows设置nginx启动端口的方法

《Windows设置nginx启动端口的方法》在服务器配置与开发过程中,nginx作为一款高效的HTTP和反向代理服务器,被广泛应用,而在Windows系统中,合理设置nginx的启动端口,是确保其正... 目录一、为什么要设置 nginx 启动端口二、设置步骤三、常见问题及解决一、为什么要设置 nginx

springboot启动流程过程

《springboot启动流程过程》SpringBoot简化了Spring框架的使用,通过创建`SpringApplication`对象,判断应用类型并设置初始化器和监听器,在`run`方法中,读取配... 目录springboot启动流程springboot程序启动入口1.创建SpringApplicat

树莓派启动python的实现方法

《树莓派启动python的实现方法》本文主要介绍了树莓派启动python的实现方法,文中通过图文介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、RASPBerry系统设置二、使用sandroidsh连接上开发板Raspberry Pi三、运

SpringBoot项目启动后自动加载系统配置的多种实现方式

《SpringBoot项目启动后自动加载系统配置的多种实现方式》:本文主要介绍SpringBoot项目启动后自动加载系统配置的多种实现方式,并通过代码示例讲解的非常详细,对大家的学习或工作有一定的... 目录1. 使用 CommandLineRunner实现方式:2. 使用 ApplicationRunne

bat脚本启动git bash窗口,并执行命令方式

《bat脚本启动gitbash窗口,并执行命令方式》本文介绍了如何在Windows服务器上使用cmd启动jar包时出现乱码的问题,并提供了解决方法——使用GitBash窗口启动并设置编码,通过编写s... 目录一、简介二、使用说明2.1 start.BAT脚本2.2 参数说明2.3 效果总结一、简介某些情

MySQL数据库宕机,启动不起来,教你一招搞定!

作者介绍:老苏,10余年DBA工作运维经验,擅长Oracle、MySQL、PG、Mongodb数据库运维(如安装迁移,性能优化、故障应急处理等)公众号:老苏畅谈运维欢迎关注本人公众号,更多精彩与您分享。 MySQL数据库宕机,数据页损坏问题,启动不起来,该如何排查和解决,本文将为你说明具体的排查过程。 查看MySQL error日志 查看 MySQL error日志,排查哪个表(表空间

springboot3打包成war包,用tomcat8启动

1、在pom中,将打包类型改为war <packaging>war</packaging> 2、pom中排除SpringBoot内置的Tomcat容器并添加Tomcat依赖,用于编译和测试,         *依赖时一定设置 scope 为 provided (相当于 tomcat 依赖只在本地运行和测试的时候有效,         打包的时候会排除这个依赖)<scope>provided

内核启动时减少log的方式

内核引导选项 内核引导选项大体上可以分为两类:一类与设备无关、另一类与设备有关。与设备有关的引导选项多如牛毛,需要你自己阅读内核中的相应驱动程序源码以获取其能够接受的引导选项。比如,如果你想知道可以向 AHA1542 SCSI 驱动程序传递哪些引导选项,那么就查看 drivers/scsi/aha1542.c 文件,一般在前面 100 行注释里就可以找到所接受的引导选项说明。大多数选项是通过"_

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=