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

刚刚看了TBBT season 11 episode 1 Sheldon 和Amy 订婚了，Bernadette又怀孕了。 想想上一季结束的时候，大概半年前。 我好像还是只单身狗，手头没啥能看的offer，还有巨大的学业压力在前方。 感觉这半年收获了好多，多了一份担当，多了几个offer，可能是16年的运气真的太差了吧。 就沈阳打铁这事。。。就真的令人窒息。 这半年真的不知道是怎么过来的，虽然也知道“成年人的事情没有容易二字”， 也不是很愿意太过矫情... 而且日常警惕那种“毫无意义的自我感动” 不过还是真的想说 感谢菊苣@sxg的陪伴 感谢身边那些，在我最低沉最痛苦最萎靡的时候，一直给我加油打气，给我信心的小伙伴。 还要感谢自 …

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

题目链接 题意: 求矩形周长并。 思路： 线段树+扫描线。 和前面的求面积并比较类似，我们先考虑平行x轴的线段，考虑线段树，维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len. 只不过我们这次求的是每条扫描线的长度对周长的贡献，因此不需要乘高度。 需要注意的是，每条扫描线对周长的贡献，是目前扫描线的长度，与上一次扫描线长度的差的绝对值。（不是与上一次答案的差的绝对值！） 演示x轴求长度和的部分 图片来自 lwt聚聚的博客 以及一个小细节是，求面积的时候，最后一条扫描线对答案是没有贡献的（因为每次是求当前扫描线与下一条扫描线之间的面积） 但是求周长的时候，最后一条扫描线是一定会对答案有贡献的。 /* …

题目链接 题意： 求n（1000）个矩形的面积交，也就是至少有2个矩形覆盖的区域的面积。 思路： 和矩形面积并_hdu1542解题报告  类似 面积并问题中，线段树len维护的是至少覆盖一次的区域的长度 在面积交的问题中，我们需要多维护一个"至少覆盖两次的区域的长度"的域（设为double two;） 同时也要维护至少覆盖一次的区域的长度（设为double one;），是因为至少覆盖两次的区域的长度可以由至少覆盖一次的区域长度得到（好像是废话） PushUp的时候要格外注意当前节点被完整覆盖一次的情况。 此时tree[rt].two 可以由两个子区间的one的情况想加得到 （因为rt节点被完整覆盖了至少一次，那么 …

hdu1542题目链接 题意： 求n(100)个矩形的面积并。 思路： 扫描线+线段树 题目是2000年中欧区域赛的题目，虽然年代久远，但是有好几个点还是很值得学习的。 首先是离散化的适用范围: 之前比较常用的是将比较大的整数值离散化，常常是因为数值太大无法作为下标。 那么其实，浮点数有的时候也需要进行离散化，比如作为数组的下标，比如用来枚举。 做法上是和将较大的整数值离散化没有区别，因为遇到的题目不多，所以特意记录一下。 第二点是扫描线的思想： 其实扫描线的思想很早就接触过，noip2011的时候，tyvj上有一道类似的题目，不过是一唯的，当时印象深刻的是@Ocean 兄的那个比喻： 一段公路上右很多区间要收不同的费用，区间的开始 …

zoj3606题目链接 题意：有个小女孩卖火柴,有n个人会来买，分别在时间t[i]，以价格p[i]，买的火柴个数为1+(k-1)%3,其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴，小女孩就会睡着。小女孩睡着后如果有人来买火柴，那小女孩就会醒过来，但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。 思路： 显然，w应该是某2个顾客的来访时间只差（而不是什么任意值）. 因此我们可以通过枚举相邻访问时间的顾客的访问之间之差。 我们可以从小到大枚举w，这样就可以保证得到的最大营业额的对应w最小。 构造一颗线段树，维护4个域，cnt表示区间中，确实购买了火柴的顾客的人数，sum[i] (i属于0..2) …

题目链接 题意：n（1E5）个操作，分为三种，add x表示将x加到集合中（保证集合中之前没有x)，del x表示从集合中删掉x(保证集合中一定右x),sum表示求集合中所有元素按从小到大排列后，所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9 思路：很容易想到的是，由于插入和删除元素造成的位置改变是剧烈的，因此要分别维护i%5==k,k属于0..4的元素的和。 这道题的核心点在于，由于只有1E5个操作，我们可以将元素离散化，这样做的目的是，将每个数和位置一一对应，每个位置用1或者0，表示该位置对应的元素是否在集合中。 考虑线段树，维护6个域，1个是区间中，在集合中的元素个数，剩下5个域，分别表示以该区间的端 …