本文从WordPress迁移而来, 查看全部WordPress迁移文章
数学推公式 or 矩阵快速幂
【2013多校联合训练第一场】
题意:比较易懂的题意,给出一个n,可以由多种方式分解它
1 | 4=1+1+1+1 |
然后给定一个数字m,问在这里分解中m这个数字出现了几次
多校的第一场,看到这题,觉得答案肯定很大,没想法,但是觉得这么的数据,肯定是数学题,第一反应是,找规律,所以写了一个dfs的暴力程序,把1<=n<=20,对于每个n的每个因子出现了几次都打印出来,然后发现了规律
下面给出n<=10的时候打出来的表
1 | n = 1 |
很明显看到是一个数列,但是这个数列有什么规律呢?我们这样定义项数,对于n,因子x=n为第1项,x=n-1为第2项………….x=1为第n项
第1,2,3项是分别是1,2,5,我们从第4项看看会怎样
1 | f[4] = 12 = 5 + 2*2 + 3 |
规律就很明显了,f[n] = f[n-1] + 2 f[n-2] + 3 2^(n-4);
这种递推式子,如果就这样推上去,复杂度是O(n),但是留意到这题数据很大为10^9,所以不能线性推,那么就构造矩阵吧
对于矩阵[ f[n-1] , f[n-2] , 3*2^(n-4) ] ,我们构造一个矩阵[ A ],两者进行一次矩阵乘法后能得到
[ f[n] , f[n-1] , 3*2^(n-3) ]
[ A ]还是很容易想的,就是
1 | | 1 1 0 | |
那么要推出后面m项,就乘上m个[ A ]即可,而m个[A]相乘,就可以利用矩阵快速幂
一开始由[ f[3] , f[2] , 3] = [ 5 , 2 , 3],要推第k项的话
就是[ 5 , 2 , 3] [A]^(k-3) = [f[k] , f[k-1] , 32^(k-3)],我们只取出f[k]即可
至于矩阵快速幂怎么写这里就不说了,道理就是二分
比赛的时候写的是迭代版的,回来后把递归版的也写了
不过赛后同学说不用这么麻烦,因为公式还没有推彻底,推彻底后,就一个公式可以了
不过也好,当做练习了一下矩阵快速幂和构造矩阵
!!!!!!!!!!!!!!!!注意一个大水坑,对于一个数字n,查询x出现了几次,这个x可能打过n,答案就是0,就是被这大水坑搞了4次wa!!!!!!!
迭代版
1 | /* |
递归版
1 | /* |