Hzao's Blog

（这是一篇水贴）

在把1到n这n个数依次入栈的情况下，如何判断出栈的顺序是否合法？

如果仅仅要求顺序合法，我们可以在已经得到了一个出栈序列的情况下，以如下的方式判断。

         int A=1,B=1;
         stack s;
         while(A<=n){
             if(a[A]==B){
                 A++;B++;
             }
             else if(!s.empty()&&s.top()==a[A]){
                 s.pop();
                 A++;
             }
             else if(B<=n){
                 s.push(B++);
             }
             else {
                 break;//不合法
             }
         }

我们可以以生成全排列的方法，借用这种判断方式来暴力求出合理的出栈顺序的数量。（当然，可以数论直接求解）

也可以直接高效生成(以下代码来自SE大佬)：

      inline void dfs(int s) {
      if(cnt == n) {
      num++;
      /* 
      for (int i = 1;i <= n; ++i) printf("%d", c[i]);  
      printf("\n");  
      */  
      return;  
  }
  if (top > 0) {
      int tp = a[top--];  
      c[++cnt] = tp;  
      dfs(s);  
      a[++top] = tp;
      cnt--;   
  }
  if (s <= n) { 
      a[++top] = s;  
      dfs(s+1);  
      top--;  
   }  
 }  
  int main(){  
      scanf("%d", &n);  
      dfs(1); 
      printf("%d", num);  
      return 0;  
  }  

写在最前面的话

由于自己太弱了，写这个来总结一下，方便复习。很多内容总结自维基百科（链接1、链接2）和李煜东《算法竞赛进阶指南》。

适用范围

一个矩阵的列数等于另一个矩阵的行数时，它们的乘法才有意义。

运算方法

对于一个的矩阵和一个的矩阵，它们的乘积 是一个 的矩阵。

矩阵和矩阵乘积中的元素,等于矩阵第行的个数和矩阵第列的个数分别相乘的和。 即：

   

矩阵乘法同数的乘法一样，有结合律、分配律。但是交换因数后不一定能满足的形式，即m不一定等于n，并且就算满足也不一定结果相等，所以矩阵乘法不满足乘法交换律。

纯乘法的代码实现

1.计算函数。由于自己太弱了，加上时间有限，写了一份很水的代码。

但是这里必须固定 、 的数组大小，可能vector可以解决这个问题？欢迎大佬们指教。

#include<cstdio>
int A[2][3]={
	{1,2,3},
	{4,5,6}
};
int B[3][4]={
	{1,2,3,4},
	{5,6,7,8},
	{9,10,11,12}
};
int c[2][4];
int n,m;
void mul(int a[][3],int b[][4],int n,int m,int p){
	for(int i=0;i<n;++i){//n 乘积的行数 
		for(int j=0;j<m;++j){//m 乘积的列数 
			for(int k=0;k<p;++k){//p 即共有的维 
				c[i][j]+=a[i][k]*b[k][j];
			}
			printf("c[%d][%d]=%d\n",i,j,c[i][j]);
		}
	}
}
int main(){
	mul(A,B,2,4,3);//计算A*B,并保存到c[][4]数组中 
	return 0;
}

2.有一种边读入边计算的写法：

	scanf("%lld%lld%lld",&n,&p,&m);
	for(long long i=1;i<=n;++i){
		for(long long j=1;j<=p;++j){
			scanf("%lld",&a[i][j]);
		}
	}
	for(long long i=1;i<=p;++i){
		for(long long j=1;j<=m;++j){
			scanf("%lld",&b[i][j]);
			for(long long k=1;k<=n;++k){//此处k枚举的并非是公共维
				ans[k][j]+=a[k][i]*b[i][j];
			}
		}
	}

需要注意的是，这里的k的含义与上一份代码不同。由于已经枚举了公共边（即第7行枚举的）和列数，这里只需要枚举乘积的行数。仍然是三维。

我也不知道自己怎么就写了这么个没用的玩意。

用途

矩阵的一个重要用途是解线性方程组。线性方程组中未知量的系数可以排成一个矩阵，加上常数项，则称为增广矩阵。另一个重要用途是表示线性变换，即是诸如
之类的线性函数的推广。

——维基百科

1.其实蒟蒻的我并不知道怎么解线性方程组，但是对于矩阵加速线性变换有一些体会。让我们考虑一种比较特殊的矩阵乘法：和。由定义可知，它们的乘积仍然是一个的矩阵。那么有什么用呢？我们可以借助快速幂的思想，利用矩阵乘法的分配律、结合律，降低时间复杂度。

例如，POJ3070 这道题要求斐波那契数列第项mod（给定,）的值。我们可以设一个的矩阵来存放，然后通过设立方程，求出一个的矩阵，使得得到的的矩阵，满足。于是，我们可以把时间复杂度由降低到。
我们可以通过设未知数解方程，使一个矩阵满足一定的性质。例如，当我们写快速计算矩阵乘法的函数时，函数里默认的矩阵（用于存放答案）应该初始化为什么呢？（计算快速幂时将对应变量初始化为1）如果全部初始化为0，就会导致任何符合条件的矩阵与其相乘都为0。

通过解方程，可以发现，一个的矩阵

   

与任何一个满足的的矩阵相乘，结果仍然等于这个的矩阵。

因此，我们可以把这个矩阵初始化为如上的矩阵，其作用等同于计算快速幂时的1；

2.以后遇到再来补充。