Posts

题目链接 题意： 给出n个银行 ，以及抢劫每个银行可以得到的价值和被抓的概率，不同银行之间被抓的概率是相互独立的，现在给出安全概率p，只有当概率从小于安全概率时才是安全的，问最多能抢劫多少价值。

题目链接 题意：给出n(n<=1E3)个字符，字符可能为’D’,‘I’,’?’，第i位对应的字符分别表示，第i位大于第i+1位，第i位小于第i+1位，或者不确定。

题目链接 题意：问长度为n的“波浪”型排列（即1..n每个数出现一次）有多少。波浪型的含义是，“高低高”或者“低高低” 思路：我们考虑当前已经知道i-1个数的波浪型的排列的方案数，那么当第i个数到来时，第i个数一定是最大的。

题目链接 题意：给出n(n<=200000)个数，问所有区间[l,r]中mex的和。 （一个区间mex的定义为，这个区间中没有出现的最小的非负数） 思路：我们观察到mex(1,i)随着i增大，是不减的。(单调是线段树查询区间的时候非常好用的东西，这也是此题的突破口)

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

题目链接 题意：问长度为n，每个位置由且仅有‘H’和’T’组成的序列中，至少有连续k个‘H’出现的方案数。 思路：不会做，参考了题解 不过没有完全搞懂。

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

题意：now he let you calculate G(n,k) .Here G(n,0) = f(n) , G(n,i) = f( G(n,i-1) ) (k >= i >= 1).其中f是斐波那契数列。 思路：其实就是hdu 4291的加强版：hdu 4291 解题报告 开一个1E4的数组存一下每一层的循环节就好了。

题目链接 题意：求一个小数的循环节… 思路：其实直接模拟就好… 模拟竖式计算… 这里用到一个小技巧。 由于多组数据，每次都memset一个bool会很慢，导致超时。

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

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

题目链接 题意：f[0] = 1,f[1] = 1,f[i] = f[i-1] + f[i-2] (i>=2)，问最小的m满足f[n]%p==f[n+m]%p 思路：求斐波那契数列循环节。 参考了Acdreamer的博客_Fib数模n的循环节

题目链接 题意：给出了一段伪代码。分析得知其实就是f[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2] 思路：一眼题，和hdu4549很类似hdu4549解题报告 不同的是这道题中p不一定是质数（其实不是也无所谓啊…hdu4549只不过是因为1E9+7是指数，又用费马小定理化简了一下，这道理%phi(p)即可）

题目链接 题意： Assume that f(0) = 1 and 0^0=1. f(n) = (n)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x). 思路：指数循环节。 trick点在于0^0=1这点。 比较容易想到的一层是ksm的时候特判。 比较不容易想到的一层是，0作为底数的时候，可能出现0^a在用降幂公式加速后，出现0^0。

题目链接 题意：给出b,p,m（( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 – 1 )），问满足图中条件的n有多少个。 思路：这题由于对p没有限制，所以细节多一些，需要讨论。 首先我们知道指数循环节公式，也就是所谓的降幂公式为：a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c)，（ps：后面的限制条件，在x<phi(c)的时候，该式子依然正确，只不过增加了运算复杂度。。。？ 存疑）

题目链接 题意：求一个楼梯数%m的大小。 思路：指数循环节。 需要注意的是，模数只有最外层是m，每往里一层，模数都变成m=phi(m) 所以可以写个dfs或者先预处理出每一层m存一下。

题目链接 题意：定义s(k)为将n分成k个正整数的划分数，给出n，问s(1) + s(2) + … + s(n-1) + s(n)是多少，结果9+7，其中n<=10^100000。 思路：首先化简要求的式子。

题意：M斐波那契数列F[n]是一种整数数列，它的定义如下： F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n，你能求出F[n]的值吗？ 思路：观察发现。。。F[n] = a^(fib(n-1)) * b ^ (fib(n))

资料先行： 指数循环节证明 指数循环节2 对指数循环节的一些理解 挂了一点题目，写完来写总结。 vjudge_不会指数循环节的111qqz 写完了。 首先要注意的是： 首先我们知道指数循环节公式，也就是所谓的降幂公式为：a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c)，（ps：后面的限制条件，在x<phi(c)的时候，该式子依然正确，只不过增加了运算复杂度。。。？ 存疑）

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次操作后它可获得的S的和的最大值。（数据保证这个值为非负数）