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次操作结束后，集合中所有数的和。

题目链接

题意：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即可。**

题目链接

题意：

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，即可得到原问题的答案。

题目链接

题意：求f[n] % 10000,f为斐波那契数。

思路：按照题目给出的公式，或者按照加速线性递推式的方法都可以。。。

因为把模数的1E4手滑写成1E4+7结果调了半天也是没谁了呵呵呵呵。

找到了篇四年前空间中的旧文，也是有点感动2333.

快速求解多项递推式

问题描述:

已知 F(n) = AF(n-1) + BF(n-2) + CF(n-3)+.....

求解 F(n)%P

分析:

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

参考资料：

十个利用矩阵乘法解决的经典题目

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
************************************************ */

 1#include <cstdio>
 2#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出现的个数。