题解 P2144 【[FJOI2007]轮状病毒】

· · 题解

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的简单多项式，我们就可以手动差分一下，分别维护每阶差分，依次向上累加即可。

这样我们就可以只用加法完成很多有趣的事情(比如现在这道题)。

#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;
}