结合多阶差分的 DP

递推方程

如果用 $f[x]$表示加入了 x 个周围的点后的方案数，我们首先想到的递推式是：
$$
f[i]=\sum_{j=1}^{i}f[i-j]\cdot j
$$
意思是，最后加入的 j 个点每个都可能与中心点连边，将所有方案数累加即可。

但是，我们遇到一个问题：第一个点永远不会与第 n 个点连边，因此方案数统计并不准确。

所以我们需要对上面的 f[x] 作一些修正。
$$
g[i]=\sum_{j=2}^{i}f[i-j]\cdot j\cdot(j-1)
$$
这样的 $g[i]+f[i]$就是我们要求的轮状病毒的数量。

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

下面我们思考如何快速求出 f 和 g。显然由于涉及高精度加法，我们需要 $O(n^3)$的复杂度求解这个鬼东西。为了追求速度，我们需要更快一些。

多阶差分

首先分析 $f[i]$。如果我们可以求出所有 $f[i-j]*j$的前缀和，这个问题就变得非常方便了。问题是对于不同的 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[j]\cdot(i-j) \ – \ \sum_{j=0}^{i-1}f[j]\cdot(i-1-j)
$$
$$
=\sum_{j=0}^{i}f[i]
$$
太棒了，前缀和的变化量就是单纯的 $f[i]$的前缀和！

所以，我们维护 $f[i]$的前缀和，以及 $f[i-j]\cdot j$的前缀和，每次将 $f[i]$累加进 $f[i]$的前缀和，将 $f[i]$的前缀和累加进 $f[i-j]\cdot j$的前缀和。事就这样成了。

然而我们还剩下 $g[i]$没办法处理。其实处理办法是一样的。
$$
g[i]=\sum_{j=2}^{i}f[i-j]\cdot j\cdot(j-1)
$$
$$
g[i]=\sum_{j=0}^{i}f[j]\cdot (i-j)\cdot (i-j+1)
$$
$$
\Delta g[i]=\sum_{j=0}^{i}f[j]\cdot(i-j)\cdot 2
$$
$$
\Delta^2 g[i]=\sum_{j=0}^{i}f[j]\cdot2
$$
$$
\Delta^3 g[i]=2f[i]
$$
也就是说 $g$的三阶差分就是 $f$，那么我们每次把每阶差分往上累加就行了。

总结

所以，如果 $f[i]$递推式中遇到了含有 i 的简单多项式，我们就可以手动差分一下，分别维护每阶差分，依次向上累加即可。

这样我们就可以只用加法完成很多有趣的事情 (比如现在这道题)。这可是 Vjudge 上最短的 C++代码。

#include <stdio.h>
#define max(x,y) (x>y?x:y)
struct BI{
    char x[43],n;
    void operator+=(BI &a)
    {
        char mx=max(n,a.n),k=0;
        for(char i=1;i<=mx||k;i++)
        {
            if(i>n)x[i]=0;
            x[i]+=a.x[i]+k;
            k=x[i]/10,x[i]%=10;
            n=max(n,i);
        }
    }
    void operator=(char a){n=1,x[1]=a;}
    void out(){for(char i=n;i>=1;i--)printf("%d",x[i]);}
};
BI f,g,f1,f2,g1,g2;
int main()
{
    char n;
    scanf("%d",&n);
    f=1,f1=1,f2=1,g1=0,g2=0;
    for(char i=1;i<=n;i++)
    {
        if(i)g2+=f,g2+=f;
        if(i<n)g1+=g2;
        if(i<n)g+=g1;
        f=f1;
        f2+=f;
        f1+=f2;
    }
    g+=f;
    g.out();
    return 0;
}