111qqz的小窝

老年咸鱼冲锋!

bzoj 2160: 拉拉队排练 (回文自动机+快速幂)

2160: 拉拉队排练 Time Limit: 10 Sec Memory Limit: 259 MB Submit: 1938 Solved: 743 [Submit][Status][Discuss] Description 艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球

Posted by 111qqz Tuesday, November 14, 2017

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

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

Posted by 111qqz Monday, October 2, 2017

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

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

Posted by 111qqz Sunday, October 1, 2017

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的范围也知道是矩

Posted by 111qqz Sunday, October 1, 2017

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]%

Posted by 111qqz Saturday, September 30, 2017

uva 10655 - Contemplation! Algebra （构造矩阵，快速幂）

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

Posted by 111qqz Saturday, September 30, 2017

【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<

Posted by 111qqz Sunday, November 13, 2016

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

Posted by 111qqz Thursday, November 3, 2016

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

Posted by 111qqz Monday, October 31, 2016

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

Posted by 111qqz Sunday, October 30, 2016

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

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

Posted by 111qqz Sunday, October 30, 2016

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

Posted by 111qqz Wednesday, October 26, 2016

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

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

Posted by 111qqz Tuesday, October 25, 2016

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’. 思路： 水题。。就一

Posted by 111qqz Wednesday, October 19, 2016

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

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

Posted by 111qqz Wednesday, October 19, 2016

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

题目链接 题意：给出p, q, e, l,令n = p * q, fn = (p-1) * (q-1) 给出l个c,计算m = D(c) = c**_d_** mod n,其中m为要输入的明文对应的ascii编码，d的计算方法：

Posted by 111qqz Wednesday, October 19, 2016

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)_

Posted by 111qqz Wednesday, October 19, 2016

codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

题目链接 题意：给出n个数,q个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+7的答案是多少。 思路：这道题需要一点欧拉函数的知识。 p

Posted by 111qqz Thursday, September 22, 2016

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

Posted by 111qqz Sunday, February 21, 2016

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

Posted by 111qqz Monday, February 8, 2016

FEATURED TAGS
bfs binary-search brute-force c++ dfs dp greedy hash km kmp leetcode math number-theory rmq sg函数 stl tensorflow 二分图最佳匹配 分块 前缀和 匈牙利算法 区间dp 博弈论 后缀自动机 图论 字符串 快速幂 数位dp 构造 树状数组 概率 模拟 母函数 矩阵 离散化 线段树 计算几何
ABOUT ME
avatar

ex-ACMer@HUST, researcher@SenseTime

FRIENDS