2018 ICPC 徐州网络赛 K题 Morgana Net

本文主要是介绍2018 ICPC 徐州网络赛 K题 Morgana Net，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

求第迭代t次后的矩阵卷积。

题解：

输入给出两个矩阵An，Bm

建立一个矩阵Cn*n，将矩阵A中的元素以此放到矩阵C的第一行

我们将卷积的过程构造成一个转移矩阵，然后用矩阵快速幂解决

构造方法：

考虑点a，它周围的点a1,a2,a3,a4,a5......要参与卷积的计算中

设点a在矩阵C中位于第y列，点ai在矩阵C中位于第xi列

我们将转移矩阵D的D[xi][y]赋值为点ai需要乘矩阵B中的数

那么C*D^t 的第一行的1的个数就是答案。

代码：

#include<bits/stdc++.h>
#define mod 1000000007
#define INF 1e17
#define eps 1e-10
#define pi 3.141592653589793
#define LL unsigned long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
int n,m;
struct Mx
{bool m[65][65];Mx(){memset(this,0,sizeof(Mx));}friend Mx operator * (Mx& a,Mx&b){Mx c;for(int i=1;i<=n;i++)for (int j=1;j<=n;j++) if (a.m[i][j])for (int k=1;k<=n;k++)c.m[i][k]=c.m[i][k]^(a.m[i][j]&b.m[j][k]);return c;}
}e;Mx qumi(Mx a,int y)
{Mx res=e;while(y){if (y&1) res=res*a;a=a*a;y>>=1;}return res;
}int main()
{int T;sc(T);for (int i=1;i<65;i++) e.m[i][i]=1;while(T--){int N,M,t;Mx a,b,c;sccc(N,M,t);for (int i=1;i<=N;i++)for (int j=1;j<=N;j++){int x;sc(x);a.m[1][(i-1)*N+j]=x&1;}for (int i=1;i<=M;i++)for (int j=1;j<=M;j++){int x;sc(x);b.m[i][j]=x&1;}n=N*N; m=M/2;for (int i=1;i<=N;i++)for (int j=1;j<=N;j++)for (int p=i-m;p<=i+m;p++)for (int q=j-m;q<=j+m;q++){if (p<1 || p>N || q<1 || q>N ) continue;c.m[(p-1)*N+q][(i-1)*N+j]=b.m[p-i+m+1][q-j+m+1];}b=qumi(c,t);b=a*b;int ans=0;for (int i=1;i<=n;i++) if (b.m[1][i]) ans++;printf("%d\n",ans);}return 0;
}