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

WJiannan · 2018-01-23 07:54:26 · 题解

一开始我看到这个就像直接上一个 \mathrm{MatrixTree} + 高精度，据说是近似 O(n^4)。

接着我用分数来优化高精度（显然不行）；

接着我打表找规律（并没有发现什么）。

于是只能推式子了。

考虑把先不管中心点，然后把外围的 n 个点拆环成链，暂时强制第一个点不能和最后一个点连边。

于是方案数就类似一个整数拆分，将外围的点分成若干个联通块，

即设 f_i 为当前已经分配了前 i 个点的方案数，f_i = \sum_{j=1}^{i} f_{i-j} \times j（因为每加入一个联通块，中心点都可以向其中的任意一个点连边）。

但是我们还需要考虑上第一个点与最后一个点连边的情况，发现，如果分配第一个联通块大小为 x，那么我们可以把这张图逆时针旋转，则总共有 x 种不同的方案。

于是答案的计算方式就等于 f_i=\sum_{j=1}^{i-1} f_{i-j} \times j +f_0 \times i \times i

再套个高精度，复杂为 O(n^3)。

本文认为此题高精度近似 O(n)。

#include <cstdio>
#include <cstring>
#define R register
#define Max(_A, _B) (_A > _B ? _A : _B)
const int Mod = 1e8;
struct BigNum
{
    int a[110], len;
    BigNum(){ len = 1; }
    friend BigNum operator + (R BigNum A, R BigNum B)
    {
        A.len = Max(A.len, B.len);
        for(R int i = 0; i < A.len; i++) 
        {
            R int tmp = A.a[i] + B.a[i];
            A.a[i] = tmp % Mod;
            A.a[i + 1] += tmp / Mod;
        }
        while(A.a[A.len]) A.len++;
        return A;
    }
    BigNum operator * (R int K)
    {
        R BigNum T; 
        memset(T.a, 0, sizeof(T.a)); T.len = len;
        for(R int i = 0; i < len; i++)
        {
            R long long tmp = 1ll * a[i] * K + T.a[i];
            T.a[i + 1] += tmp / Mod;
            T.a[i] = tmp % Mod;
        }
        while(T.a[T.len]) T.len++;
        return T;
    }
    void Print()
    {
        printf("%d", a[len - 1]);
        for(R int i = len - 2; i >= 0; i--) printf("%.8d", a[i]);
        puts("");
    }
} f[110];
int n;
int main()
{
    scanf("%d", &n);
    f[0].a[0] = 1;
    for(R int i = 0; i < n; i++)
        for(R int j = 1; i + j <= n; j++)
            if(i == 0) f[i + j] = f[i + j] + f[i] * (j * j);
            else f[i + j] = f[i + j] + f[i] * j;
    f[n].Print();
    return 0;
}