题目链接 题意： 给f[1],f[2],n,f[i] = 2*f[i-2] + f[i-1] + i^4,求f[n]的值。 思路： 很容易想到矩阵，但是i^4不是线性的差评，我们可以拆一下 i^4=(i-1+1)^4,然后二项式展开即可 i^4=(i-1)^4 + 4*(i-1)^3 + 6(i-1)^2 + 4(i-1) + 1 所以为了维护i^4这一项，需要(i-1)^4,(i-1)^3,(i-1)^2,(i-1),1, 再加上f[i-1]和f[i-2]两项，一共7项。 然后构造矩阵为 16沈阳 onsite的题，当时好像写了一个小时，现在看来，果然是个人尽皆知的傻逼题orz /* …

题目链接 题意： 求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. 尽量将要构造的表达式展 …

题目链接 题意： 给出了一段程序，程序实际算的是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即可。 /* …

给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。 比如当 x=5，k=1时返回 2，因为5+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。 输入描述: 每组测试用例仅包含一组数据，每组数据为两个正整数 x , k。 满足 0 < x , k ≤ 2,000,000,000。 输出描述: 输出一个数y。 输入例子: 5 1 输出例子: 达标2 一看就是数学题...? 打表观察... 1 0000001 2 0000010 3 0000011 4 0000100 5 0000101 6 0000110 7 …

题目链接 题意： m个区间，要求构造一个长度为n的数组，满足m个区间中，每个区间的mex值中的最小值最大。 s思路：很容易想到的是...这个最大的mex 不可能超过每一组区间长度，假设最小的区间长度为mn 那么是否一定可以构造出mex为mn的数组呢？ 是的。 只需要按照 0,1,2...mn-1,0,1....的方式构造即可。 /* *********************************************** Author :111qqz Created Time :2016年11月24日 星期四 09时00分04秒 File Name :code/cf/#381/C.cpp …

题目链接 题意：给一个n*m的由小写字母组成的table.要求从上往下每一行字典序不严格递增。问最少删除几列才能满足。 思路：一开始想的是用一个left数组维护每次删除后某一列左边是哪一列，目的是为了下次的判断。 再想了下，发现没必要。我们只需要知道，两行之间的关系是否确定就好了。over[i][j]为真表示第i行和第j行的胜负已分，对于胜负已分的行，大小无所谓。 对于胜负未分的行，如果table[i][j]>table[i+1][j]，就必须要删掉这一列了。。。。 需要注意的是，某一列最多删一次，记得打上标记。 以及ove标记的时候，要在最后确定这一列没有被删以后再标记。。。用一个set存下可能的胜负已分的行的下标即可。 …

题目链接 题意：n堆石子，每堆a[i]个，k种颜色。给每个石子涂色，要求对于每种颜色，任意两堆中该颜色石子的个数最多差一个。问是否有解，有解输出一组方案。 思路：我们发现有解与否只和最大值最小值有关。 设mn为最小值,mx为最大值。 当mx>mn+k时无解，否则有解。 如果有解。。。输出方案就好了。。。 /* *********************************************** Author :111qqz Created Time :2016年10月04日 星期二 02时40分20秒 File Name :code/cf/problem/509B.cpp …

题目链接 题意：给出n，有1..n n个数，可以选择两个数进行加，减，乘，三种操作，操做完得到一个数放回。 n-1次操作后只剩下一个数。现在要求剩下的数为24.问方法。 思路：我们发现。。。两个数相减可以为1.。那么只要找到4个数的方案和5个数的方案就好了。。。 4个数：123*4 5个数：4*5+3+2-1 然而窝一开始以为必须前面减后面。。。 所以是按照4K,4K+1,4K+2,4K+3分的类。。。每4个数得到两个-1，再相乘。。。。麻烦了一点。。代码写了一半的时候意识到了按2K,2K+1分类就行。 /* *********************************************** Author :111qqz …

题目链接 题意：存在一个[2..100]之间的数，每次可以询问一个数是否是该数的因子，返回yes或者no,最多询问20次。每次要输出询问的数，以及最后要输出这个数是否是质数。 思路：第一次做交互题。。。发现完全不能按照以前的思路。。。 更像是相反的。。。把output看做某种输入。。。input里是某种结果。。。我要根据input里的东西来确定一些东西。 就是先有output，再有input。。。output是选手的输入（最后一个除外），input是返回结果(不是你写的代码的返回结果） 对于这道题。。我们要尽可能少得猜一个数的因子，以确定该数是否为质数。 一个数不是质数的话，就有至少两个大于1的因子。。。 很容易想到。。。判素因 …