题意： W_H的方格纸，共有(w+1)_(H+1)个整点，现在将2个蜡烛放在2个不同的整点上。蜡烛不会被放在边界上。现在给出方格纸的尺寸和2个蜡烛的坐标，求一条线段将方格纸拆成2部分，而且这条线段不经过任何一个蜡烛且使得每一部分恰好有一个蜡烛。问线段的起点和终点。 思路： 为了方便讨论，我们将x坐标小的设为蜡烛1，另一个设为蜡烛2. 分两种情况讨论，即横坐标相同和不同2种情况。 需要注意的是...要交文件orz /* *********************************************** Author :111qqz Created Time :2017年10月02日 星期一 12时34分38秒 File …

题目链接 题意： 有一只熊，初始在(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) /* …

16年北京网络赛遇到了这个技巧...但是竟然忘记记了下来？ 快速乘是为了解决 计算a_b % mod 时a_b溢出LL 的问题 比如a=1E16,b=1E16,mod=1E18，虽然最后的结果没有溢出，但是中间溢出了。 原理和快速幂很类似，具体可以参考 晴川大爷的专栏 ll fastMultiplication(ll a,ll b,ll mod){ ll ans = 0; while(b){ if(b%2==1){ b--; ans = ans + a; ans %= mod; }else{ b /= 2; a = a + a; a %= mod; } } return ans; } 完全就是把快速幂中的乘法变成加法了嘛（从记忆角 …

题目链接 题意： 给出了一段程序，程序实际算的是f[n] = (f[n-1] + n%2)%m的值，其中f[1]=1,给出n,m(1E9)，问f[n] 思路： 显然是矩阵快速幂，终点在于构造矩阵。 通过经验可得（这次真的是经验了。。。其实也挺容易的，要点大概在于先把需要的项列在一起，然后增加0或者多个，为了转移需要的辅助项。 根据当前列和下一列，手动构造转移矩阵） 转移矩阵M为 [2, 1,0] [0,-1,1] [0,0 ,1] 4A..都是一个原因。。矩阵乘法那里。。。就算你%了m..也是两个1E9在相乘。。。然后就炸了23333,改成LL即可。 /* …

hdu5015题目链接 题意： 给出矩阵的构造规则： a[0][j] (j>=1) 分别为233,2333,23333....给出a[i][0] (i>=1)，对于其余的i,j,a[i][j]=a[i-1][j] + a[i][j-1] 现在问a[n][m] 在% 1E7+7 下的值是多少 （n<=10,m<=1E9） 思路： 显然矩阵快速幂，但是不会构造矩阵，放弃。 看了很多题解...发现都是“显然”构造出矩阵。。。似乎是直接凑出来的。。。 可能需要积累一点经验。 对于这道题，我们观察到n很小 所以一个直觉就是从n-1列推到第n列，推到n+1列这样地推。 初始第一列的信息是（假设n为3） [a1] [a2] …

hdu3642题目链接 题意：给出若干个（1000）长方体，求至少交三次的空间的体积。 尺寸为[x1,x2],[y1,y2],[z1,z2],其中x，y的坐标的绝对值不超过1E6,Z的坐标的绝对值不超过1E9. 思路： 线段树+扫描线。 由于Z的坐标范围比较小，我们的做法是 利用“微分”的思想，将每个长方体，想成若干的高度为1的矩形（矩形片） 因此就转化成了求矩形至少交三次的面积 其中和矩形交，也就是矩形至少交2次的面积比较类似，只不过线段树多维护一个至少三次覆盖的长度的域。 void PushUp(int l,int r,int rt) { …