题目链接 题意：给出了一段伪代码。分析得知其实就是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)的时候，这个公式才成立。 这道题就是反例，不加 …

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的和的最大 值。（数据保证这个值为非负数） Input 第一行有两个整数n,k表示初始元素数量和操作数，第二行包含n个整数表示初始时可重集的元素。 对于100%的数据，有 n<=10^5，k<=10^9，|ai|<=10^5 Output 输出一个整数，表示和的最大值。答案 …

题目链接 题意：给出n,k，以及n个正数，把n个数放在一个集合里，进行k次操作，每次操作取最大的数和次大的数放进集合。问k次操作结束后，集合中所有数的和。 思路：假设初始时刻，次大和最大分别为a0,a1，那么得到的就是一个类斐波那契数列。初始为a0,a1,fn = fn-1 + fn 最后求和。 利用这个性质。。。 我们直接构造完矩阵。。。求出F(n+2)即可。。 需要注意。。。矩阵中每一项是小于1E7+7的。。。矩乘的时候会爆int... 所以mat要用LL存。。我好傻啊。。。 /* *********************************************** Author :111qqz Created …

题目链接 题意：Step 1: Calculate a new NN matrix C = AB. Step 2: Calculate M = C^(N*N). Step 3: For each element x in M, calculate x % 6. All the remainders form a new matrix M’. Step 4: Calculate the sum of all the elements in M’. 思路： 水题。。就一个trick... 朴素的矩阵乘法的复杂度是n^3的。。。按照题目的顺序求的话。。。。求M矩阵时会超时。。。（而且1000*1000的数组也不能放到结构体里...? 我们 …

题意：给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值 思路： ** 把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，CA的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要快速幂求出A^k即可。** M67_十个利用矩阵乘法解决的经典题目 这个转化好美啊。。。 /* *********************************************** Author :111qqz …

题目链接 题意：给出p, q, e, l,令n = p * q, fn = (p-1) * (q-1) 给出l个c,计算m = D(c) = c**d** mod n,其中m为要输入的明文对应的ascii编码，d的计算方法：> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key。 问明文。 思路： 出题人JGShining（极光炫影）傻逼。 题意都说不清？ 大小写字母一个意思？ 脑袋有坑的出题人。 出题人傻逼。 出题人傻逼。 出题人傻逼。 好了。这道题需要用到扩展欧几里得算法求逆元。。。ksm(a,mod-2)的方法是基于 …

题目链接 题意： Given a n × n matrix A and a positive integer k, find the sum S = A + _A_2 + _A_3 + … + Ak. 思路： 对k进行二分。 比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。 以及错误的递归方式： 无形中增加了多少次。。。。。。怎么像小学生呢。。。 正确的写法。。。 /* …

题目链接 题意：给出n个数,q个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+7的答案是多少。 思路：这道题需要一点欧拉函数的知识。 phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。 To calculate the answer on every query let's use the formula , where _p_1, p_2, ..., p__k — all prime numbers which divided_n. 如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。 考虑两个数a,b的欧拉函数。 一开始考虑也许有什么性质。。。查了下欧拉函数的wiki 欧拉函数_维基百科 欧拉函数 …

http://acm.hdu.edu.cn/showproblem.php?pid=1575 题意：A为一方阵，求(A^k)73得到的矩阵的主对角线的和。 思路：矩阵快速幂。模板题。 /* *********************************************** Author :111qqz Created Time :2016年02月21日 星期日 10时28分33秒 File Name :code/hdu/1575.cpp ************************************************ */ #include <cstdio> #include …

http://codeforces.com/problemset/problem/621/E 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。 思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。 但是由于b很大（1E9）,所以需要用矩阵加速。 /* *********************************************** …