[FJOI2007] 轮状病毒

2018-08-12

lolifamily

题解

矩阵树 DP 差分

由于内容过长、公式较多，暂时将内容隐藏，请公式恐惧症们做好心理准备。

Problem

Description

轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。

一个 $𝑁$ 轮状基由圆环上 $𝑁$ 个不同的基原子和圆心处一个核原子构成的， $2$ 个原子之间的边表示这 $2$ 个原子之间的信息通道。

如下图所示

$𝑁$ 轮状病毒的产生规律是在一个 $𝑁$ 轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有 $16$ 个不同的 $3$ 轮状病毒，如下图所示：

现给定 $𝑁 (𝑁 \leq 100)$ ，编程计算有多少个不同的 $𝑁$ 轮状病毒

Input

第一行有 $1$ 个正整数 $𝑁$

Output

计算出的不同的 $𝑁$ 轮状病毒数输出

Sample Input

1
3

Sample Output

1
16

法一：行列式

转载自 vfleaking，题解备份

对于新手还是建议去看看基尔霍夫矩阵，这一篇论文挺不错的。

用基尔霍夫矩阵使用高斯消元解行列式，时间复杂度 $𝑂 (𝑛 3)$ 似乎可以 AC。

首先行列式有很多性质：

第 $𝑎$ 行 $\times 𝑘$ 加到第 $𝑏$ 行上去，行列式的值不变
三角行列式的值等于对角线元素之积
第 $𝑎$ 行与第 $𝑏$ 行互换，行列式的值取反
常数 $\times$ 行列式，可以把常数乘到某一行里去

如果你行列式不是很熟，建议先搜搜行列式～不然下面会看晕～

其实如果你仔细观察矩阵，可以发现它是这样的：（消去了病毒中央）

∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ 3 - 1 00 \dots 000 - 1 - 1 3 - 1 0 \dots 0000 0 - 1 3 - 1 \dots 0000 00 - 1 3 \dots 0000 000 - 1 \dots 0000 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0000 \dots 3 - 1 00 0000 \dots - 1 3 - 1 0 0000 \dots 0 - 1 3 - 1 - 1 000 \dots 00 - 1 3 ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣

那么我们现在对行列式进行变换，我们把第 $1$ 行与第 $2$ 行交换，再把第 $2$ 行与第 $3$ 行交换……，再把第 $𝑛 - 1$ 行与第 $𝑛$ 行变换，得到新的行列式：

∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ - 1 3 - 1 0 \dots 0000 0 - 1 3 - 1 \dots 0000 00 - 1 3 \dots 0000 000 - 1 \dots 0000 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0000 \dots 3 - 1 00 0000 \dots - 1 3 - 1 0 0000 \dots 0 - 1 3 - 1 - 1 000 \dots 00 - 1 3 3 - 1 00 \dots 000 - 1 ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣

这个行列式跟一开始的那个行列式的值不一定相等。因为我们是通过 $𝑛 - 1$ 次交换行的操作得到的，为了说话方便我们称一开始的行列式为 $𝐴$ ，上面刚写的行列式为 $𝐵$ 那么由行列式性质得： $𝐴 = (- 1) 𝑛 - 1 \cdot 𝐵$ 现在就可以正大光明地处理 $𝐵$ 了～

利用行列式性质，来手算这个行列式。之所以刚才有那么一步，就是为了方便手算。因为观察 $𝐵$ 矩阵，发现就只剩下左下角的 $- 1$ 、 $3$ 、 $- 1$ 三个倒霉了。

倒数第二行： - 1 000 \dots 00 - 1 3 用第一行的： - 1 3 - 1 0 \dots 0000 乘以 - 1 来消： 0 - 3 10 \dots 00 - 1 3 再用第二行： 0 - 1 3 - 1 \dots 0000 乘以 - 3 来消： 00 - 8 3 \dots 00 - 1 3

这样就有了初步感觉了～

