【BZOJ2973】石头游戏 矩阵乘法

【BZOJ2973】石头游戏

Description

石头游戏的规则是这样的。

石头游戏在一个n行m列的方格阵上进行。每个格子对应了一个编号在0~9之间的操作序列。

操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。它包括:

数字0~9:拿0~9个石头到该格子。

NWSE:把这个格子内所有的石头推到相邻的格子。

D:拿走这个格子的石头。

石头游戏的问题是:当这个石头游戏进行了t秒之后,所有方格中最多的格子有多少个石头。

注意:所有格子的操作同时执行。

Input

第一行三个整数n, m, t, act。

接下来n行,每行m个字符,表示每个格子对应的操作序列。

最后act行,每行一个字符串,表示从0开始的每个操作序列。

Output

一个整数:游戏进行了t秒之后,所有方格中最多的格子有多少个石头。

Sample Input

1 6 10 3
011112
1E
E
0

Sample Output

3
【样例解释】
这是另一个类似于传送带的结构。左边的设备0间隔地产生石头并向东传送。设备1向右传送,直到设备2。10秒后,总共产生了5个石头,2个在传送带上,3个在最右边。
【数据约定】
0≤n, m≤8。
1≤act≤10。
1≤t≤10^9。

题解:跟沼泽鳄鱼那道题差不多,只不过周期变成了60。那我们构造60个转移矩阵f[0..59],它们的乘积为x。那么ans=x^(T/12)*f[0..T%12]。至于怎么构造矩阵。。自己yy一下就好了吧?

又一次get了惨痛的历史教训,矩乘不满足交换律,所以一定要先ans*=x^(T/12)再ans*=f[0..T%12]。

#include <cstdio>
#include <cstring>
#include <iostream>
#define P(A,B) ((A-1)*m+B)
using namespace std;
typedef long long ll;
typedef struct matrix
{
	ll v[100][100];
}M;
M ans,x,emp,f[65];
int n,m,tim,act;
int len[20];
ll maxx;
char A[20][20],B[20][20],ch;
M mmul(M a,M b)
{
	M c=emp;
	int i,j,k;
	for(i=0;i<=n*m;i++)
		for(j=0;j<=n*m;j++)
			for(k=0;k<=n*m;k++)
				c.v[i][j]+=a.v[i][k]*b.v[k][j];
	return c;
}
void pm(int y)
{
	while(y)
	{
		if(y&1)	ans=mmul(ans,x);
		x=mmul(x,x),y>>=1;
	}
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&tim,&act);
	int i,j,k,l,a,b;
	for(i=1;i<=n;i++)	scanf("%s",A[i]);
	for(i=0;i<act;i++)	scanf("%s",B[i]),len[i]=strlen(B[i]);
	for(i=0;i<=n*m;i++)	x.v[i][i]=1;
	ans.v[0][0]=1;
	for(l=0;l<60;l++)
	{
		f[l].v[0][0]=1;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				k=A[i][j-1]-‘0‘,ch=B[k][l%len[k]];
				if(ch>=‘0‘&&ch<=‘9‘)	f[l].v[P(i,j)][P(i,j)]=1,f[l].v[0][P(i,j)]=ch-‘0‘;
				if(ch==‘N‘&&i>1)	f[l].v[P(i,j)][P(i-1,j)]=1;
				if(ch==‘W‘&&j>1)	f[l].v[P(i,j)][P(i,j-1)]=1;
				if(ch==‘S‘&&i<n)	f[l].v[P(i,j)][P(i+1,j)]=1;
				if(ch==‘E‘&&j<m)	f[l].v[P(i,j)][P(i,j+1)]=1;
			}
		}
		x=mmul(x,f[l]);
	}
	pm(tim/60);
	for(i=0;i<tim%60;i++)	ans=mmul(ans,f[i]);
	for(i=1;i<=n*m;i++)	maxx=max(maxx,ans.v[0][i]);
	printf("%lld",maxx);
	return 0;
}
时间: 04-30

【BZOJ2973】石头游戏 矩阵乘法的相关文章

BZOJ2973 : 石头游戏

考虑到$lcm(1,2,3,4,5,6)=60$,所以操作序列每60秒一个循环. 将操作表示成转移矩阵的形式,预处理出前60秒的转移矩阵以及它们的乘积$B$. 那么t秒的转移矩阵为前$t\bmod 60$个转移矩阵的乘积乘以$B^{\lfloor\frac{t}{60}\rfloor}$. 用矩阵快速幂加速计算即可. #include<cstdio> #include<cstring> #define rep(i,n) for(int i=0;i<n;i++) #define

