网站建设策划框架,30g月流量网站,赤峰网站建设公司,网站建设注意细节正题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid4965 题目大意
给出矩阵A,BA,BA,B#xff0c;求(AB)n(AB)^n(AB)n。然后对于每个元素%6\% 6%6后取和。 题目大意
我们发现如果直接让AB∗ABAB*ABAB∗AB这样的时间复杂度是n3n^3n3#xff0c;显然不可过。但是我们…正题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid4965 题目大意
给出矩阵A,BA,BA,B求(AB)n(AB)^n(AB)n。然后对于每个元素%6\% 6%6后取和。 题目大意
我们发现如果直接让AB∗ABAB*ABAB∗AB这样的时间复杂度是n3n^3n3显然不可过。但是我们注意到kkk特别小所以我们可以将(AB)n∗nA(BA)n∗n−1B(AB)^{n*n}A(BA)^{n*n-1}B(AB)n∗nA(BA)n∗n−1B 即可然后时间复杂度就变为了O(n2kk3logn)O(n^2kk^3\ log\ n)O(n2kk3 log n) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int Size10;
struct matrix{int a[Size][Size];
}c,ans,z;
int n,K,answer,B,Ans[1100][1100],a[1100][1100],b[1100][1100];
matrix operator*(matrix a,matrix b)
{memset(z.a,0,sizeof(z.a));for(int i0;iSize;i)for(int j0;jSize;j)for(int k0;kSize;k)(z.a[i][j]a.a[i][k]*b.a[k][j])%6;return z;
}
int main()
{while(scanf(%d%d,n,K)){if(n0||K0) return 0;Bn*n-2;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c.a,0,sizeof(c.a));memset(Ans,0,sizeof(Ans));answer0;for(int i0;in;i)for(int j0;jK;j)scanf(%d,a[i][j]);for(int i0;iK;i)for(int j0;jn;j)scanf(%d,b[i][j]);for(int i0;iK;i)for(int j0;jK;j)for(int k0;kn;k)c.a[i][j]b[i][k]*a[k][j];ansc;while(B){if(B1) ansans*c;cc*c;B1;}for(int i0;in;i)for(int j0;jK;j)for(int k0;kK;k)Ans[i][j]a[i][k]*ans.a[k][j];for(int i0;in;i)for(int j0;jn;j){int tmp0;for(int k0;kK;k)tmpAns[i][k]*b[k][j];answertmp%6;}printf(%d\n,answer);}
}
