2 条题解

  • 0
    @ 2025-10-8 16:52:37
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    struct node
    {
    	LL a[31][31];
    	node(){ memset(a, 0, sizeof a);}
    };
    int n, K; LL P;
    
    node operator*(node A, node B) {
    	node C;
    	for(int i=1; i<=n; i++)
    		for(int j=1; j<=n; j++)
    			for(int k=1; k<=n; k++)
    				C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % P;
    	return C;
    }
    node operator +(node A, node B) {
    	node C;
    	for(int i=1; i<=n; i++)
    		for(int j=1; j<=n; j++)
    			C.a[i][j] = (A.a[i][j] + B.a[i][j]) % P;
    	return C;
    }
    node qpow(node A, int b) {
    	node C; for(int i=1; i<=n; i++) C.a[i][i] = 1;
    	for(; b; b >>= 1) {
    		if(b & 1) C = C * A;
    		A = A * A;
    	}
    	return C;
    }
    node solve(node A, int b) {
    	if(b == 1) return A;
    	node t = solve(A, b / 2);
    	if(b & 1) return t + t * qpow(A, b / 2) + qpow(A, b);
    	else return t + t * qpow(A, b / 2);
    }
    int main() {
    	scanf("%d%d%lld", &n, &K, &P);
    	node A;
    	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%lld", &A.a[i][j]);
    	node ans = solve(A, K);
    	for(int i=1; i<=n; i++) {
    		for(int j=1; j<n; j++) printf("%lld ", ans.a[i][j]);
    		printf("%lld\n", ans.a[i][n]);
    	}
    	return 0;
    }
    
    • 0
      @ 2025-10-8 16:52:23


      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      struct node
      {
      	LL a[31][31];
      	node(){ memset(a,0,sizeof a);}
      };
      int n,K;LL P;
      

      node operator*(node A, node B)//如果参数是(node &A, node &B)则A和B不能是函数 { node C; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) C.a[i][j]=(C.a[i][j]+A.a[i][k]B.a[k][j])%P; return C; } node operator +(node A,node B) { node C; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) C.a[i][j]=(A.a[i][j]+B.a[i][j])%P; return C; } node qpow(node A,int b) { node C;for(int i=1;i<=n;i++)C.a[i][i]=1; for(;b;b>>=1) { if(b&1)C=CA; A=A*A; } return C; } node solve(node A,int b) { if(b==1) return A; node t=solve(A,b/2); if(b&1) return t + t * qpow(A,b/2) + qpow(A,b) ; else return t + t * qpow(A,b/2) ; } int main() { scanf("%d%d%lld",&n,&K,&P); node A; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&A.a[i][j]); node ans=solve(A,K); for(int i=1;i<=n;i++) { for(int j=1;j<n;j++)printf("%lld ",ans.a[i][j]); printf("%lld\n",ans.a[i][n]); } return 0; }

      </p>





      • 1

      *【矩阵乘法】2:矩阵幂级数和[POJ3233]

      信息

      ID
      597
      时间
      1000ms
      内存
      128MiB
      难度
      6
      标签
      递交数
      178
      已通过
      54
      上传者