挖坑#1——矩阵乘法

BZOJ1706: [usaco2007 Nov]relays 奶牛接力跑 BZOJ1898: [Zjoi2004]Swamp 沼泽鳄鱼 BZOJ2326: [HNOI2011]数学作业 BZOJ3204: [NOI2013] 矩阵游戏 BZOJ2875: [Noi2012]随机数生成器 BZOJ1009: [HNOI2008]GT考试 BZOJ3231: [Sdoi2008]递归数列 BZOJ1875: [SDOI2009]HH去散步 BZOJ2432: [Noi2011]兔农 BZOJ353

矩阵乘法的Strassen算法详解

题目描述 请编程实现矩阵乘法,并考虑当矩阵规模较大时的优化方法. 思路分析 根据wikipedia上的介绍:两个矩阵的乘法仅当第一个矩阵B的列数和另一个矩阵A的行数相等时才能定义.如A是m×n矩阵和B是n×p矩阵,它们的乘积AB是一个m×p矩阵,它的一个元素其中 1 ≤ i ≤ m, 1 ≤ j ≤ p. 值得一提的是,矩阵乘法满足结合律和分配率,但并不满足交换律,如下图所示的这个例子,两个矩阵交换相乘后,结果变了: 下面咱们来具体解决这个矩阵相乘的问题. 解法一.暴力解法 其实,通过前面的分析

51nod 1137 矩阵乘法

基本的矩阵乘法 中间for(int j=0;i<n;i++)  //这里写错了   应该是j<n 晚上果然  效率不行 等会早点儿睡 //矩阵乘法 就是 两个矩阵 第一个矩阵的列 等与 第二个矩阵的行相同 // 然后ans[i][j] += a[i][k] * b[k][j]; #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 150; int n; ll a[ma

矩阵乘法

矩阵加法就是相同位置的数字加一下,矩阵减法也类似 矩阵乘以一个常数,就是所有位置都乘以这个数 矩阵乘以矩阵 计算规则是,第一个矩阵第一行的每个数字(2和1),各自乘以第二个矩阵第一列对应位置的数字(1和1),然后将乘积相加( 2 x 1 + 1 x 1),得到结果矩阵左上角的那个值3 矩阵的本质就是线性方程式,两者是一一对应关系.如果从线性方程式的角度,理解矩阵乘法就毫无难度.下面是一组线性方程式 矩阵的最初目的,只是为线性方程组提供一个简写形式 下面是严格的证明.有三组未知数 x.y 和 t,

矩阵乘法&lt;简单总结&gt;

原理:矩阵相乘最重要的方法是一般矩阵乘积.它只有在第一个矩阵的 行数 和第二个矩阵的 列数 相同时才可进行.若A为m×n矩阵,B为n×p矩阵,则他们的乘积AB会是一个m×p矩阵. 若A=    a    b    c        d    e    f        g    h    i    B=    A    D        B    E        C    F    A*B=CC=    aA+bB+cC    aD+bE+cF        dA+eB+fC    dD+eE

POJ2778 DNA Sequence Trie+矩阵乘法

题意:给定N个有A C G T组成的字符串,求长度为L的仅由A C G T组成的字符串中有多少个是不含给定的N个字符串的题解: 首先我们把所有的模式串(给定的DNA序列)建Trie,假定我们有一个匹配串,并且在匹配过程到S[i]这个字符时匹配到了Trie上的某个节点t,那么有两种可能: 匹配失败:t->child[S[i]]为空,跳转到t->fail,因此t->fail一定不能是某个模式串的结尾: 匹配成功:跳转到t->child[S[i+1]],因此t->child[S[i

【CDQ】BZOJ 2738 矩阵乘法

题意:给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数 思路: 整体二分+二维树状数组 二分询问的答案mid,将数值小等mid的全部插入二维树状数组 然后查询每个矩阵内的元素个数,若数量>K-1则放左边,否则放右边 继续向下分治,左边二分l-mid,右边mid-r 代码: #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include

codevs矩阵乘法系列

T1:矩阵乘法板子题,练手. #include <map> #include <set> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include

基于OpenMP的矩阵乘法实现及效率提升分析

一.  矩阵乘法串行实现 例子选择两个1024*1024的矩阵相乘,根据矩阵乘法运算得到运算结果.其中,两个矩阵中的数为double类型,初值由随机数函数产生.代码如下: #include <iostream> #include <omp.h> // OpenMP编程需要包含的头文件 #include <time.h> #include <stdlib.h> using namespace std; #define MatrixOrder 1024 #def