文章

11

粉丝

125

获赞

10

访问

37.2k

头像
矩阵乘法(快速幂)
P1384 北京邮电大学
发布于2023年2月1日 16:17
阅读数 3.6k

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=11,INF = 0x3f3f3f3f;;
typedef pair<int, int> PII;
int a[N][N]={0};
int f[N][N]={0};
int n,k;      // 点的数量
void mul(int c[][N],int a[][N],int b[][N])
{
	int temp[N][N]={0};
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			for(int k=0;k<n;k++)
			{
				temp[i][j]=(temp[i][j]+a[i][k]*b[k][j]);
			}
			
		}
	}
	memcpy(c,temp,sizeof temp);
}

void qpow(int f[][N],int a[][N],int n)
{
	while(n)
	{//快速幂
        if(n&1)mul(f,f,a);
        mul(a,a,a);
        n >>= 1;
    }
	return ;
}
int main()
{
//	ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    while(cin>>n>>k)
    {
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
                if(i==j)
           ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发