We write down a random permutation\(a\), where random is well defined, i.e.\(n!\) individual permutations are chosen at random. We memorize\([l_i, r_i]\) largest\(i\) as the interval of the maximum value.
What we're asking for is\(\sum \limits _ {i = 1} ^ n \Big(r_i - l_i + 1 \Big)\) The expectation, denoted as\(\mathbb{E}\)。
A slight simplification yields\(\mathbb{E} = n + \sum \limits _ {i = 1} ^ n \mathrm{E}\Big(r_i - l_i\Big)\), note that here you can't just put\(\mathrm{E}\Big(r_i - l_i\Big)\) Take it apart, or you'll eliminate the pile and get the answer\(\mathbb{E} = n\), which is patently absurd, the problem is that the\(r_i, l_i\) are not independent, so the linear relationship of mathematical expectation cannot be directly utilized.
think over\(\mathrm{E}(r_i - l_i)\) Solve using the expectation defining equation. First enumerate the\(v\) indicate\(a_i\) values. Then enumerate the\(r_i\)Then the requirement for the presence of\(r_i - i\) Number less than\(v\)So.\(r_i \in \Big[i, \min\{n, i+v-1\}\Big]\)Select less than\(v\) The scheme for counting and arranging the numbers of\(\dbinom{n - 1}{r_i - i}(r_i - i)! = \dfrac{(n - 1)!}{(n - 1 - r_i + i)!}\). Then to the\(r_i + 1\) Categorize the discussion if\(r_i + 1 \leq n\)That position is better than\(v\) The larger the number, the program number is\(n - v\); conversely there is no need to restrict that this position must be more than\(v\) Great. For\(l_i\) Similar to enumeration. Note that at the end you have to multiply by a factorial for any random arrangement of the remaining numbers.
\[\mathbb{E} = n + \sum\limits_{i=1}^n \dfrac{\displaystyle \sum _ {v = 1} ^ n \sum _ {r_i = i} ^ {\min\{n, i+v-1\}} \sum _ {l_i = \max\{1, r_i - v + 1\}} ^ i \dfrac{(r_i - l_i)(v - 1)!}{(v - 1 - r_i + l_i)!} \dfrac{(n - v)!}{(n - v - c)!} \Big(n - r_i + l_i - 1 - c \Big)!}{n!}
\]
included among these\(c = [r_i \neq n] + [l_i \neq 1]\)The additional requirements of the\(c \leq n - v\)。
Okay, I'll admit, this equation is uglier than even I am. And OEIS only has integer series, can't find this. But there should be a relationship like this:\(\mathcal{O}(n \log_2 n) \leq \mathcal{O}(\mathbb{E}) \leq \mathcal{O}(n \sqrt{n})\). This growth rate must contain logarithms, so we conjectured that it was related to the harmonic series, and indeed, after our study below, it agrees with our conjecture.
The lovely yzh immediately knocked out a short Python code.\(\mathcal{O}(n! \cdot n)\) to verify.
Expand her cuteness code
import itertools
import fractions
def solve(n: int) -> :
total: int = 0
count: int = 0
for perm in (range(n)):
count += 1
l: list[int] = [0] * n
r: list[int] = [n - 1] * n
stack: list[int] = [-1]
for i in range(n):
while len(stack) > 1 and perm[stack[-1]] < perm[i]:
r[()] = i - 1
l[i] = stack[-1] + 1
(i)
total += sum(r[i] - l[i] + 1 for i in range(n))
return (total, count)
def main() -> None:
while True:
n = int(input('Input n: '))
print(f'∑ r[i] - l[i] + 1 = {solve(n)}')
if __name__ == '__main__':
main()
xym says, you're too slow for this ...... So xym knocks out the C++ code.
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 20;
using uint = unsigned;
using lint = long long;
lint gcd(lint a, lint b) {
return b ? gcd(b, a % b) : a;
}
int n, a[N];
lint son, mon;
void solve() {
static int stack[N], top;
static int l[N], r[N];
top = 0, a[n] = 0x3f3f3f3f, stack[0] = -1;
for (int i = 0; i <= n; ++i) {
while (top && a[stack[top]] < a[i]) r[stack[top--]] = i - 1;
l[i] = stack[top] + 1, stack[++top] = i;
}
++mon;
for (int i = 0; i < n; ++i) son += r[i] - l[i] + 1;
}
void dfs(int i, uint nvis) {
if (i == n) return solve();
for (uint st = nvis; st; st &= st - 1) {
int j = __builtin_ctz(st);
a[i] = j, dfs(i + 1, nvis ^ (1u << j));
}
}
signed main() {
while (true) {
printf("Input n: "), scanf("%d", &n);
son = mon = 0;
dfs(0, (1u << n) - 1);
lint g = gcd(son, mon);
son /= g, mon /= g;
if (mon > 1)
printf("∑ r[i] - l[i] + 1 = %lld/%lld\n", son, mon);
else
printf("∑ r[i] - l[i] + 1 = %lld\n", son);
}
return 0;
}
yzh is not convinced! She said Python yyds! So knock it off.\(\mathcal{O}(n ^ 4)\) The code. Say: You C++ still have to handwrite high precision and fraction classes, can you have the elegance of my Python?
Expand her cuteness code
from fractions import Fraction
def solve(n: int) -> Fraction:
frac: list[int] = [1] * (n + 1)
for i in range(2, n + 1):
frac[i] = frac[i - 1] * i
total: int = 0
for i in range(1, n + 1):
for v in range(1, n + 1):
for ri in range(i, min(n, i + v - 1) + 1):
for li in range(max(1, ri - v + 1), i + 1):
c = (ri != n) + (li != 1)
if c > n - v:
continue
# print(f'{i = }, {v = }, {li = }, {ri = }')
total += (ri - li + 1) * frac[v - 1] // frac[v - 1 - ri + li] * frac[n - v] // frac[n - v - c] * frac[n - ri + li - 1 - c]
return Fraction(total, frac[n])
def main() -> None:
while True:
n = int(input('Input n: '))
print(f'∑ r[i] - l[i] + 1 = {solve(n)}')
if __name__ == '__main__':
main()
xym said, I don't optimize for time complexity though, but it's not like this is OI and I run multiple processes!
from multiprocessing import Pool, cpu_count
from fractions import Fraction
from time import time
def calc(i: int, n: int, frac: list[int], g: list[list[int]]) -> int:
total: int = 0
for v in range(1, n + 1):
for ri in range(i, min(n, i + v - 1) + 1):
for li in range(max(1, ri - v + 1), i + 1):
c = (ri != n) + (li != 1)
if c > n - v or li == ri:
continue
if c == 0:
total += g[v - 1][ri - li] * frac[n - ri + li - 1 - c]
elif c == 1:
total += g[v - 1][ri - li] * frac[n - ri + li - 1 - c] * (n - v)
else:
total += g[v - 1][ri - li] * frac[n - ri + li - 1 - c] * (n - v) * (n - v - 1)
return total
def solve(n: int) -> Fraction:
frac: list[int] = [1] * (n + 1)
for i in range(2, n + 1):
frac[i] = frac[i - 1] * i
g: list[list[int]] = [[0] * (i + 1) for i in range(n + 1)]
for i in range(1, n + 1):
g[i][0] = 1
for j in range(1, i + 1):
g[i][j] = g[i][j - 1] * (i - j + 1)
for j in range(i + 1):
g[i][j] *= j
total: int = 0
with Pool(processes=cpu_count()) as pool:
results = (calc, [(i, n, frac, g) for i in range(1, n + 1)])
total = sum(results)
return n + Fraction(total, frac[n])
def main() -> None:
start_time = time()
with open('res', 'w') as f:
for n in range(100, 200):
res = solve(n)
print(f'\\frac{{{}}}{{{}}}', file=f, end=', ')
end_time = time()
print(f'time used {end_time - start_time:.2f}s.')
return
if __name__ == '__main__':
main()
yzh: Awesome! Let me try it! Whoa.\(n \in [100, 200)\) I can't believe it's only running on the junk quad-core computers in the server room.\(3837.22\) Seconds!
$n \in [1, 200)$
[
1 / 1,
3 / 1,
17 / 3,
53 / 6,
62 / 5,
163 / 10,
717 / 35,
3489 / 140,
3727 / 126,
43391 / 1260,
45596 / 1155,
619313 / 13860,
644063 / 12870,
667229 / 12012,
2756003 / 45045,
24124223 / 360360,
24784883 / 340340,
160941559 / 2042040,
164719333 / 1939938,
33664415 / 369512,
11451017 / 117572,
268428987 / 2586584,
819836496 / 7436429,
20845424563 / 178474296,
21181779967 / 171609900,
193553388003 / 1487285800,
196368607553 / 1434168450,
5773568883787 / 40156716600,
5849866645327 / 38818159380,
183636137408557 / 1164544781400,
743424203592403 / 4512611027925,
376019594141039 / 2187932619600,
34563855136549 / 193052878200,
34933413503389 / 187537081680,
35292859576609 / 182327718300,
1318781072333833 / 6563797858800,
1331390473483633 / 6391066336200,
1343680985668633 / 6227192840400,
1355668331886403 / 6071513019390,
56062051135874333 / 242860520775600,
56530424997370133 / 237078127423800,
350069394209013017 / 1422468764542800,
3880990797545677687 / 15291539218835100,
3910554440035425547 / 14951727236194320,
3939482781861975427 / 14626689687581400,
186486719509082752469 / 672827725628744400,
187790323227488444744 / 658810481344812225,
9264312833874690953831 / 31622903104550986800,
9325661265897519868223 / 30990445042459967064,
9385819188627000980759 / 30382789257313693200,
9444831913915244884859 / 29798504848519199100,
503645337436905456404827 / 1549522252122998353200,
506658297371589064313827 / 1520827395602202087400,
169872332647071722185529 / 497725329469811592240,
170841119449075462606139 / 488837377157850670950,
171793065920382856017989 / 480261282821748027600,
172728747385190744416589 / 471980915876545475400,
10245273901052056650249751 / 27374893120839637573200,
10298654942637693943517491 / 26918644902158976946980,
631421270244256248811257571 / 1615118694129538616818800,
634573356727960670950532971 / 1589068392611320252031400,
637675823589725629537832371 / 1563845084792092946443600,
854306944694613581431806703 / 2052546673789621992207225,
429158652559393575277521179 / 1010484516327198519240480,
431133690477669463292400299 / 995174144867695511373200,
9672108358327174050860236411 / 21893831187089301250210400,
9714930116384275184187853811 / 21571863081396811525942600,
29271407806369719881085398433 / 63777682153694921033221600,
29396229841441951369393274993 / 62866572408642136447032720,
2095870772307179804193060072583 / 4400660068604949551292290400,
6313466194824593491193022423849 / 13018619369622975755906359100,
462744694792051410390185246292277 / 937340594612854254425257855200,
464581375686900922104937440738277 / 924673829820788656392484100400,
466393736393349667871466709575061 / 912344845423178140973917645728,
468182412471876688174165574433133 / 900340307983399481224260834600,
469948014894025952091891072952933 / 888647576710887799649919784800,
42881011935863391720878719600703 / 79750423550977110224992801200,
3399961258583609398034292732641537 / 6220533036976214597549438493600,
3412169054668675219181983505685227 / 6142776374014011915080070512430,
30818043874625657849804266130219973 / 54602456657902328134045071221600,
30925251137088124616018671696886773 / 53936573040123031449483545962800,
2575587505783854397255815568833538559 / 4422798989290088578857650768949600,
2584275146655674214107143097129689559 / 4370146620369968476728393021700200,
2592861199427459916879068292831147599 / 4318733130718557082884529574386080,
2601348012207592895332643705599417919 / 4268515303617178512153314114218800,
2609737852631943901373772633341158319 / 4219451909322728184427413951986400,
28798362026490486912099741793464447409 / 45886539513884669005648126727852100,
2571084364772583152252865441795709936901 / 4038015477221850872497035152050984800,
2579025795211119458968776277594743540341 / 3993148638586052529469290317028196080,
2586880450225481034823446639866700101861 / 3949267884315876128046550862994919200,
2594650205519624225901451267108027062461 / 3906341059486355735350392701440626600,
2602336876636678022671011717262474747061 / 3864337392180050834970280951962770400,
2609942221504266420590900036157295093061 / 3823227419922816251619533282261038800,
2617467942846640806265140591144482611541 / 3782982920765733975286696089816185760,
2624915690471898345028986274071308227256 / 3743576848674424246377459672213933825,
255331845153870954498869763382309759404407 / 359383377472744727652236128532537647200,
256039610376852992584960391676256491709607 / 355716200151594271247621474159756650800,
256740263498363708573781464276874194203607 / 352123107220770086689564691592486381600,
257433946019588625644559906719311392375359 / 348601876148562385822669044676561517784,
1042808012853280604195170468741643454878011 / 1394407504594249543290676178706246071136,
1045555815877039860648125624740858704488779 / 1380736842784501998748610725973831893968,
107972538614420359552502907325681134436819741 / 140835157964019203872358294049330853184736,
108250146377714820483212844347605296214731961 / 139480973752826711527431771991164210365652,
542625615772709108572548906347653671147264089 / 690762917633046571373947823194337041810848,
543987591714079926812333388376404769654230761 / 684246286334621603719476617315145182925840,
58351048279823157327304482122528805986600043667 / 72530106351469889994264521435405389390139040,
58494093767349667388126503817581966615675040107 / 71858531292659983605428738829522006155045160,
6391305804869035641780956094964781592431914081063 / 7760721379607278229386303793588376664744877280,
6406615591590624545197109076084860480943274429879 / 7690169367065393881846428304555755058701742032,
583798917082675385566751412976344982590138528437 / 692808051086972421787966513923941897180337120,
585165975826338072220458025472569903655110443647 / 686622264916553025164859670049620987384084110,
66276872033452593485523520584821464593214130888641 / 76901693670653938818464283045557550587017420320,
66428651692013094680559963248727170285162191586641 / 76227117410385044618302315650421080845026039440,
66579117393336202551241307819619740592569329942753 / 75564272911164305099882295514330462750721465184,
66728291690721173463895385799557513661275495593849 / 74912856765378405917986758484034510485629038760,
66876196561770766726861667348359325387106096516529 / 74272575938323889628089435761948745438743320480,
67022853427818474068245945641007919096319886293409 / 73643147328677077004122576136847484884177699120,
67168283172543172497623834761950433037057548136209 / 73024297351125168794003899026453808540613180640,
67312506159811644705991992462527679308925259167973 / 72415761539865792387387199867900026802774737468,
1632424122469047386761123325746855460557163904315917 / 1737978276956779017297292796829600643266593699232,
1635857341852216105967423715616002458549190536131613 / 1723732553375166074532560888658866211764408504976,
1639262764701567043821988043225304121065115343178029 / 1709718467575367976365629499320176242563071850464,
1642640837480244182162387875703799630576631089979349 / 1695930415417502105588487325938561918026272883928,
205748999497638645790378840832481778615831375649748841 / 210295371511770261092972428416381677835257837607072,
206164583208007144163491143488637961455362956614543769 / 208626360626756211401758361524188172455612934134000,
26235267283934223117825216571799592336117454336514692663 / 26286921438971282636621553552047709729407229700884000,
105148900108363759174646655444969246549517943255881384777 / 104326219460917277964091790659689347988584942875383375,
52677563178067669920194813794648269723352340466829152701 / 51758744538749657284510655831163707529220436775384000,
52779886234578890396518807937329877975929337791838950301 / 51360600349990044536168266170923986702072587261727200,
6927467492220482063478831420728483327402580050831689834231 / 6676878045498705789701874602220118271269436344024536000,
6940669501083172686290287400055600379438953709057374712231 / 6626295636063109533719284643112390102547698189903138000,
6953772627040199737473506737357394053100382616004326030231 / 6576473864363386905646207314968687921325535045618152000,
6966778340279425838443627968241473921004496547251257450231 / 6527395701196495958589146066349518608479822097516524000,
6979688078444014463783948723794920746696823306510790131031 / 6479044621928373766303300539932114766935527119016401600,
6992503247585916908954063340304051179581423724121197572431 / 6431404587943606312139305683020849217178648243141281000,
959715855562603333837296429461753661740510463878495354574047 / 874671023960330458450945572890835493536296161067214216000,
961446183023046596265971126138559444999462701936258756610047 / 868332828134530962375214083232206250829511406276872084000,
133879810967940472895623170406148619573903431205866106991896533 / 119829930282565272807779543486044462614472574066208347592000,
134116903044285262756821419931474578974933494798839962079632133 / 118974002209118378002009689604001287881512055680021145109200,
134352319686954369334570077402393134714784146313270642217826933 / 118130214959408318583555720174185675910721190036900427768000,
134586084408106437908668522172596981017114517118907043768550933 / 117298312037158964227333496792677326080363998557767326164000,
134818220228431724530181356994920950830266566151017870015434933 / 116478044120815195246722773038882379744137676889531191016000,
135048749690754171270773829149893738873510171969861733830987433 / 115669168814420645279731642670556807662581165244465002189500,
135277694873166162479017160056420978899711280896931812835321133 / 114871450408803951174354183065932277954563364104848002174400,
135505077401715096327574614569476146217032300158755792784830733 / 114084659652579266577269565373699865091860875309609317228000,
135730918462659998141003086974399592888744759442531958167914733 / 113308573532493693335247323432382178934773386361924900104000,
135955238814315543087943813094438025175419682430397120301228733 / 112542975062679546758657814490271488536565458075695677806000,
20290530760976506386397432206345895840255819492261501149835851217 / 16656360309276572920281356544560180303411687795202960315288000,
20323510354388874000779589292304124997256574634096003011260121457 / 16545317907214729100812814167596445768055609876568273913186080,
3073797113566977178118861014574034211870391397101590368600320977927 / 2481797686082209365121922125139466865208341481485241086977912000,
3078711726090074184822161662992895919281100020693215747331770658927 / 2465470069726405356140856848000391425305655024370206606142531000,
3083594323679140203272558261848739831711607298290497921198837239927 / 2449355886264141268845818567948101285270977540550793491069704000,
3088445320726611392149168486934611071270098520042887479736345419927 / 2433450977911776715152014551273113614587399764313450676192628000,
3093265123631249556352727638336164915655120015059947023978868883127 / 2417751294183313639570388650942319333202964927124331639572030400,
3098054131002420350677261292779377586642041272511750988572636558727 / 2402252888451369321368014364718330106708074126309432077779902000,
37472430708899105455021190417983821674306668525971318352468729941703 / 28827034661416431856416172376619961280496889515713184933358824000,
37529537429462544335850673088578011850767399705834724851735447105703 / 28644585074951770895299614323603379247076023126373228066691996000,
37586286135743109164982870437709678922860663525236030303565685965703 / 28464430451838866675832321151756817113446614175892893298976952000,
37642681288575814919584363223991597116766679629572018098414284051853 / 28286527761514873759108369144558337006487572837293562715858346050,
37698727265941797806100857446085473573319906559603674287894773569803 / 28110835042499253425200863746144931186571500956316584065449288000,
37754428365007490771221162861286168159189594533720820111876311973803 / 27937311369397406181835426315613172352086491691154136015662564000,
2054331858356178785968594129696529488205875948604245488056299286633963 / 1508614813947459933819113021043111307012670551322323344845778456000,
2057321491371623447422808835378474678295992521343146433709194884183963 / 1499415943130707129344606234329433799043081096741089665913792002000,
2060293061149827939733691782279236647097732445698506047774369490151563 / 1490328573778399813409184378363800866927668484033567910362799323200,
2063246784648461033339785888667680565683390294681921974536474074352363 / 1481350690803831139834430255602573150861839155816498224155794508000,
345052540114949060675029439822107106182061447972456230659786738398992621 / 245904214673435969212515422430027143043065299865538705209861888328000,
345539957397605335542575675748709481412021809548975423450470571784785621 / 244440499109903612252917116344134124334475625461577165297898424707000,
58478140367397119416800016435507187290283735148306474913504322603905614949 / 41066003850463806858490075545814532888191905077544963770046935350776000,
58559547680912450610395964408795066687832680277783725812272003881630388549 / 40824439121931666818146016277897976812379011518265287512576071025183200,
58640480340926104616544218791942478466425642177811164013832023110153997349 / 40585699711861890988800133141769918468446970515234496357531766516264000,
58720943850238574993446433009392150223389249253076832404866432019351939349 / 40349736341444089297004783530480558477351348593634295797313558571402000,
10172563245656388796495105551375796820204071633349908569500371289937876393377 / 6940154650728383359084822767242656058104431958105098877137932074281144000,
10186323897119039901431222010310846914112382144990979024170558569050675213377 / 6900268704459829431733760567430916655471647866391851182441737062359988000,
10200006144207311677504431238407409931709231641046053151943743041968611875297 / 6860838597577201834980996221331311417440381307155326318542069993432216640,
10213610875290007378870387872959936225372224215342628202427670214853315532157 / 6821856560090967733645876924619201693477651867910125600823080959378624500,
10227138963722730145393041561098587862628781592775602519297099036416829075657 / 6783314997604578085433188354423612983345009766961480823417300840964056000,
10240591268184271808674827603172248173769909617762891298682864807185707231657 / 6745206486382080455739743476027974708157678251416753403061023869947404000,
1835460385307650292314581749901822354126209797358810489922319463960072922886603 / 1200646754576010321121674338732979498052066728752182105744862248850637912000,
1837841668037559379451473070673642763464013063037502317765380107420293354745403 / 1193976494828365819337665036851129611951777469148003316268501903023689923600,
333077979476441631009858847540158895717677052521212052706074191626258601891490343 / 214915769069105847480779706633203330151319944446640596928330342544264186248000,
333504268446957824476565229265953326498911264059372696967014451261744752282894343 / 213734913195099771395720477475878037128510494202428285956196659343471525884000,
333928234422312038777202642016356297687313719301970956353911169225360490883418343 / 212566962849771357344377742626283075176988578933562557617638207653070042136000,
334349902582312943915412956560153000526659375993877208166576592843802722217003343 / 211411707616892165184897428807661971507548423613271456761020608698433791907000,
334769297699585373237698672000003875897163539623423535867286293186463939523110743 / 210268941629773829156870956219512447337237351053199719156906983786550366004800,
335186444148302505189090528897020005429784187916641980471420157041395321700829943 / 209138463448968593516242617745213993319295214757214774430256946239310847908000,
335601365912685218281039865855220403245406960775866187323364677506928927714593943 / 208020075943893895155193191981870602980689357993807208791592470590972287224000,
336014086595276029041108414049950391197065456151034751625913954057622718475947943 / 206913586178234885074580462237286184879728244387457170446956340428254349526000,
336424629424994749051177026078198974897223647112120976170451565844186715201197943 / 205818805298984965047730830161956628345973068491227238328189375664083691592000,
112277672421660911669380051715489233121682324207235400247781622640387430596417181 / 68245182809663435778984433158964566241033175341827979024610161404406697738400,
21470900356822096571011824977825691096846675497036514251376617175486269382358535171 / 12966584733836052798007042300203267585796303314947316014675930666837272570296000,
21496630923403302488282870202390156955962240036427112831593239725403274595115216296 / 12899050438347323356350755621556375567120280901848632077099493527947495108992375,
4153790104534724405084076288464356384342919394615840802583024373024035887483980824753 / 2476617684162686084419345079338824108887093933154937358803102757365919060926536000,
4158705041691439014066042514523868999198185019173906013320855272826024953661592764753 / 2463851613625765022128523712950479654717572830406716032211334186451661746179492000,
4163594839509250147725343738508032258820624509868097803600166997596059790050164371953 / 2451216477145632893809915899037913092385687841532835437174352985495499378250366400,
4168459753843993266070711377715816688376430798492364502503538545102987082183528619553 / 2438710270629583746392518368940780882730658821933178113515300164140930503871538000,
822140107223082840660769616092271732935304554902371679635581575749467559017168909409941 / 477987213043398414292933600312393053015209129098902910248998832171622378758821448000,
823088839418668979937623772177740270661743833628310411169560649189080930708341721677941 / 475573136209845897049029895260310259818162618345878148076024090594998023310544572000,
54660843477706005378973832490666045471438399042093464563744199568137376476722555906616753 / 31387826989849829205235973087180477147998732810827957773017589979269869538495941752000,
54723148314280857289946225897244098718577176526722958059923639484246227167756470350994473 / 31230887854900580059209793221744574762258739146773817984152502029373520190803462043240
]
yzh thought about it and came up to xym's ear and said, "Why did you put the denominator\(n!\) About divided off ah? He said, and wrote down the numerator of the numerator before it was divided on a piece of paper.
1
6
34
212
1488
11736
103248
1004832
10733760
124966080
1575797760
21403457280
311623441920
4842481190400
80007869491200
1400671686758400
25902542427955200
504597366114508800
10328835149402112000
221649697053388800000
4976042317509795840000
116645883816108810240000
2850081244336603791360000
72467075895142688686080000
1914545944958638638366720000
52483812226093123521085440000
1490921189770317557276344320000
43835602323112218529856225280000
1332446705336234245944272486400000
41827511823053904039590520422400000
1354660802786268583843711470796800000
45221845327160072404359188997734400000
1554646245524132541209081596713369600000
54994400873805035337517574909853696000000
2000169494590713957869118380820135936000000
74739924805469832731163712335309176832000000
2867272655463516432659385028456759689216000000
112855915044919116752189714578432195559424000000
4554509343341692955693109139392993542799360000000
188346315761424009208750056972565064145960960000000
7976634399922888103249496905685018081566392320000000
345771838905576784429706482094891359895562485760000000
15333386431854373306283252333706003318849342013440000000
695258517319960322483196251506730867131352403148800000000
32218477966874346774582910266489920702280658373836800000000
1525154086541852996110535430221131125078049863342489600000000
73719140014871468085641779055492717708791827053464780800000000
3636807068672262913357528787458736305827873300696740659200000000
183044503246089144716950081410532032670130249211240775680000000000
9395489570089938869090807116105941908488510440079821373440000000000
491637281058049872375126843462281520894684684682615723130880000000000
26216541127665243610744819734197258838157804039340382895472640000000000
1424162329286872262230244632516574372792926816195673420527042560000000000
78786340622172397158043342260024256266127841676117287197527244800000000000
4437197037851631551321885275513808357241236497400895148644945100800000000000
254329531929799067053129586898366959745263895988561910953374488985600000000000
14831455692350295459141023198268684584545530238950162871127401876684800000000000
879716481591728312016223637916977107533709028349625668643212926071603200000000000
53058004571263795513877466839548890190030518592204733840749997454262272000000000000
3253041569954028616799340220559208640947024076460438568758107578807877632000000000000
202695416777791482449016530957840962828786747625916902023249032487353974784000000000000
12832243623307762044540546838241705561162363657498293255845915977259461640192000000000000
825197338549245263041301637941838001425392809179548047398159018575583183372288000000000000
53889618261757305985827357098181431156118718855329486196649833716563723597905920000000000000
3573083219527961252233948475704210287327405096038262418772534469667608454307512320000000000000
240477017935936207557015283182370989259972541304789834369332607598334719645125181440000000000000
16424835096540962041389535245354190355779823786289418987427487713560427189661251665920000000000000
1138237221635281853369791662907480872246475472021366595952646372083205651015613787668480000000000000
80016370383783575528030752090867637563856776732081347087800170416932891909155534248345600000000000000
5704948318136145504770956497556099191667656753717974974579529177290568087435868481624473600000000000000
412445257511268231086755130328797304721911996545793244215641406928833451646555898867036979200000000000000
30230122236487785180738651487128512664170843346804180689473582304969410151492645916824410521600000000000000
2245908041964744585969581200253374764696055230972290483723699427737513217033602942789765981798400000000000000
169100210120198208545829604818307489865385432025863373316602861853891943326818096656833933475840000000000000000
12900903462213702707025716967396336043308999638486935682766238677994263966957620109172807324139520000000000000000
997115746852975813552864124534123574417592834990366136121507558276969357700050251385132180087767040000000000000000
78063508943887019146136555349573394227981491493161596005835480206996772039258736910277322732596101120000000000000000
6189520585831458822338068844149675928183017586739518380082254080429394599760559461024318603093585428480000000000000000
496939559011495094546584338353895005512552291623141125969018013597981575126906526402245966782955677286400000000000000000
40394348575810551965334269329940328679195835127942383136737464123489733825799695434406727837343130478182400000000000000000
3323859265800913733326874741984539983372717610323396303377386678780532727035707329585021382785768910277836800000000000000000
276825250602857660847829000264464050404117775887733148211598670341887987943253812760726532850301528141358694400000000000000000
23331756165700755400066588826368232050142122368090803348996119862841253746364578631422174936173727426448824729600000000000000000
1989788299113997708953146927928379866227510297356794740192632656048744316952009620769809761428764160983591550976000000000000000000
171681900306545347672093532302713660683237998175059254019889493399664748251061127536241590170055430975872267452416000000000000000000
14984497807025352657207973408798744937712795525700683289025658352851520862315643200273146233778172792908012314427392000000000000000000
1322827094519606416536347095488484892449470288867230412477153041308866423952982045521921445954317134043448980952580096000000000000000000
118100468939461388422247271589247548607168067863344244047623140865951676202067730856915128289000597518730287837341548544000000000000000000
10661872632231084481725573484711541066980425219205025648649225297770330310692668768401842271010384173509355649493222031360000000000000000000
973185333506831302370565015656729434951679995203990215019109022303802195888186611167920231012115940307979869492440161320960000000000000000000
89801965272199678649105005055204477474111847721759628448574571304280404377863194151103485828892796523130004712743560879800320000000000000000000
8376324398271084888581460952217004016105410234688919367753323868729356728892472535094744589050749408896368902090779707320565760000000000000000000
789675600037590621368920264508684984833260490528195372224827887983403087992424369409817954903680297085519001681625083987561021440000000000000000000
75235498462395376004527396493676340520731905454109349692438457965010170512212029481877948730989278209196123052060498362421267660800000000000000000000
7243159072750768540651802102306461357580054229471152133340208968409010911947674818582396379816526973604495816605885093621801995468800000000000000000000
704559455948078208762381347024711144560486229809664175152019809794779808610555045699342956028901732513131681118011921363318722894233600000000000000000000
69238220524341757748730819288919277670551179965536783849418705938472250242836549138033233759707510930840445242849788684186223339424972800000000000000000000
6873341420047918030495750152663173410633473860302380331443282260986022854435252330387557288650283451320200029459116616977127288830374707200000000000000000000
689191239423221802855463373857699617830687895701761586622036591137729342736319808127135675168392267768625253298477617564417323174608240640000000000000000000000
69794034350478850952238382244951632134876002242724039675548195703062146640354828152902496705320170516020795442008685549285069499205156864000000000000000000000000
7137750073053075571817336535995176084555986138378992752821103147455277694914831684633451898201864852809658128366972198002485577146320289792000000000000000000000000
737101724919713970859618542701773172869427721750360869925544185726637249028888856476975672350695216933817846790268856962971438496450418311168000000000000000000000000
76855675959308473064890335880517348185853831022574760662452331481950222900606143264679149491658187273650978113363935346276317864189630938611712000000000000000000000000
8090344980210516065257106968031305830347268900622126868997315736353002149261937200917563974926403556201331979795110510822310512341735184581787648000000000000000000000000
859729062402050139090637692639054312271968741909040254199821495834787793013852678316741207705380709550017506690447316568103206874297577263712960512000000000000000000000000
92219184393008066262704598487902680969191711713007811643580321324639244650715226567243302961682892460563566036053120871044879842733389402385483300864000000000000000000000000
9984087690452420444323678235975849387504097612826185407938591923161588730914706307814093376727454662191256603428888594758465208677718667234066040881152000000000000000000000000
1090902576696185525000887193878600861098679926951246542651626968678196081764561248565278629665149275877162724715843510319154615544773225028592356156243968000000000000000000000000
120286730711401454637564067855301532395013607395903238391932948154693518207976612714801025522427415862663378941175020084888096040971867316273787734683811840000000000000000000000000
13383447633837696074219898449982405361836579928593893191890560907732247432073455393922734117251282902537316465782315969584902898107409358255899619637508177920000000000000000000000000
1502456157636587222210968694789116461330348046664334694960618388044387961735238552569188372321209092037205357019272426371345207761875624445640520834285295370240000000000000000000000000
170170684231827480669882954424675038031223123599603744640627148865142298047066412814883637965432084496621628061806597049259640001083821133729379235738912785694720000000000000000000000000
19443884406715806961896235262800052645436223610662696340035742637022575120633769718470935928539138882972350139447055580684210235480485046010056899299840519915438080000000000000000000000000
2241111514311775577595841353160172537543607833819175231493932433883075492108317134359428009530931789110352870240094530962359500743280655768741639203851348962023833600000000000000000000000000
260551410839131097951698107195539372123830534925614407330338866874528228430662717094464435367762483675321250856843705818633825432242262673657891427588408926809148620800000000000000000000000000
30552084732498027122803574848569396229000962438138831019538902647960806815073526971670225126039838683548797028208757878292202451935081134338120785681337282254356453785600000000000000000000000000
3613051941669540123299613768829250130585661983785161710700148045725907924996879267625433871753992237871297885708936552033092655208564852900757760603586633233877347126476800000000000000000000000000
430886116291465324083073499003612943741924521565073799314083108330495992254441911050021949205253417752945318791107803126443940123796874351191856642827783555889777857475379200000000000000000000000000
51817357217615015578529631083432111953727049092077323219163367545212424333352851190742126143927991393698678686318138877936644709451961737610865650082198896948468979846873088000000000000000000000000000
6283223483300703063058448362886348871802922159921522685557606351747370764503874545366952954461120328725312201673298788960684474207461274760285708134832225917026626774509813760000000000000000000000000000
768165435164827013314009436723170342153363915376712032822309231709083926956768730615205677118087228484983354594874716849026666645780322878123091926398099467528686021975820206080000000000000000000000000000
94681039979437867320497424152094371310032052591768837527656159124989047947166227512446652486606221278058356374196564346334796166646734081016186901987172633385153768437232403742720000000000000000000000000000
11764642815742337871079588965544750152074757311514932834463961983121797740518764496737398188463968973841283591047765987414675170334396252506256652084071008443039140699284442898759680000000000000000000000000000
1473580489146447490314862882773838449085641855560221999739881490676196538830259017506376069327267443860096620632270408056636696291417423241195711459800292902006635078685688056638341120000000000000000000000000000
186046170926088657858741681755839971475623878207411984879593163502365403380025210494746215537551573805254397839314364090155559015261923358541514859782293531387440478054522189342918574080000000000000000000000000000
23675118904753171593163762152324215558929877163924066678606118920909002871502436746148356989424313349973853773359852683942654165580018953064824926940198473797141546633191134836625149788160000000000000000000000000000
3036416818112892482545724738179502316756866904733653970414028078300375649469851081811668188780963459834307663102866501925315541495907190522994861015205456009070122445248726556434611285524480000000000000000000000000000
392465997841269833432325035379925199083178492764903135742168225560400608919553502160017500829229203327931764034155950808276923634985519274409543003098906052015583364455842493031327249381457920000000000000000000000000000
51119684183332261514588323605332606036451899788602095109183528222494107124003772825497371453127042824545375047761369746577331260991708967879686481946355761876970166282949808860729513785006489600000000000000000000000000000
6709562593952742432881681098748140234471869934591393419677848132928594944997933096116061745938353229471657609318533768255719797279753697141575752801742296815865212300580806689700220275835640217600000000000000000000000000000
887350111684448544768906311481989533601360380181947052345418677102863120831596591016518967003189465356472407946018201294840933754086813012313475922005642059611942962515519657029201698812207510323200000000000000000000000000000
118240367426201769433703433585444026495407892163254977755118732540063211643511071538177431907322388878419478846612660205443212846151317103310361047251685165536839455577073725126014795902225760229785600000000000000000000000000000
15873842824367731218263684121965518029679011605902705317153089384774086070193780917506097994100282564881527761153064282641038109281176980908569189692487098535030089457428967317930702533817915765319270400000000000000000000000000000
2146939794074905845361782920344799017849013007866896921585902921427021692972411939089744847130825455940740893571324561486463606993739395317700363330032905621793993832168381309927245022300740079482568704000000000000000000000000000000
292519913592904643547044817375127879559230637290161512399734938178033446758277544756847972018058173486546780413607676693658755120179172022962825517831623000822550689473424418619955173582572549793428537344000000000000000000000000000000
40148139972596255334050574986036702668483064609266407064854197956070588135124804402215726756401138434737954273593981137097854253167093119908575318245874371891573061642994911316693921168766886995760280240128000000000000000000000000000000
5550432503286013693934472303385084277083683041294609868190501119460424779403133370783065668083784846692675520058873434851285817112749435089716773097501258699186126561529315174164054834721464107416840688369664000000000000000000000000000000
772888662362531526163676254900857584332522174305910429161411620338944484854540750760355663686040288584709425700864395096635996781489544270995943037806602361647550107673233988748882617094183876216370935990583296000000000000000000000000000000
108396035416045973494149396778562344823493729827701546871479653334433313004079902351465878430034151289257089420314264164427576401484524897595063153846046617490518458485581186777931056085787776719022295583492669440000000000000000000000000000000
15310668861381947900996775121539038553975339351922676086350233536009297358163968084838164715378455912016920768821987722587523498820000024139766831755175733379203848628180766035908805759246977176024065220277216215040000000000000000000000000000000
2177897803821913226355793244012906068636396182145662509042137603115844371222435908577819605369743680102510073388991047081848673030032227134629927925198479325205451691297086797409715386717287360826862399278672437575680000000000000000000000000000000
311976560630352147753226706869038915100629727575196122665810297919315641925836348572537531007406710448988017214204985022031031685616752617518142177183783061196053728655360512614843621489842395313117320753741178328842240000000000000000000000000000000
45001442608700521915597418253120666547102860013559646453034257453973884681689351905575971537426690859228471421747895462462399281000109808848964235785276806575419200941534550780089574704889846094244482970073639818950082560000000000000000000000000000000
6536271222219882486613022540366232492315095222320322714468269145752483495480551646598023252634701303866302449955748280208900690862813528962711753400641969129460263823000719630204712744300531691115676413758833026516857651200000000000000000000000000000000
955899633361764502129681545690369006044105897354444134782185442771053047955167325539088883086482070768802433260356879161814852509253929234056719000804893513240692408863600458578839987962651253293302070551691465074383467315200000000000000000000000000000000
140751440752451816778658293967886167515122576165854470492337580964129508634410327991976623303939897740939142525057478221057548933352828231531273273626657236509443876553877911319210331421523482211774538593450698216963104466534400000000000000000000000000000000
20865640649451522570383102684606161345160352742992324494231957496323800781003248393705453610896960646173644492008202503703234807279724393134657634403912550251224739059409757435729705881331132106134049044352270748005065976656691200000000000000000000000000000000
3114075832145118047775132621051278470113096314391470148217818989302687107708691155146655891571068146252630223463714682269457778818631595538675201930020202289760198818524356311150690013430824705922129664689709402260966920451574988800000000000000000000000000000000
467870603025375948246078503028377467626113126090642014199662417416541965899036518163396978483898994528953907167878804832527674065582614467169356697418519777637307583398449130177838832265865860423187655913158623725198497813333278720000000000000000000000000000000000
70762347843696922219994734019065867954673327141020393264086238125725308643476706070136576056216174294088491684054668259091976365295037495654809130835593691075939497326743318642852785551011365215762997507023124938606211166870878289920000000000000000000000000000000000
10773074157950834199756541158822447701659946281706689166660055256236034042375037787577090659465949761356209245447812378497433370066155503375375361027718213585581861313885800903171350336298151446500169651521522348320220671167545831587840000000000000000000000000000000000
1650894390728070304413532623453677388392051097549940815869132590043608685205329833011975591060870674998334453370291598730510360089067132428565279420984447700906028129440683737278570024525726899682525921717218828378227847343838976299499520000000000000000000000000000000000
254637693617256279906094075036592906532393549255585847457179363214963296270233197016939548570361627050873157909934970532795247616027579257056739130364118110937496897057868600458285475835123681848602319927936799059327788704202948073310126080000000000000000000000000000000000
39530437268561160834964275095204466410120837702547967835646610245799757092315893631973891309683271494535047306735450372138745507421721652314884971046247080549802450101148515809639243317276679068640110764936035356168297641665056126326433382400000000000000000000000000000000000
6176295602002329404498218879683319173018544070873117627888533519435330547658836386449999882521853407506760529138930543733407076006144755726852700604690571565270099649938498479330618606573167615069198847623741704008062014569299668865902863974400000000000000000000000000000000000
971167832956720832001760790209629710230508247055985513169635562513064862684121889417799564617335307099563753435451884269682013385958285091957445995197752685621003460294876634322743862231357101396991954674334507995382741183641218784854824242380800000000000000000000000000000000000
153678361876754546052471928086494463489898727195979551576377913541150309005409118699434079896748786369076098005532328944776670136122146895484479932285490471840748881528032008905168232449651617848899343223593700972079351290535056768970263087179366400000000000000000000000000000000000
24471807680105904876831089545006486133935033301122007747636695564903525751616199313394244203027022039361847856144362998666470213002894808199890415826885520333340839599395713748947147995106561933445843989205043224190466920901045110798652336858831257600000000000000000000000000000000000
3921364100643239919598017570118209700368698412358193051138289480295203310344644273829006432373689974947139422109246971768360387473639636955630851061957769359905344760733361623145544111273114553406423653499836922002794295886863305790923453336718934016000000000000000000000000000000000000
632279618228487544281435713091876799300400634681865967516937309830548333471338399862286823059951327739165450148747746524753598109613406203968521947564116776759833300035815181446020664736156474048333733932496422489886417443696942650794440177246562942976000000000000000000000000000000000000
102580640781730327342041848397981599881987235650459879463541430562188761188439863104981845283418550007364362559818782027410219223869338357504311229579389178424754871336603720183415356798530274155036458755776034062535080751244540363008285668589140927578112000000000000000000000000000000000000
16745162424746292873247734115655126417000515281001193419596667150423015240163724010554824679703696345321755457800096403932284081075788123075853008564338690156269893173137056751325637593716590255665989817174608951065113922460302916843556886324546817287520256000000000000000000000000000000000000
2750203143869295241873486476485038920461944483032334021060370890863169896642233356870039458791424118111064593478405529275549778152016795103200070321652452544591992534569399107617507964849494766870396406348248950793890174814114648651799406358584228953911721984000000000000000000000000000000000000
454438958053964028852000335090706809637835641642835788987083129623830689773996654599650075966948902625281634297399100681397874075672530038529046033406179171827296539334958566243430079725342305165398543793772796657443545644556121770310897003779973538997715599360000000000000000000000000000000000000
75545016528422107135309019192310422822099946646073329497641888193581067382645789923595565232874165654688484202256708923090321291307514690743863885346880323649547422652369642451699364251765777937873561714059847401888613695874172663720459397340411674118919563509760000000000000000000000000000000000000
12633970904551387450441804883612885117793740493339831960257585094410454109588979094680672883161191684481220001044174782672689871897734731402761217622583852797827907746653613312733677620662086564986576262509675220693101472826531302952243679139274291461850425899089920000000000000000000000000000000000000
2125505341302657311317259149600921274503776091472224999740254729363988869643429734143634377482662457922617118037711551433220232079524013035684942494397652757441384932596249205004426952590679705375193695241302736132774176253153534147444673693308042005661103250011586560000000000000000000000000000000000000
359714114212628860291084198854682123536479471885925990648829686957190268054307683090528576704262055244916597367609962596234445117209581101416275059651222749019441662741375866741195260059030826345590850913946067798951018644859779459937256364754863214232189249247657328640000000000000000000000000000000000000
61236528168752503035144345041187035197848207965006892970478394005772449618700679775762160239602543198940220176372814824147942563402988836240750604190849563510614826662009520235614636898725976038937785906507789435381284347813857825244574579630195062211817252624509226188800000000000000000000000000000000000000
10485918457407203969891727065946352549396096857192411033343854038950778828709070232170105559230818694776274093959925612920729294704556297428201215065824200926173451511350332443876836331277931015354779691552557380977142305997093285770863238264402695935132447506626914340044800000000000000000000000000000000000000
1806052753398859110469259339662767717218247153600416787654544254728959050126560061733085807793192548055212562589119308357950281802878499136432246146485426320519552206677757059147768463876287600313622015325381700545581359539281581895965338069998362689078683900152346821892505600000000000000000000000000000000000000
312872795536087286174616586061426179748224253285955185026824566536748830325695930951100358676717638055404500809026713288684512544119511264395973199359029693586841024192468230444623397979405510608200897290924123386966757373873750250433918540142056976756068075709849232378481868800000000000000000000000000000000000000
54513508435565904203025316011388433467112889446725152668288454977420632323774747174114052312130538754968490571467477232998818921541009666781832772590663011546288521711601462831019305021791055132821282915430790217693053538681206569235880366236260390165198250003719271968020837171200000000000000000000000000000000000000
9552677899817029968072009157451394407699047654477658429651758097552903315319941696421271312390595052442441262100029817075682074915351106360809405031321037568198805890299197780158909759246606783329395325675723577014688575959225305947925974670592949117579384198077152892147004866560000000000000000000000000000000000000000
1683513783924305399972548665246223297383995891715415872481815582991212067040253117533283180642428974989615455659210310464679615966505899922651262098113067368525915634499675405329715231772027609644683796167789628387031915177059387729819381604950515957688368224367078325043126977167360000000000000000000000000000000000000000
298376621525973149246375856337044937330546307978592363629614583817554203650327443788522468151271403632738971088803408258412078946552195180588400779514980517837742417249984078005926405440077480916298932187576602268295594925511087426923925638962313497521387913515767424075187155076382720000000000000000000000000000000000000000
53180898429605395192459780170261961710804987251774364147605021679704697936644158901058538399848074298198482886962531263858728268428233416674004929554005730624458718878167673732008605967262212368351780082432676007131669712435707639555094007197063574538292084862820904782784382088941404160000000000000000000000000000000000000000
9531816060843303254075562670123937737404300144012763202795421755004006149003423103141011538999714844177699524566087396104025958345288251709424941137870463556747840504866167593959671074020013404259386695850413038931162381384854601655002579477850666789467434049395349173376750394704280944640000000000000000000000000000000000000000
1717952834288609947154381281468762941134188113497256898437525245964412479116096058167989194006479359089652595958024544199427731424286910768398310591243620501758911154262641969237743834115871139092197971761075993437510070149750741016384186104995696727290764282364015180863868183626504155955200000000000000000000000000000000000000000
311350139042000562732592153778882478985129142889374573796528826660238970414914881845949842279518558074088740658859511535984596612992902476895667693936611844465136738308358287046056901214053854389703219836011600193791165766186528068510306442775703913387521285383290006996941735262969408992051200000000000000000000000000000000000000000
56738248784206289899507931420376957704142736068894563698804743608156268810318684445082637324730844698298713805382905600808287826164427516464805293361533395682536119753055942192519854252700127293763645742278762524675250561169973800715447009019693300864657241374008652545734738380107392733308518400000000000000000000000000000000000000000
10396299001504131672500312123617223226575519853619213166495288503118617619787540229585900989040123709330224829012292185214470888012271274051293330656612957220029225363085012558975964481485580446277358687124509286247686343307522546410917024111703462530348391862669398629729174797707331630244508467200000000000000000000000000000000000000000
1915334556379919193706301671938708966221677542141842872989566629169783044241384673441325771963419141512479947768361638596011394240539860403660788526115900746024251899945272455205266537623181508934266403463907896794476303811695206265938623377767887965646565898318306826263283989482364722527133813964800000000000000000000000000000000000000000
354781358927184391419936848987489839086152820507821845764587939515886836031741792013759350133915344603730586226661253295681096031998892733152376080729726490481687548897975070308695163799348109960199469721428964503297415766171782331686431093388165394775176325855812078437776173772817832023070907301888000000000000000000000000000000000000000000
66071560180961685437104620424026657972026695723352677357717536064287399862737013531974328316311740802753273925664350928125641943335427192906471216110906098191754852828593757979965156396392061541688455935577681730517120866552122233408201258406032826644206264585599469550070630149397337494461491202490368000000000000000000000000000000000000000000
12370676276892375417458633438196469485901582554356927541267649019737753512125251653303819033773542982954536700397147535866747178676802556822864513374277303239874195660596366222297853058417654922577001749744199024362399212584871945310223685525409089609110936584719779558990088354308518386164349554776866816000000000000000000000000000000000000000000
2328547257091721125168683938522946893630923020283399994091821962070873734642438402630623264841080155682544370878428349702658816332412958069832515800131178428910356053643511615771829850613834284161471720490270517746030752300236543863540343722488772513161192364741877119177567113210546585186876469555293585408000000000000000000000000000000000000000000
440633141260968838464892168553647942650895826683452331712810019031146736959211039901856853932248980527103538691636881642863342198956966439200412130767457763451342172879318220754430325622974399559143629252091616377481625819976418177430124012921140577705198821045788285354000034248973538225606543019848983642112000000000000000000000000000000000000000000
83821925401226274488832394276265511773245329509154035569488570120786131969981406716253399781085812138185681965722294033379328610730332687690772906175432781462392887688738369091011222129287474860969777826840647923962300967690673523793524972116889158041166648004646793104383683302299975565334132867245519698657280000000000000000000000000000000000000000000
16029297447918017055946833350603761225146981531604817788528762029436776551804754795913324297060020706415633437635270533857163476466634213854954752368212461865985151927285139522629061484917059053750619785596784662287463082138233712524747664304271678900829937940394144671010376594299738520138365896564985343487508480000000000000000000000000000000000000000000
3081313312939531524670274998337990596417484773508361370147968387281359801808037932762469284362673654436352424005332345446066445050044463355482657690658113300740665028394174432645418349259151661830824388951514822939678235805425616550584132884841745623013355895994629060065156444150247638395536100437832814859292508160000000000000000000000000000000000000000000
595401614041992531502880965846815840432244516037800385013516906401026112834468746742230095233279428570229941621748700562617089863962711715761365265127143130811081682727515556480945298941337263630405882404188132138764311345418072233734892036930766829774052316352668787931707346451663886794385006262445188180259771514880000000000000000000000000000000000000000000
115644586889508130902924449189185102812851997613084597071998180222767979118715783105992416141383806814885468325956453442676753502671328242310147303980261086797037616474544693521976121396543731480983954849277937361654380742632649134654703918141995474170527832226799315722324720589823414309162179867284027569962077619486720000000000000000000000000000000000000000000
22577209508931025152555679757337607407664898430986062714333061702803260078732578626090446845389936868484058189062877820035778315920524152701316070967509509335229865682582059404580073881477009627959027802604217418326492523722599509241499168065343606648801157035074214382401808679413442488118071149274001881222895307744870400000000000000000000000000000000000000000000
4430303570032865234428944535997826095045149288541306998174533256718240536743980106994247077075474795535664341805487729841577123103632957615744490492086819674998426010872594433909573317885225170786658442859486437271522852107418062320966546163936477861502449792769950195497649095000823262241033184295282723170305511625483878400000000000000000000000000000000000000000000
873783235819611703878491139760995645002621947257052931472181836690604632633843087807707828233162754320149506395938112500127392177775238935548238628764440515626086257923806026951144046286342910640386886284830566512535732082562614430358805261949677886578288053120294819466296456051948035664777515507764942313103840795463306444800000000000000000000000000000000000000000000
173208729491240192305707603189041292438861408349626898591921151541979730371090576732182427264102376627307272479463466186470551643270144703765336676148678929230199751187973880919756088254010439025729697983223987164796352464332011362999212397078484001476868460953024961960382143981901927647655944369546158243524972082984743495270400000000000000000000000000000000000000000000
34508068138962510193218228073132898366290044127266128110259978729544632043904832028276649631335868142789041644863266984616846386941999068326914741690592381753466496061329642705842076735716044647732878469720770992004093744969710758732788221852859089819578251943533902855934633181331297580616164385029156137976097890011827393894809600000000000000000000000000000000000000000000
6909480390941844295676567428594697197623113573773371546311493554594806074651204373673906830808700208851525875535948650607178631262463289216405802229327176689453400839259307763202165261831920919770488164062329596672599403770255946546978528217914426175965560125872358839748688187388519707546668897740528264857333207336049158358302720000000000000000000000000000000000000000000000
Don't look and see. This string of numbers appears on the OEIS! It'sA063090 No. Sequence.
This sequence is different from our problem, but is also related to an alignment. We may wish to remember this sequence as\(a_i = \mathbb{E}(n) \cdot n!\). So.\(\dfrac{a_i}{n \cdot n!}\) for, in a randomized order of insertion of\(n\) The expectation of the number of comparisons to find a node in a binary search tree of one node.
\(\sum\limits_{i=1}^n \Big(r_i - l_i + 1\Big)\) With the shift in counting perspective, it can also be seen as a way of making a decision on each of the\(i\) Calculate how many of its\(j\) (used form a nominal expression)\(l_j \sim r_j\) Contained within.
A binary lookup tree is at this point a Cartesian tree. A number of\(l_i \sim r_i\) It can be thought of as a subtree on a Cartesian tree. The number of comparisons is the number of nodes found all the way down from the root, and so is equivalent to our problem.
There's an interesting conclusion that\(a_n \bmod n \in \{-2, 0\}\)furthermore\(a_n \bmod n = -2\) if and only if\(n \in \mathbb{P}\), but it doesn't help with us solving the problem.
The author is too much of a rookie to prove it at this point.
Find the generalized formula according to the following:\(a_n = 2(n+1)!\cdot H_{n} - 3n\cdot n!\)Yes\(a_n \equiv 2(n+1)!\cdot H_{n} \pmod n\)。
insofar as\(H_n\) center\(i < n\) (used form a nominal expression)\(\dfrac{1}{i}\)，\((n+1)! \dfrac{1}{i} \equiv 0 \pmod n\)The therefore\(a_n \equiv 2(n+1)!\dfrac{1}{n} \equiv 2(n+1)(n-1)! \equiv 2(n-1)!\pmod n\)。
(coll.) fail (a student)\(n \in \mathbb{P}\) When, by Wilson's theorem\((n - 1)! \bmod n = -1\)So.\(a_n \equiv -2 \pmod n\)。
insofar as\(n \not \in \mathbb{P}\) Careful discussion is needed.
- (coll.) fail (a student)\(n\) are not perfect squares.
\(n\) must be decomposable into\(a \times b\) The form in which the\(1 \lt a \lt b \lt n\)So.\((n-1)!\) include\(ab\)So.\(a_n \equiv 0 \pmod n\)。 - (coll.) fail (a student)\(n\) is a perfect square number.
suppose that...\(n = k^2\)which\(1 \leq k\). If\(k \gt 2\)So.\(\dfrac{n}{k} = k \gt 2\)namely\(2k \lt n\)So.\((n-1)!\) embody\(k \times 2k\), so the conclusion holds at this point. Otherwise, when\(k \leq 2\) when the time comes, i.e.\(n \in \{1, 4\}\) At the time of validation, it was found that the conclusion still holds.
In summary.\(a_n \bmod n \in \{-2, 0\}\)furthermore\(a_n \bmod n = -2\) if and only if\(n \in \mathbb{P}\)。
We are more concerned, of course, with\(a_n\) of the formula. We have
\[a_n = n \cdot n! + 2 \sum_{i=1}^{n-1} \dfrac{(n-1)!}{i!} a_i
\]
Think in terms of using a binary search tree.\(a_1 = 1\) Obviously.
Consider the enumeration arrangement\(p\) The first insertion into the binary search tree\(p_1\), i.e., the root node, for\(n!\) of each permutation of the\(n\) number, all contribute to one more lookup, so it's\(n \cdot n!\)。
Next consider the subproblem of the subtree. The left and right subtrees are symmetric at this point, so just compute the left subtree and multiply by two.
The case where the left subtree has no nodes does not contribute to the answer. From the\(i = 1\) Starts the enumeration, indicating the size of the left subtree. For the left subtree, it is a\(a_i\) subproblem for a deterministic left subtree with a right subtree of\(A_{n - 1}^{n - 1 - i} = \dfrac{(n-1)!}{i!}\) in the middle way, so use\(a_i \cdot \dfrac{(n-1)!}{i!}\) It is then obtained that, in each case, the left subtree pair\(a_n\) Contributions made.
So get:
\[a_n = n \cdot n! + 2 \sum_{i=1}^{n-1} \dfrac{(n-1)!}{i!} a_i
\]
Further, the recursive equation can be obtained as follows:
\[\begin{aligned}
a_1 &= 1 \\
a_n &= (2n - 1)(n - 1)! + (n + 1) \cdot a_{n-1}
\end{aligned}
\]
The proof of this is given below after the introduction of the generalized formula.
see that\(a_n = f(n) + g(n) \cdot a_{n - 1}\) form, it is clear that the generalized formula can be solved for.
\[a_n = 2(n+1)!\cdot H_{n} - 3n\cdot n!
\]
For general series we have:
\[a_n = \sum _ {i = 2} ^ n f(i) \prod _ {j = i + 1} ^ n g(j) + \prod _ {i = 2} ^ n g(i) a_1
\]
At this point.\(f(n)=(2n-1)(n-1)!\)，\(g(n)=n+1\)，\(a_1=1\)So:
\[\begin{aligned}
a_n &= \sum _ {i = 2} ^ n (2i-1)(i-1)! \prod _ {j = i + 1} ^ n (j+1) + \prod _ {i = 2} ^ n (i+1) \\
&= \sum _ {i = 2} ^ n (2i-1)(i-1)! \prod _ {j = i + 2} ^ {n+1} j + \prod _ {i = 3} ^ {n+1} i \\
&= \sum _ {i = 2} ^ n (2i-1)(i-1)! \dfrac{(n+1)!}{(i+1)!} + \dfrac{(n+1)!}{2} \\
&= (n+1)! \sum _ {i = 2} ^ n \dfrac{2i-1}{i(i+1)} + \dfrac{(n+1)!}{2} \\
&= (n+1)! \Bigg(2\sum_{i=2}^n\dfrac{1}{i+1} - \sum_{i=2}^n\dfrac{1}{i(i+1)}\Bigg) + \dfrac{(n+1)!}{2} \\
&= (n+1)! \Bigg(2\sum_{i=3}^{n+1}\dfrac{1}{i} - \sum_{i=2}^n\Big(\dfrac{1}{i}-\dfrac{1}{i+1}\Big)\Bigg) + \dfrac{(n+1)!}{2} \\
&= (n+1)! \Bigg(2\Big(H_{n+1}-\dfrac{1}{2}-\dfrac{1}{1}\Big) - \Big(\dfrac{1}{2}-\dfrac{1}{n+1}\Big)\Bigg) + \dfrac{(n+1)!}{2} \\
&= (n+1)! \Bigg(2H_{n+1}+\dfrac{1}{n+1} - \dfrac{7}{2}\Bigg) + \dfrac{(n+1)!}{2} \\
&= 2(n+1)!\cdot H_{n+1}+n! -3(n+1)! \\
&= 2(n+1)!\cdot H_{n} + 3n! -3(n+1)\cdot n! \\
&= 2(n+1)!\cdot H_{n} - 3n\cdot n! \\
\end{aligned}
\]
(of which\(H_n\) geared series (such as 2+4+6+8+...)\(\sum\limits_{i=1}^n\dfrac{1}{i}\)(For the empty sum and product, let the result be the youngest element of the operation.)
Note that for\(n = 1\) The above equation and the derivation process still hold.
The generalized formula and the recursive formula are essentially the same, and by showing that the generalized formula is correct, we show that the recursive formula is correct.
Using second mathematical induction, for\(a_2\) Obviously. Suppose that for\(i \lt n\) Established, launched\(a_n\) Establishment is proof.
\[\begin{aligned}
a_n &= n \cdot n! + 2 \sum_{i=1}^{n-1} \dfrac{(n-1)!}{i!} a_i \\
&= n \cdot n! + 2 \sum_{i=1}^{n-1} \dfrac{(n-1)!}{i!} \Big(2(i+1)!\cdot H_{i} - 3i\cdot i!\Big) \\
&= n \cdot n! + 2 (n-1)! \sum_{i=1}^{n-1} \Big(2(i+1)\cdot H_{i} - 3i\Big) \\
&= n \cdot n! + 2 (n-1)! \Bigg(2\sum_{i=1}^{n-1} (i+1)\cdot H_{i} - 3 \sum_{i=1}^{n-1} i\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(2\sum_{i=1}^{n-1} \dfrac{1}{i} \sum_{j=i}^{n-1}(j+1) - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(2\sum_{i=1}^{n-1} \dfrac{1}{i} \dfrac{(n+i+1)(n-i)}{2} - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(2\sum_{i=1}^{n-1} \dfrac{1}{i} \dfrac{n(n+1) - i(i+1)}{2} - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(\sum_{i=1}^{n-1} \Big(\dfrac{n(n+1)}{i} - (i+1)\Big) - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(n(n+1)\sum_{i=1}^{n-1} \dfrac{1}{i} - \sum_{i=2}^ni - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(n(n+1)H_{n-1} - \dfrac{(n+2)(n-1)}{2} - 3 \cdot \dfrac{n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Bigg(n(n+1)H_{n-1} - \dfrac{(n+2)(n-1) + 3n(n-1)}{2}\Bigg) \\
&= n \cdot n! + 2 (n-1)! \Big(n(n+1)H_{n-1} - (2n^2 - n - 1)\Big) \\
&= n \cdot n! + 2 (n+1)!H_{n-1} - 2 (n-1)!(n-1)(2n + 1) \\
&= n \cdot n! + 2 (n+1)!\Big(H_{n} - \dfrac{1}{n}\Big) - 2\dfrac{n!}{n}(n-1)(2n + 1) \\
&= n \cdot n! + 2 (n+1)!H_{n} - 2(n+1)\dfrac{n!}{n} - 2(n-1)(2n+1)\dfrac{n!}{n} \\
&= n \cdot n! + 2 (n+1)!H_{n} - 2(n+1 + (n-1)(2n+1))\dfrac{n!}{n} \\
&= n \cdot n! + 2 (n+1)!H_{n} - 4n^2\dfrac{n!}{n} \\
&= 2 (n+1)!H_{n} - 3n \cdot n! \\
\end{aligned}
\]
Testify to the end.
the reason why\(\mathbb{E}(n) = \dfrac{a_n}{n!}\) For:
\[\begin{aligned}
\mathbb{E}(n) &= \dfrac{2(n+1)!\cdot H_{n} - 3n\cdot n!}{n!} \\
&= 2(n+1)H_{n} - 3n \\
\end{aligned}
\]
in other words\(\mathbb{E}(n) = \mathcal{O}(n \log n)\)。