2396: 神奇的矩阵

本文主要是介绍2396: 神奇的矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一开始想了个fft 时间复杂度 O(t∗n2log n2) O ( t ∗ n 2 l o g n 2 ) $O( t * n^2 log\ {n^2})$ 应该超时了…
然后看了题解… 随机化…
c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}int n;
struct Matrix { int a[1010][1010]; }a,b,c,r;Matrix mul(Matrix&a,Matrix&b)
{Matrix c;rep(i,1,n) c.a[i][1] = 0;rep(i,1,n) rep(j,1,n)c.a[i][1] += a.a[i][j] * b.a[j][1];return c;
}bool check(Matrix&a,Matrix&b)
{rep(i,1,n) if(a.a[i][1] != b.a[i][1]) return false;return true;
}int main()
{rep(i,1,1000) r.a[i][1] = rand();while(~scanf("%d",&n)){rep(i,1,n) rep(j,1,n) read(a.a[i][j]);rep(i,1,n) rep(j,1,n) read(b.a[i][j]);rep(i,1,n) rep(j,1,n) read(c.a[i][j]);Matrix d = mul(b,r); a = mul(a,d); c = mul(c,r);puts(check(a,c)?"Yes":"No");}   return 0;
}

这篇关于2396: 神奇的矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---