/* 矩阵乘法+快速幂. 一开始迷之题意.. 这个gcd有个规律. a b b c=a*x+b(x为常数). 然后要使b+c最小的话. 那x就等于1咯. 那么问题转化为求 a b b a+b 就是斐波那契了.... */ #include<iostream> #include<cstdio> #define MAXN 3 #define LL long long #define mod 1000000007 using namespace std; LL n; LL a[MAXN]
目录 1.矩阵相乘的朴素算法 2.矩阵相乘的strassen算法 3.完整测试代码c++ 4.性能分析 5.参考资料 内容 1.矩阵相乘的朴素算法 T(n) = Θ(n3) 朴素矩阵相乘算法,思想明了,编程实现简单.时间复杂度是Θ(n^3).伪码如下 to n to n to n do c[i][j] ← c[i][j] + a[i][k]⋅ b[k][j] 2.矩阵相乘的strassen算法 T(n)=Θ(nlog7) =Θ (n2.81) 矩阵乘法中采用分治法,第一感觉上应该能够有效的提高算
[题目大意] 已知Xn+1=(aXn+c) mod m,求Xn mod g. [思路] get到了longlong乘法的正确方法,快速乘.什么是快速乘呢? 简单来讲,快速幂就是模拟了二进制的竖式乘法.如: 10101 × 1011 = 10101*1+10101*2^1*1+10101*2^2*0+10101*2^3*1 代码如下: long long multi(long long a,long long b,long long m) { ; while(b) { ) (ans+=a) %=
We consider problems concerning the number of ways in which a number can be written as a sum. If the order of the terms in the sum is taken into account the sum is called a composition and the number of compositions of n is denoted by c(n). Thus, the