题目概述:
给定了函数f的表达式与函数g的表达式,给了T(T<=100)次询问,每次询问一个数n(n<=1e12),求g(n)的值,最终答案对1e9+7取模。
tag:
记忆化,递归,数学
题解:
首先我们需要知道取模的常识:
1. (a+b)%mod=(a%mod+b%mod)%mod
2. a*b%mod=a%mod*b%mod
3. (a+b)%mod=(a+b+mod)%mod(这个很重要,因为在取模过程中,即便是sum原本是累加的,其本身数值比a大,但是经过取模之后,sum可能小于a,因而,当计算(sum-a)%mod的时候就需要写成(sum-a+mod)%mod来避免这种出现负数的情况)
我们首先考虑 f(x) 怎么计算,我们可以很容易地写出:
但是,写过递归的都知道,这将会产生一棵二叉树,我们粗略的估计他的计算次数
假如 f(x)=f(x/3)+f(x/3),那么我们只有在算到x=0的时候才会抵达递归出口,这棵二叉树的深度就大概是log(3)x,而这是一棵类似于满二叉树的树,除了最后一层外的每一层的点都会被填满,那么当n=1e12的时候,树的深度是12log(3)10,约等于25,那么我们就需要计算pow(2,25)次,而原表达式的复杂度肯定是更高的。不是,查询100次f(n)我就gg了,那还写个集贸啊?
我们以计算 f(6)为例,观察下图,我们就会发现f(1)被计算了多次,而当n越大,我们重复计算的就越多,实际上,不管是不断除以2还是不断除以3,一个数n顶多计算log2(n)次和log3(n)次,如果不重复计算的话,我们计算f(n)的时间复杂度肯定是要小于log2(n)+log3(n)的。所以,为了避免重复的计算我们便需要对其记忆化。
修正代码:
这样的话,计算过的数值就不会重复计算了
f(n)的问题解决了,那么我们就可以去解决g(n)了,g(n)是个求和,而求和本身的时间复杂度就是O(n)的,我们使用强硬的手段必然会T飞掉。由于表达式本身的复杂度有问题,我们就要去想想如何对表达式进行进一步的简化,我们可以带入f(x)=f(x/2)+f(x/3)。步骤如下:
在得到了这个式子之后我们会发现,g(x)与f(x)递归式表达式的区别也就在于多了点杂项,但是,即便每次都要计算杂项,对于每一项的计算也都是log的,而实际的复杂度也只是Alog(n) (这里的A是个小常数),具体写法参见AC代码。
AC代码:
标签:复杂度,树脂,P2084,计算,sum,mod,我们,表达式,LevOJ From: https://blog.csdn.net/2301_79921853/article/details/143178746