- 浏览: 117937 次
- 性别:
- 来自: 北京
最新评论
推导公式的题目,矩阵幂关键就在于构造系数矩阵
备忘:
S(n, k) - S(n - 1, k) = Fn ^ k
当Fn能够线性表示的时候,S(n, k) = S(n - 1, k) + Fn ^ k 不也是线性表示嘛!
Fn ^ k = sigma( C(k, i) * a^i * b^(k-i) * Fn-1^i * Fn-2^(k-i) ) 其中0 <= i <= k
备忘2:
构造矩阵系数的时候,要用 += 把相应的项的系数加上去,而不是直接 =
备忘3:
快速幂的复杂度很低,所以基本不用考虑常数
备忘:
S(n, k) - S(n - 1, k) = Fn ^ k
当Fn能够线性表示的时候,S(n, k) = S(n - 1, k) + Fn ^ k 不也是线性表示嘛!
Fn ^ k = sigma( C(k, i) * a^i * b^(k-i) * Fn-1^i * Fn-2^(k-i) ) 其中0 <= i <= k
备忘2:
构造矩阵系数的时候,要用 += 把相应的项的系数加上去,而不是直接 =
备忘3:
快速幂的复杂度很低,所以基本不用考虑常数
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #define out(v) cout << #v << ": " << (v) << endl using namespace std; typedef long long LL; LL f1[52], f2[52], a[52], b[52], k, n, m; LL C[52][52]; void make1() { C[0][0] = 1; for (int i = 1; i <= 50; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m; } a[0] = 1; for (int i = 2; i <= 50; ++i) a[i] = (a[i - 1] * a[1]) % m; b[0] = 1; for (int i = 2; i <= 50; ++i) b[i] = (b[i - 1] * b[1]) % m; f1[0] = 1; for (int i = 2; i <= 50; ++i) f1[i] = (f1[i - 1] * f1[1]) % m; f2[0] = 1; for (int i = 2; i <= 50; ++i) f2[i] = (f2[i - 1] * f2[1]) % m; } typedef LL matrix[52][52]; void copy(int size, matrix X, matrix Y) { for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) Y[i][j] = X[i][j]; } void mutiply(int size, matrix _X, matrix _Y, matrix Z) { matrix X, Y; copy(size, _X, X); copy(size, _Y, Y); for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) { Z[i][j] = 0; for (int k = 0; k < size; ++k) Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % m; } } void ident(int size, matrix X) { for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) X[i][j] = (i == j ? 1 : 0); } void power(int size, matrix _X, LL n, matrix Y) { ident(size, Y); matrix X; copy(size, _X, X); while (n) { if (n & 1) mutiply(size, Y, X, Y); n >>= 1; if (n) mutiply(size, X, X, X); } } void print(int size, matrix X) { for (int i = 0; i < size; ++i) { for (int j = 0; j < size; ++j) cout << X[i][j] << " "; cout << endl; } } void clear(int size, matrix X) { for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) X[i][j] = 0; } matrix A; void make2() { clear(k + 2, A); for (int i = 0; i <= k; ++i) for (int j = 0; j <= i; ++j) A[i][k - (i - j)] = (A[i][k - (i - j)] + C[i][j] * a[j] % m * b[i - j]) % m; for (int j = 0; j <= k; ++j) A[k + 1][j] = (A[k + 1][j] + C[k][j] * a[j] % m * b[k - j]) % m; A[k + 1][k + 1] = 1; //cout << "A" << endl; print(k + 2, A); } int main() { int T; cin >> T; while (T--) { cin >> f1[1] >> f2[1] >> a[1] >> b[1] >> k >> n >> m; make1(); make2(); if (n == 1) { cout << f1[k] % m << endl; continue; } else if (n == 2) { cout << (f1[k] + f2[k]) % m << endl; continue; } LL p[52]; for (int i = 0; i <= k; ++i) p[i] = f2[i] * f1[k - i] % m; p[k + 1] = (f2[k] + f1[k]) % m; matrix D; power(k + 2, A, n - 2, D); //cout << "D" << endl; print(k + 2, D); LL ans = 0; for (int j = 0; j <= k + 1; ++j) ans = (ans + D[k + 1][j] * p[j] % m) % m; cout << ans << endl; } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1143/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 833线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 844线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 879写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 962转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1180封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 791终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 595写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1122源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 794import java.util.*; import j ... -
整数划分
2010-10-07 10:38 829#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 973// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1039typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1127最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1278Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 765static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 866标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 839“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1031“多重覆盖”或“重复覆盖”问题 #include < ... -
RMQ模板
2010-07-28 11:04 1178/* * Author: rush * Creat ...
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu题目分类
HDU图论题目分类
自己做的HDU ACM已经AC的题目
hdu 1005.比较简单的一道题,有兴趣的可以看看。