首页 > 其他分享 >【XXSY】棋盘(矩阵乘法,trick)

【XXSY】棋盘(矩阵乘法,trick)

时间:2022-10-31 07:58:44浏览次数:99  
标签:ch int 矩阵 top1 trick 第二个 XXSY 答案 乘法

题面

棋盘

题解

直接的想法是矩阵加速 DP,记录两行的 DP 状态,用一个大小为 \(2n\times 2n\) 的矩阵记录,每次相当于询问一段区间的矩阵乘积,如果使用线段树维护的话是 \(O(n^3q\log q)\) 的。

使用优化可以做到 \(O(n^3q+n^2q\log q)\),下文算法中的优化方法与此优化方法类似,先略去。

注意到询问的 \(l,r\) 是单调的,有一个 trick:

  • 对于一类问题:在序列尾部加入、首部删除,信息不具有可减性,询问当前序列时,不妨维护两个栈,分别代表 \([l,m]\) 和 \([m+1,r]\),其中第一个栈维护 \([l,m]\) 每个后缀的答案(顺便也维护了整体答案),第二个栈维护 \([m+1,r]\) 整体的答案。

    加入时(\(r\) 增大)在第二个栈中插入,并更新第二个栈整体的答案。

    删除时(\(l\) 增大)若第一个栈非空,直接删除第一个栈的首元素并利用记录的后缀信息更新第一个栈整体的答案,否则将第二个栈复制到第一个栈并清空第二个栈,然后暴力计算存储第一个栈每一个后缀的答案。

    询问时合并第一个栈整体答案和第二个栈整体答案即可。

复杂度降至 \(O(n^3q)\)。

接下来是优化矩阵乘法:

  • 更新第二个栈整体的答案、暴力计算第一个栈每一个后缀的答案:这两步中的矩乘都是一个矩阵乘上一个稀疏矩阵(只有 \(O(n)\) 个元素),可以加速到 \(O(n^2)\)。

  • 询问时合并第一个栈整体答案和第二个栈整体答案:由于我们已经知道了初始矩阵(一个列向量),我们直接用这个列向量先乘第一个矩阵得到一个新的列向量,再用这个新的列向量乘第二个矩阵即可。列向量乘矩阵也是 \(O(n^2)\) 的。

    上面线段树做法中提及的优化就和这里类似。

复杂度降至 \(O(n^2q)\)。

实际上可以不需要特殊考虑第二种特殊情况,因为列向量其实也是稀疏矩阵。

常数和空间有一点点大(因为矩阵大小是 \(2n\),所以会乘 \(4\) 倍)。

#include<bits/stdc++.h>

#define N 100010
#define re register

using namespace std;

namespace modular
{
	const int mod=998244353;
	inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
	inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
	inline int mul(int x,int y){return 1ll*x*y%mod;}
	inline void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
}using namespace modular;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

const int fx[]={1,2,2,1},fy[]={-2,-1,1,2};

int n,nn,q;
char s[N][21];

struct Matrix
{
	int a[41][41];
	Matrix(bool opt=0)
	{
		for(int i=1;i<=nn;i++)
			for(int j=1;j<=nn;j++)
				a[i][j]=(i==j?opt:0);
	}
}b[N];

Matrix mula(const Matrix &a,const Matrix &b)
{
	Matrix c(0);
	for(re int i=1;i<=nn;i++)
	{
		for(re int j=1;j<=nn;j++)
		{
			if(!a.a[i][j]) continue;
			for(re int k=1;k<=nn;k++)
				Add(c.a[i][k],mul(a.a[i][j],b.a[j][k]));
		}
	}
	return c;
}

Matrix mulb(const Matrix &a,const Matrix &b)
{
	Matrix c(0);
	for(re int i=1;i<=nn;i++)
	{
		for(re int j=1;j<=nn;j++)
		{
			if(!b.a[i][j]) continue;
			for(re int k=1;k<=nn;k++)
				Add(c.a[k][j],mul(a.a[k][i],b.a[i][j]));
		}
	}
	return c;
}

int top1,top2;
int sta2[N];
Matrix sum1[N>>1],sum2;

inline void pop()
{
	if(top1) top1--;
	else
	{
		assert(top2);
		sum1[0]=sum2=Matrix(1);
		while(top2)
		{
			top1++;
			sum1[top1]=mulb(sum1[top1-1],b[sta2[top2]]);
			top2--;
		}
		top1--;
	}
}

