矩阵快速幂 例4:灯环的状态

xiaoxiao2021-02-28  46

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int n,m; int a[105][105],b[105][105]; int c[105][105]; void mu(int a[][105],int b[][105],int n){ memset(c,0,sizeof c); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ c[i][1]+=(a[j][1]*b[i][j]); c[i][1]%=2; } } for(int i=1;i<=n;i++)    a[i][1]=c[i][1]; return; } void answer(int a[][105],int k){ while(k){ if(n&1) mu(a,b,n); mu(b,b,n); k>>=1; } return; } int main(){ freopen("6.in","r",stdin); freopen("6.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i][1]); } memset(b,0,sizeof b); b[1][1]=1;b[1][n]=1; for(int i=2;i<=n;i++){ b[i][i]=1; b[i][i-1]=1; } answer(a,m); for(int i=1;i<=n;i++){ printf("%d ",a[i][1]); } return 0; } 
转载请注明原文地址: https://www.6miu.com/read-2623070.html

最新回复(0)