本文共 1708 字，大约阅读时间需要 5 分钟。

      今天对于昨天的题进行了补题，并且看了几道15年的多校联合题。

     计算满足以下3个条件的n×m矩阵A的数量。   * A(i，j)∈{0,1,2}      * A（i，j）≤A（i+ 1，j)       * A(i，j)≤A(i，j + 1)

对于组合数的各种知识进行了学习，比如一个n*m的矩形，从点（0，0）走到（n，m）的方法数有多少种，是一个经典问题，有c（（n+m），n）种。今天的这个也是用了这个，和一个引理， Lindström–Gessel–Viennot lemma 引理。说的是在一个矩形的一边的所有点a（1,2,...n）到另一边的所有点b(1,2,....n)的不相交的路径的方案数可以表示成一个行列式的答案如下图。

    然后看了B题的公式题，并且看了相关博客，明白了公式的转化。

      计算满足以下条件模数m的n×n矩阵的数量A.

      * A（i，j）∈{0,1,2}   * A(i，j )= A(j，i)     

      * A（i，1） + A（i，2） + ... + A（i，n） = 2，

     * A(1,1) = A(2,2) = ... = A(n，n) = 0。

首先，题目给出的是一个矩阵，我们可以把它转化为一个图，这个图每个点的度为2，并且没有自环，每个点都在一个环中，计算矩阵的方案数，就是计算图的种数。这种转化的思想要学习，看到矩阵，可以转化为图，一个图也可以转化为矩阵。然后，就是写出公式，怎么化简的问题。公式如下图。

f(n)就是n个点的矩阵有多少种，那它本来是（n-1个点），然后又加了1个点，就是从（n-1）个点中挑出k（1...n-3）个点与新来的点组成环，看一下这种挑选的方案数。然后出了挑选一个点，都会因为对称而重复，所以要把挑选一个点的方式独立出来，就是从（n-1）里挑一个点与新点组成一个环，然后方案有（n-1）中，剩余的（n-2）个点的组成这种图的方案数是f（n-2），所以是公式的 （n-1）*f（n-2），剩下的部分是取k（2...n-3）的所有情况。就是如果取（n-1-k）个点与新点组成环，那么方案数为

(n-1)!/(k!*(n-1-k)!)  ， (n-1-k)个点组成环的方式有(n-1-k)!种，剩下的k的点组成图的方式有f（k）种，但是这部分点组成环会有重复的部分，所以有1/2。最终全部乘起来就是  sum（k<n-2）(n-1)!f(k)/k!/2.最终公式计算出来了。

这个公式如何化简那，就是去点那么sum（sigma）。

这个式子是计算n个点的东西，那么再写的（n-1）个点的式子，两者相减，可以把（sigma）消掉，得到一个公式，如下公式：

f(n)=(n-1)*f(n-2)+(n-1)*f(n-1)-(n-1)*(n-2)*f(n-3)/2;

     15年的多校，看了Magician这道题，看了相关题解，其实看到这道题就可以想到是线段树，但是有一个操作不好维护，就是求连续的美丽子序列，一般看过很多线段树区间合并的问题，就感觉这种连续区间问题，可以在每个线段树的节点，多维护几个变量，比如左孩子的包含左右端点的连续区间，最长连续区间，右孩子的包含左右端点的连续区间，最长连续区间，然后，本区间就可以维护了，这是基本的区间合并的做法，这道题看题解都是写的很麻烦。估计细节很麻烦，一般知道怎么写，估计跳出来也得花很长时间。

     还看了Work 这道题，刚看了题，感觉是并查集的路径压缩可以做，网上的题解大多是dfs做的，也有用并查集的，看样子是这份题的签到题。

     The Goddess Of The Moon 月亮女神这道题，用n个给的字符串，求组成长度为m的字符串的方案数，但两个字符串如果能相连，是有条件的，前面的后缀等于后面的前缀，后缀（前缀）不能为1。这样只要符合条件，就可以相连。看了很多博客，多是说dp+矩阵优化，应该像斐波那契数列一样，可以用矩阵快速幂来优化递推的速度吧。这道题主要是构造矩阵费些事，开始矩阵快速幂后，这道题就算结束了。

     学习新知识，巩固旧知识，努力提升自己。

转载地址：https://blog.csdn.net/a1046765624/article/details/81137907 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！