现在把这个过程一般化：

第 𝑘 个和第 𝑘 + 1 个： 00 \dots 𝐹 (𝑘) 𝐺 (𝑘) 00 \dots - 1 3 总能找到上面的某一行 00 \dots - 1 3 - 1 0 \dots 00 乘以 𝐹 (𝑘) 来消： 00 \dots 0 𝐹 (𝑘 + 1) 𝐺 (𝑘 + 1) 0 \dots - 1 3

于是得到：

{𝐹 (𝑘 + 1) = 𝐺 (𝑘) + 3 𝐹 (𝑘) 𝐺 (𝑘 + 1) = - 𝐹 (𝑘)

整合一下： $𝐹 (𝑘 + 1) = 3 𝐹 (𝑘) - 𝐹 (𝑘 - 1)$

从初始的行和消了一次之后的行中取得边界条件： $𝐹 (1) = - 1, 𝐹 (2) = - 3$ 最终一定会变为下面这种情况：

倒数第二行： 0000 \dots 𝐹 (𝑛 - 3) 𝐺 (𝑛 - 3) - 1 3 用倒数第四行： 0000 \dots - 1 3 - 1 0 乘以 𝐹 (𝑛 - 3) 来消： 0000 \dots 0 𝐹 (𝑛 - 2) 𝐺 (𝑛 - 2) - 1 3 用倒数第三行： 0000 \dots 0 - 1 3 - 1 乘以 𝐹 (𝑛 - 2) 来消： 0000 \dots 00 𝐹 (𝑛 - 1) - 1 𝐺 (𝑛 - 1) + 3

好现在搞定了倒数第二行，来看看成果： $(𝑓 = 𝐹 (𝑛 - 1) - 1, 𝑔 = 𝐺 (𝑛 - 1) + 3)$

∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ - 1 3 - 1 0 \dots 0000 0 - 1 3 - 1 \dots 0000 00 - 1 3 \dots 0000 000 - 1 \dots 0000 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0000 \dots 3 - 1 00 0000 \dots - 1 3 - 1 0 0000 \dots 0 - 1 3 - 1 0000 \dots 00 𝑓 𝑔 3 - 1 00 \dots 000 - 1 ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣

好，现在来搞倒数第一行。和倒数第二行的方法是类似的。

再设函数 $𝐻 (𝑘)$ 和 $𝐼 (𝑘)$ ，意义与 $𝐹 (𝑘)$ 、 $𝐺 (𝑘)$ 类似，得：

{𝐻 (𝑘 + 1) = 𝐼 (𝑘) + 3 𝐻 (𝑘) 𝐼 (𝑘 + 1) = - 𝐻 (𝑘)

其实跟 $𝐹$ 、 $𝐺$ 的递推式是一样的我会乱说？ $𝐻 (𝑘 + 1) = 3 𝐻 (𝑘) - 𝐻 (𝑘 - 1)$ 边界条件是： $𝐻 (1) = 3, 𝐻 (2) = 8$ 最后使劲搞一搞，倒数第一行就成了：

00000 \dots 00 𝐻 (𝑛 - 1) 𝐼 (𝑛 - 1) - 1

再来看成果： $(ℎ = 𝐻 (𝑛 - 1), 𝑖 = 𝐼 (𝑛 - 1) - 1)$

∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ - 1 3 - 1 0 \dots 0000 0 - 1 3 - 1 \dots 0000 00 - 1 3 \dots 0000 000 - 1 \dots 0000 ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ 0000 \dots 3 - 1 00 0000 \dots - 1 3 - 1 0 0000 \dots 0 - 1 3 - 1 0000 \dots 00 𝑓 𝑔 0000 \dots 00 ℎ 𝑖 ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣

用倒数第二行来消倒数第一行，得：

0000 \dots 000 𝑖 - 𝑔 \cdot (ℎ 𝑓)

现在这个行列式已经是三角行列式了，它的值就是对角线元素之积。于是： $𝐵 = (- 1) \times (- 1) \times (- 1) \times \dots \times 𝑓 (𝑖 - 𝑔 \cdot ℎ 𝑓)$ 一共有 $𝑛 - 2$ 个 $- 1$ 。

如前文所述： $𝐴 = (- 1) 𝑛 - 1 𝐵$

又因为： $𝐵 = (- 1) 𝑛 - 2 (𝑓 \cdot 𝑖 - 𝑔 \cdot ℎ)$

于是有： $𝐴 = (- 1) 2 𝑛 - 3 (𝑓 \cdot 𝑖 - 𝑔 \cdot ℎ) = - 𝑓 \cdot 𝑖 + 𝑔 \cdot ℎ$

带入 $𝑓$ 、 $𝑔$ 、 $ℎ$ 、 $𝑖$ 的值得： $𝐴 = - (𝐹 (𝑛 - 1) - 1) (𝐼 (𝑛 - 1) - 1) + (𝐺 (𝑛 - 1) + 3) 𝐻 (𝑛 - 1)$

带入 $𝐻$ 、 $𝐼$ 的值： $𝐴 = - (𝐹 (𝑛 - 1) - 1) (- 𝐻 (𝑛 - 2) - 1) + (- 𝐹 (𝑛 - 2) + 3) 𝐻 (𝑛 - 1)$

然后再展开…… 回忆下 $𝐹$ 、 $𝐻$ 的递推式

𝐴 = 𝐹 (𝑛 - 1) 𝐻 (𝑛 - 2) + 𝐹 (𝑛 - 1) - 𝐻 (𝑛 - 2) - 1 - 𝐹 (𝑛 - 2) 𝐻 (𝑛 - 1) + 3 𝐻 (𝑛 - 1) = 𝐻 (𝑛) + 𝐹 (𝑛 - 1) + 𝐹 (𝑛 - 1) 𝐻 (𝑛 - 2) - 𝐹 (𝑛 - 2) 𝐻 (𝑛 - 1) - 1 = 𝐻 (𝑛) + 𝐹 (𝑛 - 1) + ∣ 𝐹 (𝑛 - 1) 𝐻 (𝑛 - 1) 𝐹 (𝑛 - 2) 𝐻 (𝑛 - 2) ∣ - 1

发现不能化简了？没关系！在行列式上动动手脚吧！

FH 定理

对于任意大于 $2$ 的 $𝑘$ 有：

∣ 𝐹 (𝑘 - 1) 𝐻 (𝑘 - 1) 𝐹 (𝑘 - 2) 𝐻 (𝑘 - 2) ∣ = ∣ 𝐹 (2) 𝐻 (2) 𝐹 (1) 𝐻 (1) ∣

证明：对于行列式：

∣ 𝐹 (𝑘 - 1) 𝐻 (𝑘 - 1) 𝐹 (𝑘 - 2) 𝐻 (𝑘 - 2) ∣

把行列式最下面的行取反，则行列式的值取反：

- ∣ 𝐹 (𝑘 - 1) 𝐻 (𝑘 - 1) - 𝐹 (𝑘 - 2) - 𝐻 (𝑘 - 2) ∣

把行列式的上面的行乘以 $3$ 加到下面去：

- ∣ 𝐹 (𝑘 - 1) 𝐻 (𝑘 - 1) 3 𝐹 (𝑘 - 1) - 𝐹 (𝑘 - 2) 3 𝐻 (𝑘 - 1) - 𝐻 (𝑘 - 2) ∣

特意构造的递推式出现了：

- ∣ 𝐹 (𝑘 - 1) 𝐻 (𝑘 - 1) 𝐹 (𝑘) 𝐻 (𝑘) ∣

有点眉目了～把第一行与第二行调换位置，行列式的值取反：

∣ 𝐹 (𝑘) 𝐻 (𝑘) 𝐹 (𝑘 - 1) 𝐻 (𝑘 - 1) ∣

一目了然，这是 k++ 后的行列式的样子。（Pascal 同学早日转 C++）

那么立即推出：

∣ 𝐹 (𝑘 - 1) 𝐻 (𝑘 - 1) 𝐹 (𝑘 - 2) 𝐻 (𝑘 - 2) ∣ = ∣ 𝐹 (2) 𝐻 (2) 𝐹 (1) 𝐻 (1) ∣

FH 定理得证。

利用 FH 定理，把 $𝐹 (1) = - 1, 𝐹 (2) = - 3, 𝐻 (1) = 3, 𝐻 (2) = 8$ 带入：

∣ 𝐹 (𝑛 - 1) 𝐻 (𝑛 - 1) 𝐹 (𝑛 - 2) 𝐻 (𝑛 - 2) ∣ = - 1

于是就爽了嘛！

∴ 𝐴 = 𝐻 (𝑛) + 𝐹 (𝑛 - 1) + (- 1) - 1 = 𝐻 (𝑛) + 𝐹 (𝑛 - 1) - 2

进一步我们发现…… 设 $𝑅 (𝑛) = 𝐻 (𝑛) + 𝐹 (𝑛 - 1) - 2$

那么立即有：

𝑅 (𝑛) = 3 𝐻 (𝑛 - 1) - 𝐻 (𝑛 - 2) + 3 𝐹 (𝑛 - 2) - 𝐹 (𝑛 - 3) - 2 = 3 (𝑅 (𝑛 - 1) + 2) - (𝑅 (𝑛 - 2) + 2) - 2 = 3 𝑅 (𝑛 - 1) - 𝑅 (𝑛 - 2) + 2

所以，轮状病毒的方案数满足递推式 $𝐹 (𝑛) = 3 𝐹 (𝑛 - 1) - 𝐹 (𝑛 - 2) + 2$ ，其中 $𝐹 (1) = 1, 𝐹 (2) = 5$ 。

然后随手写一个高精度就可以过了～

法二：DP

转载自 boshi

如果用 f[x] 表示加入了 $𝑥$ 个周围的点后的方案数，我们首先想到的递推式是： $𝑓 [𝑖] = 𝑖 \sum 𝑗 = 1 𝑓 [𝑖 - 𝑗] \cdot 𝑗$

解释：最后加入的 $𝑗$ 个点每个都可能与中心点连边，将所有方案数累加即可。

但是，第一个点永远不会与第 $𝑛$ 个点连边，因此方案数统计并不准确。

我们再设： $𝑔 [𝑖] = 𝑖 \sum 𝑗 = 2 𝑓 [𝑖 - 𝑗] \cdot 𝑗 \cdot (𝑗 - 1)$

解释：如果有 $𝑗$ 个周围的点连成一条，且跨越了 $1$ 和 $𝑛$ ，我们将所有这样的情况累加到答案中去。如果这样的点有 $𝑗$ 个，剩下的点肯定不与这 $𝑗$ 个点相连，所以连边方案数就是 $𝑓 [𝑖 - 𝑗]$ ，这 $𝑗$ 个点有 $(𝑗 - 1)$ 种选法（跨越 $1$ 和 $𝑛$ ），与中心点连边的方案数是 $𝑗$ ，根据乘法原理，答案要累加 $𝑓 [𝑖 - 𝑗] \cdot 𝑗 \cdot (𝑗 - 1)$ 。

这样的 $𝑓 [𝑛] + 𝑔 [𝑛]$ 就是我们要求的轮状病毒的数量。

下面我们思考如何快速求出 $𝑓$ 和 $𝑔$ 。

多阶差分

首先分析 $𝑓 [𝑖]$ 。如果我们可以求出所有 $𝑓 [𝑖 - 𝑗] \cdot 𝑗$ 的前缀和，这个问题就变得非常方便了。

问题是对于不同的 $𝑖$ ，这个前缀和中每一项都会发生变化。

那如果我们知道了变化的量是多少呢？于是我们就对前缀和进行差分。

Δ 𝑓 [𝑖] = 𝑖 \sum 𝑗 = 1 𝑓 [𝑖 - 𝑗] \cdot 𝑗 - 𝑖 - 1 \sum 𝑗 = 1 𝑓 [𝑖 - 1 - 𝑗] \cdot 𝑗 = 𝑖 \sum 𝑗 = 0 𝑓 [𝑖 - 𝑗] \cdot 𝑗 - 𝑖 - 1 \sum 𝑗 = 0 𝑓 [𝑖 - 1 - 𝑗] \cdot 𝑗 (𝑓 [𝑖] \cdot 0 = 𝑓 [𝑖 - 1] \cdot 0 = 0) = 𝑖 \sum 𝑗 = 0 𝑓 [𝑗] \cdot (𝑖 - 𝑗) - 𝑖 - 1 \sum 𝑗 = 0 𝑓 [𝑗] \cdot (𝑖 - 1 - 𝑗) (交换枚举顺序) = 𝑖 \sum 𝑗 = 0 𝑓 [𝑖] 𝑔 [𝑖] = 𝑖 \sum 𝑗 = 2 𝑓 [𝑖 - 𝑗] \cdot 𝑗 \cdot (𝑗 - 1) = 𝑖 \sum 𝑗 = 0 𝑓 [𝑖 - 𝑗] \cdot 𝑗 \cdot (𝑗 - 1) (𝑓 [𝑖 - 1] \cdot 1 \cdot 0 = 0) Δ 𝑔 [𝑖] = 𝑖 \sum 𝑗 = 0 𝑓 [𝑖 - 𝑗] \cdot 𝑗 \cdot (𝑗 - 1) - 𝑖 - 1 \sum 𝑗 = 0 𝑓 [𝑖 - 𝑗 - 1] \cdot (𝑗 - 1) \cdot (𝑗 - 2) = 𝑖 \sum 𝑗 = 0 𝑓 [𝑗] \cdot (𝑖 - 𝑗) \cdot (𝑖 - 𝑗 + 1) - 𝑖 - 1 \sum 𝑗 = 0 𝑓 [𝑗] \cdot (𝑖 - 𝑗) \cdot (𝑖 - 𝑗 - 1) = 𝑖 \sum 𝑗 = 0 𝑓 [𝑗] \cdot (𝑖 - 𝑗) \cdot 2 (𝑖 - 𝑖 = 0) Δ 2 𝑔 [𝑖] = 𝑖 \sum 𝑗 = 0 𝑓 [𝑗] \cdot (𝑖 - 𝑗) \cdot 2 - 𝑖 - 1 \sum 𝑗 = 0 𝑓 [𝑗] \cdot (𝑖 - 𝑗 - 1) \cdot 2 = 𝑖 \sum 𝑗 = 0 2 𝑓 [𝑗] (𝑖 - 𝑖 = 0) ∴ Δ 3 = 2 𝑓 [𝑖]

我们维护 $𝑓 [𝑖]$ 的前缀和，以及 $𝑓 [𝑖 - 𝑗] \cdot 𝑗$ 的前缀和，每次将 $𝑓 [𝑖]$ 累加进 $𝑓 [𝑖]$ 的前缀和，将 $𝑓 [𝑖]$ 的前缀和累加进 $𝑓 [𝑖 - 𝑗] \cdot 𝑗$ 的前缀和， $𝑔 [𝑖]$ 同理。

行列式解法：

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define digit 100000000
6
using namespace std;
7
struct bigint
8
{
9
  mutable int a[205];
10
  inline bigint()
11
  {
12
    memset(a,0,sizeof(a));
13
    a[0]=1;a[1]=0;return;
14
  }
15
  inline bigint(int b)
16
  {
17
    memset(a,0,sizeof(a));
18
    a[0]=1;a[1]=b;return;
19
  }
20
  inline int& operator[](size_t pos)const{return a[pos];}
21
  inline bigint operator+(int b)const
22
  {
23
    int i;bigint c=*this;
24
    c[1]+=b;
25
    for(i=1;i<=c[0];++i)
26
    {
27
      if(c[i]>=digit)
28
      {
29
        ++c[i+1];c[i]-=digit;
30
      }
31
    }
32
    if(c[c[0]+1])++c[0];
33
    return c;
34
  }
35
  inline bigint operator-(const bigint& b)const
36
  {
37
    int i;bigint c;c[0]=a[0];
38
    for(i=1;i<=c[0];++i)c[i]=a[i]-b[i];
39
    for(i=1;i<=c[0];++i)
40
    {
41
      if(c[i]<0)
42
      {
43
        c[i]+=digit;--c[i+1];
44
      }
45
    }
46
    while(!c[c[0]]&&c[0]>1)--c[0];
47
    return c;
48
  }
49
  inline bigint operator*(int b)const
50
  {
51
    int i;bigint c;c[0]=a[0];
52
    for(i=1;i<=c[0];++i)c[i]=a[i]*b;
53
    for(i=1;i<=c[0]||c[i];++i)
54
    {
55
      if(c[i]>=digit)
56
      {
57
        c[i+1]+=c[i]/digit;c[i]%=digit;
58
      }
59
    }
60
    c[0]=i-1;
61
    return c;
62
  }
63
  friend ostream& operator<<(ostream& os,const bigint& a)
64
  {
65
    printf("%d",a[a[0]]);
66
    for(int i=a[0]-1;i>=1;--i)printf("%08d",a[i]);
67
    return os;
68
  }
69
}f[3005];
70
int main(void)
71
{
72
  int i,n;
73
  scanf("%d",&n);
74
  f[1]=1;f[2]=5;
75
  for(i=3;i<=n;++i)f[i]=f[i-1]*3-f[i-2]+2;
76
  cout<<f[n]<<endl;
77
  return 0;
78
}

DP 解法：

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define digit 1000000000
6
using namespace std;
7
struct bigint
8
{
9
  mutable int a[205];
10
  inline bigint()
11
  {
12
    memset(a,0,sizeof(a));
13
    a[0]=1;a[1]=0;return;
14
  }
15
  inline bigint(int b)
16
  {
17
    memset(a,0,sizeof(a));
18
    a[0]=1;a[1]=b;return;
19
  }
20
  inline int& operator[](size_t pos)const{return a[pos];}
21
  inline bigint& operator+=(const bigint& b)
22
  {
23
    int i;a[0]=max(a[0],b[0]);
24
    for(i=1;i<=a[0];++i)a[i]+=b[i];
25
    for(i=1;i<=a[0];++i)
26
    {
27
      if(a[i]>=digit)
28
      {
29
        ++a[i+1];a[i]-=digit;
30
      }
31
    }
32
    if(a[a[0]+1])++a[0];
33
    return *this;
34
  }
35
  friend ostream& operator<<(ostream& os,const bigint& a)
36
  {
37
    printf("%d",a[a[0]]);
38
    for(int i=a[0]-1;i>=1;--i)printf("%09d",a[i]);
39
    return os;
40
  }
41
}F=1,F1=1,F2=1,G=0,G1=0,G2=0;
42
int main(void)
43
{
44
  int i,n;
45
  scanf("%d",&n);
46
  for(i=1;i<=n;++i)
47
  {
48
    if(i)G2+=F,G2+=F;
49
    if(i<n)G1+=G2,G+=G1;
50
    F=F1;F2+=F;F1+=F2;
51
  }
52
  cout<<(F+=G)<<endl;
53
  return 0;
54
}

完结撒花！★,°:.☆(￣▽￣)/$:.°★