hdu 4794 Arnold (二次剩余,斐波那契循环节)

题意:

给定一个 NN(N4e9) 的矩阵,现在经过这样一个变换:将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0x<N,0y<N) 现在求经过多少次这样的变换之后在回到 NN 的原始矩阵。

思路:

在模n的剩余系下可以写成(fib(n)x+fib(n+1)y,fib(n+1)x+fib(n+2)y)的形式fib(n)表示Fibonacci数列的第n项

所以就成了斐波那契数列循环节。。经典题。注意会爆long long,要用ULL

又写了遍板子,去年的东西都忘得差不多了orz

 

 

acdream oj 1124 喵喵的遗憾 (斐波那契数列循环节)

题目链接

题意:

F0 = 1 , F1 = 1 , F2 = 2 , Fn = Fn-1+Fn-2

求:

FFFn Mod P

( 也就是 F[ F[ F[n] ] ]  % P )

思路:原来这是适牛出的题2333.

需要注意的是p可能为1,因此n==0或者1的时候,特判要输出1%p而不是1.

其他的没了。就是求斐波那契数列循环节的经典做法。

 

hdu 3978 Evil teacher’s Final Problem (斐波那契数列的循环节)

题意:now he let you calculate G(n,k) .Here G(n,0) = f(n) , G(n,i) = f( G(n,i-1) ) (k >= i >= 1).其中f是斐波那契数列。

思路:其实就是hdu 4291的加强版:hdu 4291 解题报告

开一个1E4的数组存一下每一层的循环节就好了。

http://vjudge.net/contest/139429#overview  告一段落,完结撒花!

 

 

hdu 4291 A Short problem (矩阵快速幂+广义斐波那契循环节||暴力找循环节)

题目链接

题意:

Given n (1 <= n <= 1018), You should solve for

g(g(g(n))) mod 109 + 7

where

g(n) = 3g(n – 1) + g(n – 2)
 

g(1) = 1
 

g(0) = 0
思路:找循环节。首先由于模数固定,可以暴力一下找到循环节。

得到1E9+7的循环节是222222224,222222224的循环节是183120.

然后三次矩阵快速幂就行了。

需要注意每次都要判断那一层的n是否为0和1。

暴力解法:

再来一个比较一般的做法:

参考递推式循环节

Acdreamer的博客_广义Fibonacci数列找循环节

摘重点:

今天早上起来后,看了下代码,为什么要判断5是不是p的模二次剩余呢,为什么是5呢

想了想,5对于斐波那契数列来讲,不就是x^2=x+1的delta么,那么这题的递推式是x^2=3*x+1,delta=3*3+4=13,然后我就把勒让德符号判断二次剩余那里改成13,然后对应的暴力出13及13以内的素数对应的循环节,交了一发,AC了

 

 

      所以综上所述:

是模的二次剩余时,枚举的因子

是模的二次非剩余时,枚举的因子

对于第二种非剩余的情况,理论上是枚举(p+1)(p-1)的因子,实际上常常只是枚举2*(p+1)的因子

对于c=5的情况,是有定理:

screenshot-from-2016-10-31-21-23-45

不过对于c不等于5的情况。。。该结论是否一定成立呢…感觉不是很好证,求指教。

 

hdu 3977 Evil teacher (斐波那契数列循环节)

题目链接

题意:f[0] = 1,f[1] = 1,f[i] = f[i-1] + f[i-2] (i>=2),问最小的m满足f[n]%p==f[n+m]%p

思路:求斐波那契数列循环节。

参考了Acdreamer的博客_Fib数模n的循环节

对于一个正整数n,我们求Fib数模n的循环节的长度的方法如下:

(1)把n素因子分解,即

(2)分别计算Fib数模每个的循环节长度,假设长度分别是

(3)那么Fib模n的循环节长度

从上面三个步骤看来,貌似最困难的是第二步,那么我们如何求Fib模的循环节长度呢?

     这里有一个优美的定理:Fib数模的最小循环节长度等于,其中表示Fib数模素数的最小循环节长度。可以看出我们现在最重要的就是求

对于求我们利用如下定理:

   如果5是模的二次剩余,那么循环节的的长度是的因子,否则,循环节的长度是的因子。

顺便说一句,对于小于等于5的素数,我们直接特殊判断,loop(2)=3,loop(3)=8,loop(5)=20。

那么我们可以先求出所有的因子,然后用矩阵快速幂来一个一个判断,这样时间复杂度不会很大。

这道题是模板题。博客中的模板代码很好理解…

换成了自己比较熟悉的矩阵构造方式,以及代码风格。

需要注意的是下标是从0开始的,当验证k是否为循环节的时候,应该验证f[k]和f[k+1]

 

 

 

BZOJ 4547: Hdu5171 小奇的集合 (矩阵快速幂)

4547: Hdu5171 小奇的集合

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 263  Solved: 113
[Submit][Status][Discuss]

Description

 有一个大小为n的可重集S,小奇每次操作可以加入一个数a+b(a,b均属于S),求k次操作后它可获得的S的和的最大

值。(数据保证这个值为非负数)

Input

第一行有两个整数n,k表示初始元素数量和操作数,第二行包含n个整数表示初始时可重集的元素。

对于100%的数据,有 n<=10^5,k<=10^9,|ai|<=10^5

Output

输出一个整数,表示和的最大值。答案对10000007取模。

Sample Input

2 2
3 6

Sample Output

33

HINT

Source

思路:同hdu 5171的区别在于,a可能为负数。

同样是设a0为次大值,a1为最大值。

根据a0,a1的正负分类讨论。

如果a1<0(此时a0一定也小于0)那么每次操作都是a0+a1,因为越加越小。

如果a0<0,需要计算需要几次运算,使得a0>=0。设需要num次。

原因是,类斐波那契数列的性质可以对于正数,也可以对于负数,但是如果有正数有负数,性质是不满足的。

因此如果num>k,说明一直都是负数,直接运算即可,如果num<=k,就需要先把负数部分用等差数列的方法处理掉。

然后再用矩阵快速幂的方法计算剩下的k-num次。

 

hdu 5171 GTY’s birthday gift (矩阵快速幂)

题目链接

题意:给出n,k,以及n个正数,把n个数放在一个集合里,进行k次操作,每次操作取最大的数和次大的数放进集合。问k次操作结束后,集合中所有数的和。

思路:假设初始时刻,次大和最大分别为a0,a1,那么得到的就是一个类斐波那契数列。初始为a0,a1,fn = fn-1 + fn

最后求和。

 

screenshot-from-2016-10-25-18-48-09

利用这个性质。。。

我们直接构造完矩阵。。。求出F(n+2)即可。。

需要注意。。。矩阵中每一项是小于1E7+7的。。。矩乘的时候会爆int…

所以mat要用LL存。。我好傻啊。。。