【每日一题】4月29日题目精讲 dp+数学

题号 NC17134
名称 Symmetric Matrix
来源牛客网暑期ACM多校训练营（第一场）
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
好像一涉及到数学大家就有点懵？

首先我们看这个矩阵满足的条件，矩阵对称和 $a_{ii}=0$ 可以让我们联想到无向图的邻接矩阵（这里其实用了数形结合的思想），即 $a_{ij}$ 表示i点到j点的权值，因为是无向图所以对称， $a_{ii}=0$ 说明没有自环。
那么下一步就是给这个权值赋予一个含义，最好的方法是用它表示边数（因为长度容量等在数形结合的找个“形”里并不好直观的看到）。
如果边权表示边数的话 $\sum a_{ij} = 2$ 实际上就是每个点都连了两条边，那么每个点有且只有两条边的图是什么样子的呢？显然是由若干个简单环组成的（简单环就是没有公共点公共边的环），环中元素个数至少是2（没有自环）。
那么我们考虑用f[i]表示由n个点组成若干个简单环的方法数。
显然f[1]= 0 f[2] = 1 f[3] = 1……
考虑n>3时，从f[n-1]推到f[n]，也就是说已经有n-1个点了要加入第n个点：
加入之后和之前的某个点组成一个二圆环，方案数为： $C^1_{n-1}\times f(n-2)$
加入之和后之前某k-1个点组成一个k圆环，方案数为： $\sum ^{n}_{k=3} (C^{k-1}_{n-1}f(n-k)\times (k-1)!/2)$ （k圆环还有个顺序问题：1234和2341和3412是一样的，所以我们可以固定一个数作为环的起点，方案数为 $(k-1)!$ ，并且无向图从左到右和从右到左是一样（即1234和1432也是一样是）的所以还要除以2）
所以 $f[n] = C^1_{n-1} f(n-2) + \sum ^{n}_{k=3}(C^{k-1}_{n-1}f(n-k)*(k-1)!/2)$
然后我们需要对它进行化简想办法把 $\sum$ 去掉（不同的推法可以写错多个不一样的的f[n]=...但是都要化简，化简是一般思路是把f[n]和f[n-1]表示出来，然后给其中某个乘以一个系数把 $\sum$ 里面的数变成一样的，只是求和的项不同，就可以相减了）。 $f[n] = C^1_{n-1}f(n-2) + \sum ^{n}_{k=3} (C^{k-1}_{n-1}f(n-k)\times (k-1)!/2)$
先表达成分式子形式： $f[n] = C^1_{n-1} f(n-2) + \sum ^{n}_{k=3} (\frac{(n-1)!}{(k-1)! \times (n-k)!}f(n-k)\times (k-1)!/2)$
这个时候你是不是想把(k-1)!划掉？但是划掉之后会有个麻烦的问题： $f[n] = C^1_{n-1}f(n-2) + \sum ^{n}_{k=3} (\frac{(n-1)!f(n-k)}{2(n-k)!})$ 分母上存在一个 $(n-k)！$ ，显然
f[n-1]的分母上也会对应有一个 $(n-k-1)!$ ，他们相差一个n-k，对于求和的每一项来说这个k都是不一样的，没有办法通过乘法把它消除掉。
所以我们考虑调整一下变量k，令x = n-k，于是x的取值范围是[0, n-3]: $f[n] = C^1_{n-1}f(n-2) + \sum ^{n-3}_{x=0} (C^{n-x-1}_{n-1}f(x) \times (n-x-1)!/2)$
$f[n] = C^1_{n-1} f(n-2) + \sum ^{n-3}_{x=0} (\frac{(n-1)!}{(n-x-1)!(x)!} f(x)\times(n-x-1)!/2)$
这个时候把 $(n-x-1)!$ 约分划掉: $f[n] = C^1_{n-1}f(n-2) + \sum ^{n-3}_{x=0} \frac{(n-1)!f(x)}{2(x)!}$
那么f[n-1]就可以表示为： $f[n-1] = C^1_{n-2}f(n-3) + \sum ^{n-4}_{x=0} \frac{(n-2)!f(x)}{2(x)!}$
为了把 $\sum$ 里面的东西变成一致，我们给f[n-1]乘以(n-1) $(n-1)f[n-1] = (n-1)(n-2)f(n-3) + \sum ^{n-4}_{x=0} \frac{(n-1)!f(x)}{2(x)!}$
所以： $f[n]- (n-1)f[n-1] = (n-1)f[n-2] - (n-1)(n-2)f[n-3] + \frac{(n-1)!f[n-3]}{(2(n-3)!}$
$=(n-1)f[n-2] - \frac{1}{2}(n-1)(n-2)f[n-3]$
$f[n] = (n-1)f[n-1] + (n-1)f[n-2] - \frac{1}{2}(n-1)(n-2)f[n-3]$
这样就可以愉快的递推了。
（这里在题解中我故意使用了我推出来几种式子中化简过程最恶心一个（需要换一下变量），希望大家不仅要知道这个题是怎么化简的，还要去了解这个f[n]- (n-1)f[n-1]的思路是怎么来的——当你的式子不太适合这么操作的时候如果知道为什么，也许你也能转化过去，而不是凭运气……）

【每日一题】4月29日题目精讲 dp+数学

活动奖励：

牛客博客开通方式

全站热榜