111qqz的小窝

老年咸鱼冲锋!

codeforces 385 E. Bear in the Field (先记录想法)

题目链接 题意: 有一只熊,初始在(sx,sy)处,如果当前的位置在(x,y),那么下一秒会在((x+dx-1)%n+1,(y+dy-1)%n+

UVA - 10518 How Many Calls? (构造矩阵,快速幂)

题目链接 题意: 求f[n] = f[n-1] + f[n-2] + 1,在b(10000)进制下的最后一位数字的十进制表示。 思路: 构造矩阵即可,M矩阵是一个3_3的矩阵,M1

hdu 4686 Arc of Dream (构造矩阵,快速幂)

hdu4686题目链接 题意: An Arc of Dream is a curve defined by following function: where a 0 = A0 a i = a i-1_AX+AY b 0 = B0 b i = b i-1_BX+BY What is the value of AoD(N) modulo 1,000,000,007? 思路: 看n的1E18的范围也知道是矩

uva 10870 - Recurrences (矩阵加速线性递推式)

uva10870题目链接 题意: f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d 给出f[1]..f[d],a[1]..a[d],问 f[n]%

uva 10655 - Contemplation! Algebra (构造矩阵,快速幂)

uva10655题目链接 题意: 给出a+b和ab的值,问a^n+b^n 思路: 构造矩阵,手写一下很显然… 转移矩阵M=[0 , 1] [-q,p ] 初

【dp专题001】bzoj 1009: [HNOI2008]GT考试 (字符串上dp+kmp+矩阵加速线性递推式)

1009: [HNOI2008]GT考试 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 3127 Solved: 1926 [Submit][Status][Discuss] Description 阿申准备报名参加GT考试,准考证号为N位数X1X2….Xn(0<

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,因此

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思路:找循环节。首先由于模数固定,可以暴力一下找到循环节。 得到

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). 思路:矩阵加速线性递推式。 这题第一次看是20

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

题目链接 题意:给出了一段伪代码。分析得知其实就是f[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2] 思路:一眼题,和hdu4549很类似hdu4549解题报告 不同的是这道题

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次操作后它可获得

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

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

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

题目链接 题意:Step 1: Calculate a new NN matrix C = AB. 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’. 思路: 水题。。就一

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

题意:给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值 思路: ** 把给定的图转为邻接矩阵,即A(i,j)=1当且

poj 3233 Matrix Power Series (矩阵快速幂+分治)

题目链接 题意: Given a n × n matrix A and a positive integer k, find the sum S = A + _A_2 + _A_3 + … + Ak. 思路: 对k进行二分。 比如,当k=6时,有: A + A^2 + A^3 + A^4 + A^5 + A^6 =_(A + A^2 + A^3)_

poj 3070 Fibonacci (矩阵加速线性递推式)

题目链接 题意:求f[n] % 10000,f为斐波那契数。 思路:按照题目给出的公式,或者按照加速线性递推式的方法都可以。。。 因为把模数的1E4手

矩阵加速线性递推式(转载)

找到了篇四年前空间中的旧文,也是有点感动2333. 快速求解多项递推式 问题描述: 已知 F(n) = AF(n-1) + BF(n-2) + CF(n-3)+….. 求解 F(n)%P 分析: ****************

矩阵学习笔记

参考资料: 十个利用矩阵乘法解决的经典题目

hdu 1575 Tr A (矩阵快速幂模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=1575 题意:A为一方阵,求(A^k)73得到的矩阵的主对角线的和。 思路:矩阵快速幂。模板题。 /* *********************************************** Author :111qqz Created Time :2016年02月21日 星期日 10时28

codeforces #341 div 2 E. Wet Shark and Blocks (数位dp+矩阵加速)

http://codeforces.com/problemset/problem/621/E 题意:有b组数,每组数均有n个且相同。你必须在每组选一个数,组成一个新数sum,使得sum % x == k,问方案数 % (1e9+7)。 思路:数位d