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） …

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的情况然后算循环的次数即可。 /* *********************************************** Author :111qqz Created …

**问题：**给定 ，满足 ，求 的循 环节长度。 原理见广义Fibonacci数列找循环节 这里只说做法 我们先写出递推式的特征式子 x^2 =ax + b,整理得到 x^2-ax-b=0求出 delta = a^2+4b 对于质因数小于等于delta的部分，我们选择暴力求循环节。 暴力求循环节的代码如下： int get_loop( LL p) //暴力得到不大于13的素数的循环节。 { LL a,b,c; a = 0 ; b = 1 ; for ( int i = 2; ; i++) { c = (a+3*b%p)%p; //此处为递推式 a = b; b = c; if (a==0&&b==1) return …

题目链接 题意： 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. 其他的没了。就是求斐波那契数列循环节的经典做法。 /* *********************************************** Author :111qqz Created Time :Thu 03 Nov 2016 08:09:26 AM CST File Name :1124.cpp …

题意：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 告一段落，完结撒花！ /* *********************************************** Author :111qqz Created Time :Tue 01 Nov 2016 …

题目链接 题意：求一个小数的循环节... 思路：其实直接模拟就好... 模拟竖式计算... 这里用到一个小技巧。 由于多组数据，每次都memset一个bool会很慢，导致超时。 我们可以用一个人int数组来代替每次重置的bool数组, /* *********************************************** Author :111qqz Created Time :Tue 01 Nov 2016 08:00:49 PM CST File Name :code/hdu/2522.cpp ************************************************ */ #include …

题目链接 题意： 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。 暴力解法： /* *********************************************** Author :111qqz …

题目链接 题意：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数模素数 的最小循环节长度。可以看出我们 …