不妨设 $g(n)$ 表示 $n$ 个点的 无向图 个数,$f(i)$ 表示 $n$ 个点的 无向连通图 个数,那么有:
$$g(n) = \sum_{i \le n} \dbinom{n - 1}{i - 1} f(i) g(n - i)$$
解释一下这个柿子的意义:与 $1$ 相连的连通块大小为 $i$,需要先选出 $i - 1$ 个点与 $1$ 相连。剩下 $n - i$ 个点没有连通性限制。不难发现这样没有重复或遗漏。
将 $f(n)$ 分离并移项,可以得到:
$$f(n) = g(n) - \sum_{i < n}\dbinom{n - 1}{i - 1}f(i)g(n - i)$$
这个做法是 $O(n ^ 2)$ 的。
接下来你发现,若设出 $f, g$ 的 $\mathbf{EGF}$ 分别为 $\mathcal{F, G}$,上述式子可以直接分治 NTT。这样可以做到 $O(n \ \mathrm{polylog}(n))$ 的复杂度。
由于这道题没有取模,因此需要高精度。人生苦短,我用 python
。
N = 55
c = [[0 for o in range(N)] for o in range(N)]
f = [0 for o in range(N)]
g = [0 for o in range(N)]
def h(n) :
ans = 0
for i in range(0, n) :
ans = ans + c[n - 1][i - 1] * f[i] * g[n - i]
return ans
for i in range(0, N) :
for j in range(0, i + 1) :
if j == 0 :
c[i][j] = 1
else :
c[i][j] = c[i - 1][j] + c[i - 1][j - 1]
f[0] = 1
for i in range(0, N) :
g[i] = 2 ** c[i][2]
for i in range(0, N) :
f[i] = g[i] - h(i)
n = int(input())
while n > 0 :
print(f[n])
n = int(input())
一种更简单的办法是:
ans = [1,1,1,4,38,728,26704,1866256,251548592,66296291072,34496488594816,35641657548953344,73354596206766622208,
301272202649664088951808,2471648811030443735290891264,40527680937730480234609755344896,1328578958335783201008338986845427712,
87089689052447182841791388989051400978432,11416413520434522308788674285713247919244640256,
2992938411601818037370034280152893935458466172698624,1569215570739406346256547210377768575765884983264804405248,
1645471602537064877722485517800176164374001516327306287561310208,
3450836972295011606260171491426093685143754611532806996347023345844224,
14473931784581530777452916362195345689326195578125463551466449404195748970496,
121416458387840348322477378286414146687038407628418077332783529218671227143860518912,
2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472,
68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896,
4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344,
615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208,
165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128,
88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584,
95268202520385449790227094691687836722278710954949736428196756305746453532341035148366531266372862653739009088659598082113309304400438624256,
204586909944926298207861553173799965921067126517774603507480126827588404754232387878919170016875623577048105576068684204467114231315623298308706926592,
878694093745349914731889727208157807680003171098920968952145189548012830636076748530741378813207711246134152874638123892704663922045456803250047261786444398592,
7547924819767483287594694542205326068855891655862820018679189530528628155893698967796630219069788201405972928386025644172169109953194652176102437455457970998547197198336,129672361263353660216004848405397154497075914498088480263529787446798464815868889966259599220355751574955667311875199310825316757090836792227021420332597263591744872066219249762304,
4455508410978470003213152055317479855991723332650114280703483486331017198541367912550307040027205813596014620050254013798901452927850711294962075802234712748298505435020109941966616435621888,306180206751230090930313674296749763317292930219833760674864513181351793147422958983304199997791891477494238067606067864147691875149221011750587805454462256284237767964756224079011437145490032917741568,
42081087200752140195116730773102052524009718837902621183664949269856744858385083976643391056195246283737633254986683196506525739229100562028667655727478159896469450443625002559600024194689577683162985133342982144,11567161173227696466220457283329529101751379197153495724502457893891478829937149071434453800538222228465001645119757350054456753856800058471020811256328606811309950183460999195585736337722940242137574318489684508433109221376,
6359114105601017351375465630036218352726964545083913061809864302427743340641476112983635151514041188995967358659226381513838435962182371853731281705837980150384424607870600516842502175922529566100381861494213531965265765000213275082752,6991919901710702396948942815573257427744311018004588489866790612959056357721564695830748688904669995738081555372234543689358610668809196548322563461899302515136978058611651369187392760821440875968116963440793130046454847480988052748303630065467392,
15375394465098365435098131065240195173750887603455691084898736566282027607324662718653380384318359771738669872579070523864682029424324656980343742654131923883848453279046887366030428581980234722002609397042921130626427482776226373410811403774539364168814821376,67621699984704009571087635348261788647460730411971168452281282746962798999895717916292043207408657855232972628889146834646084600650980317820241001687549180689983916950502853108787655643356237905731863505593837387547463783553663104052737827256888296815897621036524900450304,
594806763388137870319868932592503661181879874998563369872608575294390559331829154567126246824792929668641338543467328561106071308881273503814138669414317911219402066314092130747535752627679688399993515689603622744525243838714230998285264232171322066511990049433899384262102238508351488,10463951242026625501784363274596214619943325701401522513836100192928357652762255136769619473700702276949844553770347735730521468871772581157963359677917896206658361141741863952608795675733168160935829452838892433190712974942475048711118429563334205007874224852816312589287727030417085994911901155328,
368167554019320956145827247050509963076959450983143444578072117098399777382502455552633802915095691807005512740224345254318634273382517137823997743877511866703540358482988273801636313118482363728678083259725882776454656507629131210255280738244476783496709369751571318821222548711309212127848471930415455355797504,25907488423318455274080473672019976083009208996271003791416218114322853582878049179546761491016196610119349803222490393175612695149120594742502991139032865749979736985340247224801444473477196529096332604358326020598992443433363048888842556850935198901353471923472154386768107635993449205071378228596636214817388982756553261056,
3646154850293767810262810894999553363628589110640769385457986485984919161321600546344826908488589572223649058216506920510786720770519258252897810249930214560211056122090333850686659187132094273815095247787669459869137017783625755540375408272361426098383313551230976557640520636974573279383371834513917048967432546435999569365350430111956992,1026301351570055077911628972867042177680735585635225345203536190737910863123857244548313982876228994987864700400759811456244128889754306386459557887432298148719591734971030611474690885904247396313959818854940592795291449937598794070517570167551607950979266237997797283563645242105244737520881371410960067902176629829514256225641238164014573644333472284672,
577756298062641319815321284633539861082132919998722885657507672188606317696301924134068233518707877841769252356274834883678320922291785288952259324960085933885572481476441044041666245632947630667669900623389069655523344952222114179660086674251300523449279256078271770682664276058349275922600493471476178420154378012048571333436567365397136152469165480980158369042006016]
n = int(input())
while n :
print(ans[n])
n = int(input())