题目链接 题意： 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 …

题目链接 题意：A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n). 思路：矩阵加速线性递推式。 这题第一次看是2012年11月2333，当时用pascal写的 /* *********************************************** Author :111qqz Created Time :Mon 31 Oct 2016 …

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

题目链接 题意：给出了一段伪代码。分析得知其实就是f[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2] 思路：一眼题，和hdu4549很类似hdu4549解题报告 不同的是这道题中p不一定是质数（其实不是也无所谓啊...hdu4549只不过是因为1E9+7是指数，又用费马小定理化简了一下,这道理%phi(p)即可） 还有这道题让我知道了 首先我们知道指数循环节公式，也就是所谓的降幂公式为：**a^x = a^(x mod phi(c)+phi(c)) (mod c) x=phi(c)，（ps:后面的限制条件，在x** 括号里的话是错误的。只有当x<phi(c)的时候，这个公式才成立。 这道题就是反例，不加 …

题目链接 题意： Assume that f(0) = 1 and 0^0=1. f(n) = (n)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x). 思路：指数循环节。 trick点在于0^0=1这点。 比较容易想到的一层是ksm的时候特判。 比较不容易想到的一层是，0作为底数的时候，可能出现0^a在用降幂公式加速后，出现0^0。 举个例子： 680 80 phi(80)=32,恰好是8^6的因子 而0^(8^6)答案应该为0，用降幂公式加速后变成了0^0， …

题目链接 题意：给出b,p,m（( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 – 1 )）,问满足图中条件的n有多少个。 思路：这题由于对p没有限制，所以细节多一些，需要讨论。 首先我们知道指数循环节公式，也就是所谓的降幂公式为：a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c)，（ps:后面的限制条件，在x<phi(c)的时候，该式子依然正确，只不过增加了运算复杂度。。。？ 存疑） 然后我们只需要对n分两种情况讨论。 第一种是n<t ,第二种是n>=t (t = min{x| x! % …

题目链接 题意：求一个楼梯数%m的大小。 思路：指数循环节。 需要注意的是，模数只有最外层是m，每往里一层，模数都变成m=phi(m) 所以可以写个dfs或者先预处理出每一层m存一下。 记得考虑n=1的特殊情况。 /* *********************************************** Author :111qqz Created Time :Wed 26 Oct 2016 07:07:27 PM CST File Name :code/uva/10692.cpp ************************************************ */ #include …

题目链接 题意：定义s(k)为将n分成k个正整数的划分数，给出n，问s(1) + s(2) + ... + s(n-1) + s(n)是多少，结果9+7，其中n<=10^100000。 思路：首先化简要求的式子。 根据隔板法_维基百科 现在有10个球，要放进3个盒子里 ●●●●●●●●●● 隔2个板子，把10个球被隔开成3个部分 ●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、...... 如此类推，10个球放进3个盒子的方法总数为{ n个球放进k个盒子的方法总数为{ 问题等价于求{ 的可行解数， …

题意：M斐波那契数列F[n]是一种整数数列，它的定义如下： F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n，你能求出F[n]的值吗？ 思路：观察发现。。。F[n] = a^(fib(n-1)) * b ^ (fib(n)) 此处要用到指数循环节的知识： 111qqz_指数循环节学习笔记 a^n ≡ a^(n % Phi(M) + Phi(M)) (mod M) (n >= Phi(M)) 然后 因为1000000007是质数，对于任意的x,有gcd(x,1000000007) = 1，所以可以结合费马小定理化简上式： a^n ≡ …

资料先行： 指数循环节证明 指数循环节2 对指数循环节的一些理解 挂了一点题目，写完来写总结。 vjudge_不会指数循环节的111qqz 写完了。 首先要注意的是： 首先我们知道指数循环节公式，也就是所谓的降幂公式为：**a^x = a^(x mod phi(c)+phi(c)) (mod c) x=phi(c)，（ps:后面的限制条件，在x）** 括号里的话是错误的。当x<phi(c)时，该式子是错误的。 之前一直没出问题是因为数据水。 参考题目：hdu3221解题报告