111qqz的小窝

老年咸鱼冲锋!

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 1005 Number Sequence (矩阵快速幂加速线性递推式)

题目链接

题意: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写的

 

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]

 

 

 

hdu 3221 Brute-force Algorithm (矩阵快速幂+指数循环节)

题目链接

 

题意:给出了一段伪代码。分析得知其实就是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<phi(c)的时候,该式子依然正确,只不过增加了运算复杂度。。。? 存疑)

括号里的话是错误的。只有当x<phi(c)的时候,这个公式才成立。

这道题就是反例,不加判断会wa。

 

 

 

hdu 2837 Calculation (指数循环节+欧拉函数)

题目链接

题意:

Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^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,答案变成了1,结果错误
究其原因,是因为这道题中底数可能有0以及0^0是题目中定义的运算。
解决办法是ksm的结果判断一下,如果是0就加mod。

 

hdu 4335 What is N? (指数循环节+欧拉函数)

题目链接

题意:给出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! % phi(P)==0})

由于t不会很大。。前一种直接暴力。。。

后一种用降幂公式搞之。。。

 

 

uva 10692 Huge Mods (欧拉函数,指数循环节)

题目链接

题意:求一个楼梯数%m的大小。

思路:指数循环节。

需要注意的是,模数只有最外层是m,每往里一层,模数都变成m=phi(m)

所以可以写个dfs或者先预处理出每一层m存一下。

记得考虑n=1的特殊情况。

 

 

hdu 4704 Sum (隔板法,指数循环节,费马小定理)

题目链接

题意:定义s(k)为将n分成k个正整数的划分数,给出n,问s(1) + s(2) + … + s(n-1) + s(n)是多少,结果%1E9+7,其中n<=10^100000。

思路:首先化简要求的式子。

根据隔板法_维基百科

现在有10个球,要放进3个盒子里

●●●●●●●●●●

隔2个板子,把10个球被隔开成3个部分

●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、……

如此类推,10个球放进3个盒子的方法总数为{{\binom {10-1}{3-1}}={\binom {9}{2}}=36

n个球放进k个盒子的方法总数为{{\binom {n-1}{k-1}}

问题等价于求{x_{1}+x_{2}+...+x_{k}=n的可行解数,其中x_{1},x_{2},...,x_{k}正整数

 

于是问题转化成:

n个木棍,n-1个缝,

分成1份则是C(n-1,0);

分成2份则是C(n-1,1);

分成3份则是C(n-1,2);

分成n份则是C(n-1,n-1);

ans = sum( C(n-1,i) ) (0<=i<=n-1)

=2^(n-1);

 

这是我能理解的得到2^(n-1)的方式。。。

看到有好多人说这个结论是显然的。。。求指教(说这是个结论记住就好的就算了23333)

接下来,就是求A=2^(n-1)%1E9+7的问题了。。。

根据指数循环节公式A=2^((n-1)%(mod-1))*2^(mod-1)%mod (其中mod=1E9+7)

由于gcd(2,1E9+7)=1,根据费马小定理2^(mod-1)%mod=1,因此A=2^((n-1)%(mod-1))

然后快速幂搞之。

 

 

 

hdu 4549 M斐波那契数列 (矩阵快速幂+费马小定理+指数循环节)

题意: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 ≡ a^(n%(m-1)) * a^(m-1)≡ a^(n%(m-1)) (mod m)

记得特判一下n为0和1的情况。

xiaodingli

 

指数循环节学习笔记

资料先行:

指数循环节证明

指数循环节2

对指数循环节的一些理解

READ MORE →

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存。。我好傻啊。。。

 

 

hdu 4965 Fast Matrix Calculation (矩阵快速幂,2014多校#9)

题目链接

题意:Step 1: Calculate a new N*N matrix C = A*B.
Step 2: Calculate M = C^(N*N).
Step 3: For each element x in M, calculate x % 6. All the remainders form a new matrix M’.
Step 4: Calculate the sum of all the elements in M’.

思路: 水题。。就一个trick…

朴素的矩阵乘法的复杂度是n^3的。。。按照题目的顺序求的话。。。。求M矩阵时会超时。。。(而且1000*1000的数组也不能放到结构体里…?

我们可以根据矩阵乘法的结合律。

M = (A*B)^(N*N) = A * (B*A)^(N*N-1) * B

然后就可以搞了。

 

hdu 2157 How many ways?? (矩阵快速幂经典题目)

题意:给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值

思路:
 把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,我们只需要快速幂求出A^k即可。

M67_十个利用矩阵乘法解决的经典题目

这个转化好美啊。。。

 

 

 

hdu 1211 RSA (扩展欧几里得算法求逆元 +快速幂)

题目链接

题意:给出p, q, e, l,令n = p * q, fn = (p-1) * (q-1)

给出l个c,计算m = D(c) = cd mod n,其中m为要输入的明文对应的ascii编码,d的计算方法:> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key。

问明文。

 

思路:

出题人JGShining(极光炫影)傻逼。

题意都说不清?

大小写字母一个意思?

脑袋有坑的出题人。

出题人傻逼。

出题人傻逼。

出题人傻逼。

 

 

好了。这道题需要用到扩展欧几里得算法求逆元。。。ksm(a,mod-2)的方法是基于费马小定理,必须mod为质数才可以用。扩展偶记里算法没有这个限制。

用欧几里德算法求模的逆元:

同余方程ax≡b (mod n),如果 gcd(a,n)== 1,则方程只有唯一解。

在这种情况下,如果 b== 1,同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。

这时称求出的 x 为 a 的对模 n 乘法的逆元。

对于同余方程 ax= 1(mod n ), gcd(a,n)= 1 的求解就是求解方程

ax+ ny= 1,x, y 为整数。这个可用扩展欧几里德算法求出,原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。

也就是gcd(a,n,x,y);
然后再(x = x%n + n)%n,得到最小的正整数x,即为a在模n意义下的逆元。