如何访问未备案的网站,扶风网站开发,如何给网站做第三方流量监测,学网站开发推荐书快速幂总结 快速幂这个东西比较好理解#xff0c;但实现起来到不老好办#xff0c;记了几次老是忘#xff0c;今天把它系统的总结一下防止忘记。 首先#xff0c;快速幂的目的就是做到快速求幂#xff0c;假设我们要求a^b,按照朴素算法就是把a连乘b次#xff0c;这样一来…快速幂总结 快速幂这个东西比较好理解但实现起来到不老好办记了几次老是忘今天把它系统的总结一下防止忘记。 首先快速幂的目的就是做到快速求幂假设我们要求a^b,按照朴素算法就是把a连乘b次这样一来时间复杂度是O(b)也即是O(n)级别快速幂能做到O(logn)快了好多好多。它的原理如下 假设我们要求a^b那么其实b是可以拆成二进制的该二进制数第i位的权为2^(i-1)例如当b11时 a11a(2^02^12^3) 11的二进制是101111 2³×1 2²×0 2¹×1 2º×1因此我们将a¹¹转化为算 a2^0*a2^1*a2^3也就是a1*a2*a8 看出来快的多了吧原来算11次现在算三次但是这三项貌似不好求的样子....不急下面会有详细解释。 由于是二进制很自然地想到用位运算这个强大的工具和 运算通常用于二进制取位操作例如一个数 1 的结果就是取二进制的最末位。还可以判断奇偶x10为偶x11为奇。 运算比较单纯,二进制去掉最后一位不多说了先放代码再解释。 1 int poww(int a,int b){//求a的b次方2 int ans1,basea;3 while(b!0){4 if(b1!0)5 ans*base;6 base*base;7 b1;8 }9 return ans;
10 } 代码很短死记也可行但最好还是理解一下吧其实也很好理解以b11为例b1011,二进制从右向左算但乘出来的顺序是 a^(2^0)*a^(2^1)*a^(2^3)是从左向右的。我们不断的让base*base目的即是累乘以便随时对ans做出贡献。 其中要理解base*base这一步因为 base*basebase2下一步再乘就是base2*base2base4然后同理 base4*base4base8由此可以做到base--base2--base4--base8--base16--base32.......指数正是 2^i 再看上面的例子a¹¹ a1*a2*a8这三项就可以完美解决了快速幂就是这样。 顺便啰嗦一句由于指数函数是爆炸增长的函数所以很有可能会爆掉int的范围根据题意选择 long long还是mod某个数自己看着办。 矩阵快速幂也是这个道理下面放一个求斐波那契数列的矩阵快速幂模板 1 #includeiostream2 #includecstdio3 #includecstring4 #includecmath5 #includealgorithm6 using namespace std;7 const int mod 10000;8 const int maxn 35;9 int N;
10 struct Matrix {
11 int mat[maxn][maxn];
12 int x, y;
13 Matrix() {
14 memset(mat, 0, sizeof(mat));
15 for (int i 1; i maxn - 5; i) mat[i][i] 1;
16 }
17 };
18 inline void mat_mul(Matrix a, Matrix b, Matrix c) {
19 memset(c.mat, 0, sizeof(c.mat));
20 c.x a.x; c.y b.y;
21 for (int i 1; i c.x; i) {
22 for (int j 1; j c.y; j) {
23 for (int k 1; k a.y; k) {
24 c.mat[i][j] (a.mat[i][k] * b.mat[k][j]) % mod;
25 c.mat[i][j] % mod;
26 }
27 }
28 }
29 return;
30 }
31 inline void mat_pow(Matrix a, int z) {
32 Matrix ans, base a;
33 ans.x a.x; ans.y a.y;
34 while (z) {
35 if (z 1 1) mat_mul(ans, base, ans);
36 mat_mul(base, base, base);
37 z 1;
38 }
39 a ans;
40 }
41 int main() {
42 while (cin N) {
43 switch (N){
44 case -1: return 0;
45 case 0: cout 0 endl; continue;
46 case 1: cout 1 endl; continue;
47 case 2: cout 1 endl; continue;
48 }
49 Matrix A, B;
50 A.x 2; A.y 2;
51 A.mat[1][1] 1; A.mat[1][2] 1;
52 A.mat[2][1] 1; A.mat[2][2] 0;
53 B.x 2; B.y 1;
54 B.mat[1][1] 1; B.mat[2][1] 1;
55
56 mat_pow(A, N - 1);
57 mat_mul(A, B, B);
58 cout B.mat[1][1] endl;
59
60 }
61 return 0;
62 } 洛谷P1962 斐波那契数列 题目背景 大家都知道斐波那契数列是满足如下性质的一个数列 • f(1) 1 • f(2) 1 • f(n) f(n-1) f(n-2) (n ≥ 2 且 n 为整数) 题目描述 请你求出 f(n) mod 1000000007 的值。 输入输出格式 输入格式 ·第 1 行一个整数 n 输出格式 第 1 行 f(n) mod 1000000007 的值 输入输出样例 输入样例#1 复制 5 输出样例#1 复制 5 输入样例#2 复制 10 输出样例#2 复制 55 说明 对于 60% 的数据 n ≤ 92 对于 100% 的数据 n在long long(INT64)范围内。 首先看到数据范围longlong以内故我们考虑矩阵加速动态规划。 我们都知道斐波那契数列有这样的一个动态转移方程f[i]f[i-1]f[i-2]; 由此可以推出一个2×2的矩阵1 1 1 0 然后就是套用矩阵快速幂的模板来加速。 以下是代码 #include cstdio#include cstring#include iostream#include cstdlibusing namespace std;typedef long long lol; lol n;lol mod1e97;lol f[3][3],ans[3]{0,1,1}; void lu() {lol t[3]{0};for (int i1;i2;i)for (int j1;j2;j)t[i](t[i](ans[j]*f[j][i])%mod)%mod;memcpy(ans,t,sizeof(ans));} void ge() {lol t[3][3]{0};for (lol i1;i2;i)for (lol j1;j2;j)for (lol k1;k2;k)t[i][j](t[i][j](f[i][k]*f[k][j])%mod)%mod;memcpy(f,t,sizeof(f));} int main() {cinn;if (n1||n2||!n) {cout1endl;exit(0);}n--;f[1][1]1;f[1][2]1;f[2][1]1;f[2][2]0;while (n) {if (n1) lu();ge();n1;}coutans[2]endl;return 0;} 转载于:https://www.cnblogs.com/Renyi-Fan/p/8142674.html
