题目链接 题意： 有一只熊，初始在(sx,sy)处，如果当前的位置在(x,y)，那么下一秒会在((x+dx-1)%n+1,(y+dy-1)%n+1)处， dx[i] = k[i-1] + dx[i-1],dy[i]=k[i-1] + dy[i-1]，k表示的是某个点的花丛数目。 初始点(x,y)的花丛数为x+y,每经过一个时间，所有点的花丛数增加1. 所以，k[i] = x[i] + y[i] + i-1，现在问经过时间t后，熊的位置在哪里。也就是x[t],y[t]的值。 思路： 我们不妨先只考虑x方向的，因为y方向完全相同。 观察x[t]的式子， x[t] = (x[t-1] + dx[t-1] -1) % n +1。。这个%n之 …

题目链接 题意： 求f[n] = f[n-1] + f[n-2] + 1，在b(10000)进制下的最后一位数字的十进制表示。 思路： 构造矩阵即可，M矩阵是一个3_3的矩阵，M1矩阵是一个3_1的矩阵。。很easy，就不说了。 写题解的目的是，对于这种要求b进制下，最后一位或者最后两位的数字的十进制表示的问题，其实就是在说，取模的数是base或者base^2 1A美滋滋 /* *********************************************** Author :111qqz Created Time :2017年10月01日 星期日 18时39分17秒 File Name :10518.cpp …

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的范围也知道是矩阵快速幂。。 难点还是构造矩阵。 构造矩阵主要凭借经验，但是还是有一些规律可循： 1. 对于求和的式子，如 s[n] = sum{F[1]..F[n]}类似的式子，我们只需要考虑如何构造F[n]即可。 2. 尽量将要构造的表达式展 …

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]%m是多少。 思路： 构造矩阵，加速递推式。 趁着这道题说一下一般的构造法。 转移矩阵M(d*d)的构造方法是，最后一行倒序写a[1]..a[d], 除去第一列和最后一行外，用1填充对角线，其余的为0. 初始矩阵M1(d*1)的构造方法是从上到下，f[1]..f[d]即可。 需要注意的是 *最后答案是 (M^(n-d))M1.mat[d-1][0] (由于经常出现的是d=2的递推式，因 …

uva10655题目链接 题意： 给出a+b和ab的值，问a^n+b^n 思路： 构造矩阵,手写一下很显然... 转移矩阵M=[0 , 1] [-q,p ] 初始矩阵M1=[p ] [p^2-2*q] 快速幂即可。 有个坑点在于..读入的结束是p=0&q=0,并且只有这两个输入。 如果用p=0&&q=0作为终止条件，那么就会将三个输入，但p==0&&q==0的情况错误得终止... 正确的做法是 while (~scanf("%lld%lld%lld",&p,&q,&n)==3) /* …

1009: [HNOI2008]GT考试 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 3127 Solved: 1926 [Submit][Status][Discuss] Description 　阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。 他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为 0 Input 　第一行输入N,M,K.接下来一行输入M位的数。 …

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

题目链接 题意： 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[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)的时候，这个公式才成立。 这道题就是反例，不加 …