inline void insert(const int id)
{
	sta2[++top2]=id;
	sum2=mula(b[id],sum2);
}

int main()
{
	n=read(),nn=n<<1,q=read();
	sum1[0]=sum2=Matrix(1);
	int nl=1,nr=0;
	while(q--)
	{
		char opt[4];
		scanf("%s",opt);
		if(opt[0]=='A')
		{
			++nr;
			scanf("%s",s[nr]+1);
			for(int i=1;i<=n;i++)
			{
				if(s[nr][i]=='#') continue;
				for(int j=0;j<4;j++)
				{
					int xx=fx[j]-1,yy=i+fy[j];
					if(yy<1||yy>n) continue;
					b[nr].a[i][xx*n+yy]=1;
				}
			}
			for(int i=1;i<=n;i++)
				b[nr].a[n+i][i]=1;
			if(nr>nl) insert(nr);
		}
		if(opt[0]=='D')
		{
			if(nr>nl) pop();
			++nl;
		}
		if(opt[0]=='Q')
		{
			int u=read(),v=read();
			if(nr<nl)
			{
				puts("0");
				continue;
			}
			if(s[nl][u]=='#')
			{
				puts("0");
				continue;
			}
			Matrix res(0);
			res.a[u][1]=1;
			res=mulb(sum1[top1],res);
			for(int i=1;i<=nn;i++)
				for(int j=2;j<=nn;j++)
					res.a[i][j]=0;
			res=mulb(sum2,res);
			printf("%d\n",res.a[v][1]);
		}
	}
	return 0;
}
/*
5 10
Add .....
Add .....
Que 3 1
*/

标签:ch,int,矩阵,top1,trick,第二个,XXSY,答案,乘法
From: https://www.cnblogs.com/ez-lcw/p/16842990.html

相关文章

  • 【XSY4206】QWQ(trick)
    两个问题的解决方法感觉很妙:一、给你若干棵树\(T_1,T_2,\cdots,T_k\),设\(f(T_i,u,v)\)为树\(T\)中\(lca(u,v)\)的深度,问如何优美地表示\(g(u,v)=\min_{i=1}^kf(......
  • 【XSY3312】路径(path)(trick)
    原题就不说了,记录一下其中要用的一个trick。定理:对于一个\(1\simn\)的随机排列,它的前缀最大值的期望个数为\(O(\logn)\)。证明:考虑元素\(x\)作为前缀最大值的概......
  • 使用for语句实现9*9乘法表
    问题9*9乘法表的数量较大,直接打印需用大量的代码,如何用更简单的方法实现对9*9乘法表的打印。方法运用for循环结构对1-9进行循环处理,以得到9*9乘法表及运算结果解决此类问......
  • 【ABC196F】Substring 2(多项式乘法)
    我竟然能在AT当场做出F题!哦,是ABC啊,没事了。以下的字符串均从\(1\)开始记位。以下设\(S_i\)表示字符串\(S\)的第\(i\)位,\(S(l,r)\)表示字符串\(S\)的第......
  • The 2021 ICPC Asia Nanjing Regional Contest E.Paimon Segment Tree 区间合并线段树
    The2021ICPCAsiaNanjingRegionalContestE.PaimonSegmentTree区间合并线段树/维护矩阵乘法题目大意给定长度为的序列,要求支持区间加操作,同时对操作记录历史版本,查......
  • some tricks
    sometricks多从宏观角度想问题,别被微观困住了十进制快速幂防止写高精树的重心在树的dfn序列上的带权中点的到根的路径上组合数:\(\binom{n}{m}=\binom{n-1}{m-1}+\bi......
  • glm 库中的数据排布和乘法
    glm中乘法和求逆运算的结果 //56*13//24glm::vec2x(5,6);glm::mat2m(1,2,3,4);//memorylocates1234tooprintf(......
  • 用for打印九九乘法表
    packagecom.jiemo.struct;publicclassForShabi4{publicstaticvoidmain(String[]args){//1.先打印第一列//2.把固定的i......
  • 时序乘法器与序列乘法器
    今天学习了时序乘法器与序列乘法器,时序乘法器的思路是利用时钟做周期性乘法,具体内容见书籍《verilog应用设计实例》的290页,代码如下:moduletest_net(x_in,y_in,clk,i......
  • 2 道用到同个贪心 trick 的题目
    你别急,我可能不会。https://www.luogu.com.cn/problem/P4437https://www.luogu.com.cn/problem/UVA1205......