[FJOI2007] 轮状病毒

2018-08-12

lolifamily

题解

矩阵树 DP 差分

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

题解备份

Problem

Description

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

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

如下图所示

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

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

Input

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

Output

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

Sample Input

1
3

Sample Output

1
16

法一: 行列式

转载自 vfleaking，

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

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

首先行列式有很多性质：

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

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

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

| \begin{matrix} 3 & - 1 & 0 & 0 & \dots & 0 & 0 & 0 & - 1 \\ - 1 & 3 & - 1 & 0 & \dots & 0 & 0 & 0 & 0 \\ 0 & - 1 & 3 & - 1 & \dots & 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & 3 & \dots & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & \dots & 0 & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & \dots & 3 & - 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & \dots & - 1 & 3 & - 1 & 0 \\ 0 & 0 & 0 & 0 & \dots & 0 & - 1 & 3 & - 1 \\ - 1 & 0 & 0 & 0 & \dots & 0 & 0 & - 1 & 3 \end{matrix} |

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

| \begin{matrix} - 1 & 3 & - 1 & 0 & \dots & 0 & 0 & 0 & 0 \\ 0 & - 1 & 3 & - 1 & \dots & 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & 3 & \dots & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & \dots & 0 & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & \dots & 3 & - 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & \dots & - 1 & 3 & - 1 & 0 \\ 0 & 0 & 0 & 0 & \dots & 0 & - 1 & 3 & - 1 \\ - 1 & 0 & 0 & 0 & \dots & 0 & 0 & - 1 & 3 \\ 3 & - 1 & 0 & 0 & \dots & 0 & 0 & 0 & - 1 \end{matrix} |

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

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

\begin{matrix} 倒数第二行： & - 1 & 0 & 0 & 0 & \dots & 0 & 0 & - 1 & 3 \\ 用第一行的： & - 1 & 3 & - 1 & 0 & \dots & 0 & 0 & 0 & 0 \\ 乘以 - 1 来消： & 0 & - 3 & 1 & 0 & \dots & 0 & 0 & - 1 & 3 \\ 再用第二行： & 0 & - 1 & 3 & - 1 & \dots & 0 & 0 & 0 & 0 \\ 乘以 - 3 来消： & 0 & 0 & - 8 & 3 & \dots & 0 & 0 & - 1 & 3 \end{matrix}

这样就有了初步感觉了～

现在把这个过程一般化：

\begin{matrix} 第 k 个和第 k + 1 个： & 0 & 0 & \dots & F (k) & G (k) & 0 & 0 & \dots & - 1 & 3 \\ 总能找到上面的某一行 & 0 & 0 & \dots & - 1 & 3 & - 1 & 0 & \dots & 0 & 0 \\ 乘以 F (k) 来消： & 0 & 0 & \dots & 0 & F (k + 1) & G (k + 1) & 0 & \dots & - 1 & 3 \end{matrix}

于是得到：

