专题总结（矩乘）

矩阵乘法 总结

---

行列对应关系

$S$矩阵第$i$行顺时针翻转$90$度,与$T$矩阵第$j$列横向对应相乘（就是左右相乘），结果存在$S$矩阵$(i,j)$这一位置。

还有，给矩阵赋值时，注意第一维是横坐标，第二维是纵坐标。

知识整理

$$\sum_{S\subseteq[n]}(\sum_{i=1}^n[i\in S])^k=\sum_{i=1}^n\binom{k}{i}*i^k$$
原理：左边的$\sum$枚举了$\{1,2,...n\}$的所有子集$S$,括号内是子集大小$|S|$;右边只是合并了所有子集大小相同的情况。

牛继电器

$n$个点的有向图,求点$1$到点$n$经过$k$条边的最短路。

• $n\leq100,k\leq10^9$

看起来很板啊。
设起始矩阵$S$,运算矩阵$T$。初始化$S,T$边权为$\infty$，给$T$矩阵赋边权，然后矩阵快速幂$k$次（从原图走$k-1$次，因原图相当于已走一条边），即可得答案。
$S*T^k$上第$i$行第$j$列的意义是：从$i$到$j$走$k$步所经最短距离。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=105;
int k,m,s,t,n,num[1000005];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
struct Matrix
{
  int a[205][205];
  Matrix(){memset(a,0,sizeof(a));}
  il int * operator [](re int x){return a[x];}
  Matrix operator *(Matrix b)
  {
    Matrix c;memset(c.a,63,sizeof(c.a));
    fp(k,1,n)
      fp(i,1,n)
      fp(j,1,n)
      c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
    return c;
  }
}S,T;
int main()
{
  k=gi();m=gi();s=gi();t=gi();
  memset(S.a,63,sizeof(S.a));memset(T.a,63,sizeof(T.a));
  fp(i,1,m)
    {
      re int w=gi(),u=gi(),v=gi();
      if(!num[u]) num[u]=++n;if(!num[v]) num[v]=++n;
      T[num[u]][num[v]]=T[num[v]][num[u]]=min(T[num[u]][num[v]],w);
    }
  fp(i,1,n) S.a[i][i]=0;
  while(k)
    {
      if(k&1) S=S*T;
      T=T*T;
      k>>=1;
    }
  printf("%d\n",S[num[s]][num[t]]);
  return 0;
}

好像有个思路拓展：[TJOI2017]可乐题解

Homework

准备咕

Painting Machines

从$n$个集合$\{1, 2\},\{2,3\},...,\{n,n+1\}$选择$k$个使得并集是$\{1,2,...,n+1\}$,求方案数。

• $n\leq10^6$
  题解

Permanent

咕咕咕