hdu 6038 | 2017 Multi-University Training Contest – Team 1 E Function (置换群找循环节)

http://acm.hdu.edu.cn/showproblem.php?pid=6038

题意:

给出两个序列 a 和 b ,求满足  f[i]= b_{f[a[i]]} 的函数个数。

思路:

分别找两个序列的循环节,这一点是比较容易想到的。

由于点都在0..n-1 或者0..m-1,因此没必要建图跑dfs找循环节,直接while就可以了。

然后发现一个循环节如果符合条件,那么对答案的贡献是循环节长度。

但是没有想清楚,什么才是符合条件的循环节。

结论是,b的循环节长度当且近当是A的循环节的长度的因子时,b的这个循环节会对答案贡献其长度的大小。

对于A的每个循环节,都是互不影响的。

而且我们只关心循环节的长度。

因此O(n)和O(m)的时间,处理出所有循环节的长度。

然后分别枚举累计答案即可。

但是我怎么感觉。。。这复杂度不太对啊。。。。

对于O(1E5)的序列。。我好像可以构造出1E5个长度为1的循环节?

那么1E5 * 1E5,1E10的复杂度了。。。

然而看了下官方题解。。。发现给出的复杂度分析是O(n+m)

?????????????????????

所以这是说。。。数据保证O(n*m) < O (n+m)了么。。。

这是面向数据解题。。还是说我哪里想错了啊。。。orz

 

 

 

 

hdu 6043 | 2017 Multi-University Training Contest – Team 1 K KazaQ’s Socks (循环节)

http://acm.hdu.edu.cn/showproblem.php?pid=6043

题意:

n双袜子标号1到n,初始在抽屉里,每天早晨穿一双标号最小的袜子,晚上把脏袜子放到盆里,如果放完之后喷子里已经有了n-1双脏袜子,那么就要洗,然后在第二天晚上放回抽屉里。问第k天穿的是标号为几的袜子。

思路:

手写了几个发现对于n双袜子,标号出现的情况是:

1,2,3…n,1,2,3…n-2,n-1,1,2,3…n-2,n

所以特判k<=n的情况然后算循环的次数即可。

 

 

广义Fibonacci数列找循环节 (二次剩余)

问题:给定,满足,求的循

环节长度。

原理见广义Fibonacci数列找循环节

这里只说做法

我们先写出递推式的特征式子   x^2 =ax + b,整理得到 x^2-ax-b=0求出 delta = a^2+4b

对于质因数小于等于delta的部分,我们选择暴力求循环节。

暴力求循环节的代码如下:

通常做法是先暴力求出来之后,写进一个表里。

通常不会有很多项。

对于质因数大于delta的部分,我们判断每个质因数是否是delta的二次剩余,如果是,枚举(prime-1)的因子,否则枚举2*(prime+1)的因子。

贴一个板子,需要注意如果是多个函数嵌套的形式,我们只需要从外向里,依次求循环节即可。

 

再补一个,更为常用的,求斐波那契循环节的板子:

 

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 2522 A simple problem (模拟,求小数循环节)

题目链接

题意:求一个小数的循环节…

思路:其实直接模拟就好…

模拟竖式计算…

这里用到一个小技巧。

由于多组数据,每次都memset一个bool会很慢,导致超时。

我们可以用一个人int数组来代替每次重置的bool数组,

 

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]