「Luogu P2144」[FJOI2007]轮状病毒

发表于 |
字数统计: 697 | 阅读时长 ≈ 3

有$n+1$个点组成一个无向图，其中$n$个点组成一个环，剩下一个点向这$n$个点各连一条边，求这个图不同的生成树个数。

Data Range：$n\leq 100$

链接

Luogu P2144
BZOJ 1002
CodeVS 2886

题解

既然这个题要你生成树数量，那么就可以用$\texttt{Matrix-Tree}$定理乱搞了。

设$F_i$表示$n=i$时的答案，那么有：

$F_1=1,F_2=5,F_3=16,F_4=45\cdots$

好像看不出来啊，然而你可以打一个$O(n^3)$的高斯消元求行列式，所以又可以算出一下数据：

$F_5=121,F_6=320$

那么可以看到奇数项都是平方数，于是想把偶数项拆成有关平方数的式子。

那么$F_1=1^2,F_2=3^2-4,F_3=4^2,F_4=7^2-4,F_5=11^2,F_6=18^2-4$

于是考虑怎么推出这些平方项的。把它们提出来，会是这样：

$1,3,4,7,11,18\cdots$

所以这一项会是前两项的和，于是就可以开开心心写了。

但是$n\leq 100$，所以要用到高精qwq。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MAXN=151;
struct BigInt{
    ll digit;
    ll num[MAXN];
    BigInt()
    {
        memset(num,0,sizeof(num));
    }
    inline void operator =(ll x)
    {
        while(x)
        {
            num[digit++]=x%100000000,x/=100000000;
        } 
    }
    inline void op()
    {
        printf("%lld",num[digit-1]);
        for(register int i=digit-2;i>=0;i--)
        {
            if(!num[i])
            {
                printf("00000000");
                continue;
            }
            ll rest=7-(ll)(log10(num[i]));
            for(register int j=rest;j;j--)
            {
                putchar('0');
            }
            printf("%lld",num[i]);
        }
    }
}; 
BigInt res;
BigInt sqr[151];
ll num;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline BigInt operator +(BigInt x,BigInt y)
{
    BigInt res;
    ll carry=0;
    res.digit=max(x.digit,y.digit)+1;
    for(register int i=0;i<=res.digit;i++)
    {
        res.num[i]=x.num[i]+y.num[i]+carry;
        carry=res.num[i]/100000000,res.num[i]%=100000000;
    }
    if(!res.num[res.digit-1])
    {
        res.digit--;
    }
    return res;
}
inline BigInt operator *(BigInt x,ll y)
{
    BigInt res;
    ll carry=0;
    res.digit=x.digit+1;
    for(register int i=0;i<=res.digit;i++)
    {
        res.num[i]=x.num[i]*y+carry;
        carry=res.num[i]/100000000,res.num[i]%=100000000;
    }
    if(!res.num[res.digit-1])
    {
        res.digit--;
    }
    return res;
}
inline BigInt operator *(BigInt x,BigInt y)
{
    BigInt res;
    res.digit=x.digit+y.digit;
    for(register int i=0;i<res.digit;i++)
    {
        for(register int j=0,k=i;k>=0;j++,k--)
        {
            res.num[i]+=x.num[j]*y.num[k];
            res.num[i+1]+=res.num[i]/100000000,res.num[i]%=100000000;
        }
    }
    if(!res.num[res.digit-1])
    {
        res.digit--;
    }
    return res;
}
inline void setup(ll num)
{
    sqr[1]=1,sqr[2]=3;
    for(register int i=3;i<=num;i++)
    {
        sqr[i]=sqr[i-1]+sqr[i-2];
    }
}
int main()
{
    num=read();
    setup(num);
    res=sqr[num]*sqr[num],res.num[0]-=(num&1)?0:4;
    res.op();
}