结合多阶差分的 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;
}
分类: 文章

1 条评论

P`eipei · 2018年3月1日 2:07 下午

这么强!!!!!!,orz,%%%%%%%%%%

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注