{\begin{cases} F (k + 1) = G (k) + 3 F (k) \\ G (k + 1) = - F (k) \end{cases}

整合一下： $F (k + 1) = 3 F (k) - F (k - 1)$

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

\begin{matrix} 倒数第二行： & 0 & 0 & 0 & 0 & \dots & F (n - 3) & G (n - 3) & - 1 & 3 \\ 用倒数第四行： & 0 & 0 & 0 & 0 & \dots & - 1 & 3 & - 1 & 0 \\ 乘以 F (n - 3) 来消： & 0 & 0 & 0 & 0 & \dots & 0 & F (n - 2) & G (n - 2) - 1 & 3 \\ 用倒数第三行： & 0 & 0 & 0 & 0 & \dots & 0 & - 1 & 3 & - 1 \\ 乘以 F (n - 2) 来消： & 0 & 0 & 0 & 0 & \dots & 0 & 0 & F (n - 1) - 1 & G (n - 1) + 3 \end{matrix}

好现在搞定了倒数第二行，来看看成果： $(f = F (n - 1) - 1, g = G (n - 1) + 3)$

| \begin{matrix} - 1 & 3 & - 1 & 0 & \dots & 0 & 0 & 0 & 0 \\ 0 & - 1 & 3 & - 1 & \dots & 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & 3 & \dots & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & \dots & 0 & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & \dots & 3 & - 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & \dots & - 1 & 3 & - 1 & 0 \\ 0 & 0 & 0 & 0 & \dots & 0 & - 1 & 3 & - 1 \\ 0 & 0 & 0 & 0 & \dots & 0 & 0 & f & g \\ 3 & - 1 & 0 & 0 & \dots & 0 & 0 & 0 & - 1 \end{matrix} |

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

再设函数 $H (k)$ 和 $I (k)$ ，意义与 $F (k)$ 、 $G (k)$ 类似，得：

{\begin{cases} H (k + 1) = I (k) + 3 H (k) \\ I (k + 1) = - H (k) \end{cases}

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

\begin{matrix} 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & H (n - 1) & I (n - 1) - 1 \end{matrix}

再来看成果： $(h = H (n - 1), i = I (n - 1) - 1)$

| \begin{matrix} - 1 & 3 & - 1 & 0 & \dots & 0 & 0 & 0 & 0 \\ 0 & - 1 & 3 & - 1 & \dots & 0 & 0 & 0 & 0 \\ 0 & 0 & - 1 & 3 & \dots & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - 1 & \dots & 0 & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & \dots & 3 & - 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & \dots & - 1 & 3 & - 1 & 0 \\ 0 & 0 & 0 & 0 & \dots & 0 & - 1 & 3 & - 1 \\ 0 & 0 & 0 & 0 & \dots & 0 & 0 & f & g \\ 0 & 0 & 0 & 0 & \dots & 0 & 0 & h & i \end{matrix} |

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

\begin{matrix} 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 & i - g \cdot (\frac{h}{f}) \end{matrix}

现在这个行列式已经是三角行列式了，它的值就是对角线元素之积。于是： $B = (- 1) \times (- 1) \times (- 1) \times \dots \times f (i - g \cdot \frac{h}{f})$ 一共有 $n - 2$ 个 $- 1$ 。

如前文所述： $A = (- 1)^{n - 1} B$

又因为： $B = (- 1)^{n - 2} (f \cdot i - g \cdot h)$

于是有： $A = (- 1)^{2 n - 3} (f \cdot i - g \cdot h) = - f \cdot i + g \cdot h$

带入 $f$ 、 $g$ 、 $h$ 、 $i$ 的值得： $A = - (F (n - 1) - 1) (I (n - 1) - 1) + (G (n - 1) + 3) H (n - 1)$

带入 $H$ 、 $I$ 的值： $A = - (F (n - 1) - 1) (- H (n - 2) - 1) + (- F (n - 2) + 3) H (n - 1)$

然后再展开…… 回忆下 $F$ 、 $H$ 的递推式

\begin{aligned} A & = F (n - 1) H (n - 2) + F (n - 1) - H (n - 2) - 1 - F (n - 2) H (n - 1) + 3 H (n - 1) \\ = H (n) + F (n - 1) + F (n - 1) H (n - 2) - F (n - 2) H (n - 1) - 1 \\ = H (n) + F (n - 1) + | \begin{matrix} F (n - 1) & H (n - 1) \\ F (n - 2) & H (n - 2) \end{matrix} | - 1 \end{aligned}

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

FH 定理

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

| \begin{matrix} F (k - 1) & H (k - 1) \\ F (k - 2) & H (k - 2) \end{matrix} | = | \begin{matrix} F (2) & H (2) \\ F (1) & H (1) \end{matrix} |

证明：对于行列式：

| \begin{matrix} F (k - 1) & H (k - 1) \\ F (k - 2) & H (k - 2) \end{matrix} |

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

- | \begin{matrix} F (k - 1) & H (k - 1) \\ - F (k - 2) & - H (k - 2) \end{matrix} |

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

- | \begin{matrix} F (k - 1) & H (k - 1) \\ 3 F (k - 1) - F (k - 2) & 3 H (k - 1) - H (k - 2) \end{matrix} |

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

- | \begin{matrix} F (k - 1) & H (k - 1) \\ F (k) & H (k) \end{matrix} |

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

| \begin{matrix} F (k) & H (k) \\ F (k - 1) & H (k - 1) \end{matrix} |

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

那么立即推出：

| \begin{matrix} F (k - 1) & H (k - 1) \\ F (k - 2) & H (k - 2) \end{matrix} | = | \begin{matrix} F (2) & H (2) \\ F (1) & H (1) \end{matrix} |

FH 定理得证。

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

| \begin{matrix} F (n - 1) & H (n - 1) \\ F (n - 2) & H (n - 2) \end{matrix} | = - 1

于是就爽了嘛！

\begin{aligned} ∴ A & = H (n) + F (n - 1) + (- 1) - 1 \\ = H (n) + F (n - 1) - 2 \end{aligned}

进一步我们发现…… 设 $R (n) = H (n) + F (n - 1) - 2$

那么立即有：

\begin{aligned} R (n) & = 3 H (n - 1) - H (n - 2) + 3 F (n - 2) - F (n - 3) - 2 \\ = 3 (R (n - 1) + 2) - (R (n - 2) + 2) - 2 \\ = 3 R (n - 1) - R (n - 2) + 2 \end{aligned}

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

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

法二：DP

转载自 boshi

如果用 f[x] 表示加入了 $x$ 个周围的点后的方案数，我们首先想到的递推式是： $f [i] = \sum_{j = 1}^{i} f [i - j] \cdot j$

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

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

我们再设： $g [i] = \sum_{j = 2}^{i} f [i - j] \cdot j \cdot (j - 1)$

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

这样的 $f [n] + g [n]$ 就是我们要求的轮状病毒的数量。

下面我们思考如何快速求出 $f$ 和 $g$ 。

多阶差分

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

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

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

\begin{aligned} Δ f [i] & = \sum_{j = 1}^{i} f [i - j] \cdot j - \sum_{j = 1}^{i - 1} f [i - 1 - j] \cdot j \\ = \sum_{j = 0}^{i} f [i - j] \cdot j - \sum_{j = 0}^{i - 1} f [i - 1 - j] \cdot j (f [i] \cdot 0 = f [i - 1] \cdot 0 = 0) \\ = \sum_{j = 0}^{i} f [j] \cdot (i - j) - \sum_{j = 0}^{i - 1} f [j] \cdot (i - 1 - j) (交换枚举顺序) \\ = \sum_{j = 0}^{i} f [i] \\ g [i] & = \sum_{j = 2}^{i} f [i - j] \cdot j \cdot (j - 1) \\ = \sum_{j = 0}^{i} f [i - j] \cdot j \cdot (j - 1) (f [i - 1] \cdot 1 \cdot 0 = 0) \\ Δ g [i] & = \sum_{j = 0}^{i} f [i - j] \cdot j \cdot (j - 1) - \sum_{j = 0}^{i - 1} f [i - j - 1] \cdot (j - 1) \cdot (j - 2) \\ = \sum_{j = 0}^{i} f [j] \cdot (i - j) \cdot (i - j + 1) - \sum_{j = 0}^{i - 1} f [j] \cdot (i - j) \cdot (i - j - 1) \\ = \sum_{j = 0}^{i} f [j] \cdot (i - j) \cdot 2 (i - i = 0) \\ Δ^{2} g [i] & = \sum_{j = 0}^{i} f [j] \cdot (i - j) \cdot 2 - \sum_{j = 0}^{i - 1} f [j] \cdot (i - j - 1) \cdot 2 \\ = \sum_{j = 0}^{i} 2 f [j] (i - i = 0) \\ ∴ Δ^{3} & = 2 f [i] \end{aligned}

我们维护 $f [i]$ 的前缀和，以及 $f [i - j] \cdot j$ 的前缀和，每次将 $f [i]$ 累加进 $f [i]$ 的前缀和，将 $f [i]$ 的前缀和累加进 $f [i - j] \cdot j$ 的前缀和， $g [i]$ 同理。

行列式解法：

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
}

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