只做乡村旅游的网站,免费建站网站一级在线看,英语网站开发,成色好的y31s标准版下载快速幂 题目链接#xff1a;https://www.luogu.org/problemnew/show/P1226 快速幂用了二分的思想#xff0c;即将\(a^{b}\)的指数b不断分解成二进制的形式#xff0c;然后相乘累加起来#xff0c;就是用\(a^{b/2}a^{b/2}\)去求\(a{^b}\)。 例如:\(a^{11}a^{(2^02^12^3)}\)… 快速幂 题目链接https://www.luogu.org/problemnew/show/P1226 快速幂用了二分的思想即将\(a^{b}\)的指数b不断分解成二进制的形式然后相乘累加起来就是用\(a^{b/2}×a^{b/2}\)去求\(a{^b}\)。 例如:\(a^{11}a^{(2^02^12^3)}\) 程序实现是这样的使用了位运算 ll pow(ll b,ll p,ll k)
{for(;p;p1) // 右移等同于 /2{if(p1) //判断p是否为奇数是则返回trueansans*b%k;bb*b%k;}return ans%k;
} AC代码 #includeiostream
#includecstdio
#define ll long long
using namespace std;
int k1,m0,flag;
ll ans1;
ll pow(ll b,ll p,ll k)
{for(;p;p1){if(p1)ansans*b%k;bb*b%k;}return ans%k;
}
int main()
{ll b,p,k;cinbpk;ll mpow(b,p,k)%k;printf(%d^%d mod %d%d,b,p,k,m); return 0;
} 矩阵快速幂 题目链接https://www.luogu.org/problemnew/show/P3390 矩阵运算法则 矩阵A的大小为\(n×m\)B的大小为\(n×k\)设\(CA×B\) 则\(C_{i,j}\sum\limits_{k1}^{n}A_{i,p}×B_{p,j}\) 例 矩阵乘满足结合律\((AB)CA(BC)\) 有一种特殊的矩阵单位矩阵它从左上角到右下角的对角线上的元素均为1除此以外全都为0。它在矩阵乘中相当于数乘中的1即任何矩阵乘它都等于本身。 以上这些就是打出矩阵快速幂前必备的基础知识了。 代码实现 理解了矩阵乘法之后我们就可以用函数来模拟矩阵乘了。Mat Mul(Mat x,Mat y)
{for(int i1;in;i)for(int j1;jn;j)c.m[i][j]0;for(int i1;in;i)for(int j1;jn;j)for(int k1;kn;k){c.m[i][j]c.m[i][j]%modx.m[i][k]*y.m[k][j]%mod;}return c;
} 因为矩阵乘满足结合律所以快速幂完全适用于矩阵矩阵快速幂和普通快速幂几乎一模一样不同点在于“*”号改成了Mul函数不会普通快速幂的请前往P1226Mat pow(Mat x,ll y)
{Mat anse;while(y){if(y1)ansMul(ans,x); xMul(x,x);y1;}return ans;
} 知道了这些后这道题基本就可以AC了 最后要注意开long long不然会爆零。 AC代码
#includeiostream
#includecstring
#define mod 1000000007
#define ll long long
using namespace std;
struct Mat{ll m[101][101];
};//结构体存矩阵
Mat a,e;//a是输入的矩阵e是单位矩阵
ll n,p;
Mat Mul(Mat x,Mat y) //矩阵乘
{Mat c;for(int i1;in;i)for(int j1;jn;j)c.m[i][j]0;for(int i1;in;i)for(int j1;jn;j)for(int k1;kn;k){c.m[i][j]c.m[i][j]%modx.m[i][k]*y.m[k][j]%mod;}return c;
}
Mat pow(Mat x,ll y) //矩阵快速幂
{Mat anse;while(y){if(y1)ansMul(ans,x); xMul(x,x);y1;}return ans;
}int main()
{//输入 cinnp;for(int i1;in;i)for(int j1;jn;j)cina.m[i][j];//算法核心 for(int i1;in;i)e.m[i][i]1; Mat anspow(a,p);//输出 for(int i1;in;i){for(int j1;jn;j)coutans.m[i][j]%mod ;coutendl;} return 0;
} 广告时间 在下的洛谷博客博客园博客 转载于:https://www.cnblogs.com/wxl-Ezio/p/8520427.html
