2160: 拉拉队排练 # Time Limit: 10 Sec Memory Limit: 259 MB Submit: 1938 Solved: 743 [Submit][Status][Discuss]
Description # 艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。
题目链接
题意： # 有一只熊，初始在(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表示的是某个点的花丛数目。
题目链接
题意： # 求f[n] = f[n-1] + f[n-2] + 1，在b(10000)进制下的最后一位数字的十进制表示。
思路： # 构造矩阵即可，M矩阵是一个3_3的矩阵，M1矩阵是一个3_1的矩阵。。很easy，就不说了。
hdu4686题目链接
题意： # An Arc of Dream is a curve defined by the following function:
$$ \text{AoD}(N) = \sum_{i=0}^{N-1} a_i b_i $$where: $$ a_0 = A_0, \quad a_i = a_{i-1} A_X + A_Y $$ $$ b_0 = B_0, \quad b_i = b_{i-1} B_X + B_Y $$What is the value of \( \text{AoD}(N) \pmod{1{,}000{,}000{,}007} \)?
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是多少。
uva10655题目链接
题意： # 给出a+b和ab的值，问a^n+b^n
思路： # 构造矩阵，手写一下很显然…
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
题目链接
题意：
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.
题目链接
题意：
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[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2]
思路：一眼题，和hdu4549很类似hdu4549解题报告
不同的是这道题中p不一定是质数（其实不是也无所谓啊…hdu4549只不过是因为1E9+7是指数，又用费马小定理化简了一下，这道理%phi(p)即可）
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的和的最大值。（数据保证这个值为非负数）
题目链接
题意：给出n,k，以及n个正数，把n个数放在一个集合里，进行k次操作，每次操作取最大的数和次大的数放进集合。问k次操作结束后，集合中所有数的和。
思路：假设初始时刻，次大和最大分别为a0,a1，那么得到的就是一个类斐波那契数列。初始为a0,a1,fn = fn-1 + fn
题目链接
题意：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…
题意：给定一个有向图，问从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即可。**
题目链接
题意：给出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。
题目链接
题意：
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 个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数对 1e9+7 取模的答案是多少。
思路：这道题需要一点欧拉函数的知识。
phi(n) 是欧拉函数，意义为小于等于 n 并且与 n 互质的数的个数。
http://acm.hdu.edu.cn/showproblem.php?pid=1575
题意：A为一方阵，求(A^k)73得到的矩阵的主对角线的和。
思路：矩阵快速幂。模板题。
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月21日 星期日 10时28分33秒 4File Name :code/hdu/1575.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=12; 34const int MOD = 9973; 35struct Mat 36{ 37 int mat[N][N]; 38 void clear() 39 { 40 ms(mat,0); 41 } 42}A; 43int n,k; 44 45Mat operator * (Mat a,Mat b) 46{ 47 Mat c; 48 c.clear(); 49 for ( int i = 0 ; i < n ; i++) 50 for ( int j = 0 ; j < n ; j++) 51 for (int k = 0 ; k < n ; k++) 52 c.mat[i][j] =(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD; 53 54 return c; 55 56} 57Mat operator ^ (Mat a,int b) 58{ 59 Mat c; 60 for ( int i = 0 ; i < n ; i++) 61 for ( int j = 0 ; j < n ; j++ ) 62 c.mat[i][j]=(i==j); 63 while (b) 64 { 65 if (b&1) c = c * a; 66 b = b>>1; 67 a = a * a; 68 } 69 return c; 70} 71int main() 72{ 73 #ifndef ONLINE_JUDGE 74 freopen("code/in.txt","r",stdin); 75 #endif 76 77 int T; 78 scanf("%d",&T); 79 while (T--) 80 { 81 scanf("%d %d",&n,&k); 82 A.clear(); 83 for ( int i = 0 ; i < n ; i++) 84 for ( int j = 0 ; j < n; j ++) 85 scanf("%d",&A.mat[i][j]); 86 87 Mat res; 88 res.clear(); 89 res = A^k; 90 91 int ans = 0 ; 92 for ( int i = 0 ; i < n ;i++) ans = (ans +res.mat[i][i])%MOD; 93 94 printf("%d\n",ans); 95 96 } 97 98 99 #ifndef ONLINE_JUDGE 100 fclose(stdin); 101 #endif 102 return 0; 103}
http://codeforces.com/problemset/problem/621/E # 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。
