@qq290637843
2021-01-16T13:03:45.000000Z
字数 66250
阅读 322
用分别表示内秉坐标轴的方向，那么显然：
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;using lf = double;ul T;ul n;class vec {public:lf x = 0;lf y = 0;lf z = 0;vec()=default;vec(lf a, lf b, lf c): x(a), y(b), z(c) {}};vec operator*(const vec& a, lf b){return vec(a.x * b, a.y * b, a.z * b);}vec operator*(lf a, const vec& b){return vec(a * b.x, a * b.y, a * b.z);}vec operator-(const vec& a){return vec(-a.x, -a.y, -a.z);}vec operator/(const vec& a, lf b){return vec(a.x / b, a.y / b, a.z / b);}vec operator+(const vec& a, const vec& b){return vec(a.x + b.x, a.y + b.y, a.z + b.z);}vec operator-(const vec& a, const vec& b){return vec(a.x - b.x, a.y - b.y, a.z - b.z);}const lf pi = 3.141592653589793238462643383279;int main(){for (ul Case = 1; ; ++Case) {if (std::scanf("%u", &n) <= 0) {break;}vec s(0, 0, 0);vec alpha(1, 0, 0);vec beta(0, 1, 0);vec gamma(0, 0, 1);lf wx, wy, wz, v, t;for (ul i = 1; i <= n; ++i) {std::scanf("%lf%lf%lf%lf%lf", &wx, &wy, &wz, &v, &t);wx = wx * pi / lf(180);wy = wy * pi / lf(180);wz = wz * pi / lf(180);lf w = std::sqrt(wx * wx + wy * wy + wz * wz);if (w != 0) {vec aalpha, balpha, calpha, abeta, bbeta, cbeta, agamma, bgamma, cgamma;balpha = (wz * beta - wy * gamma) / w;bbeta = (-wz * alpha + wx * gamma) / w;bgamma = (wy * alpha - wx * beta) / w;aalpha = -(wz * bbeta - wy * bgamma) / w;abeta = -(-wz * balpha + wx * bgamma) / w;agamma = -(wy * balpha - wx * bbeta) / w;calpha = alpha - aalpha;cbeta = beta - abeta;cgamma = gamma - agamma;s = s + (aalpha / w * std::sin(w * t) - balpha / w * (std::cos(w * t) - lf(1)) + calpha * t) * v;alpha = aalpha * std::cos(w * t) + balpha * std::sin(w * t) + calpha;beta = abeta * std::cos(w * t) + bbeta * std::sin(w * t) + cbeta;gamma = agamma * std::cos(w * t) + bgamma * std::sin(w * t) + cgamma;} else {s = s + alpha * v * t;}}std::printf("%.15lf %.15lf %.15lf\n", s.x, s.y, s.z);std::printf("%.15lf %.15lf %.15lf\n", alpha.x, alpha.y, alpha.z);std::printf("%.15lf %.15lf %.15lf\n", beta.x, beta.y, beta.z);std::printf("%.15lf %.15lf %.15lf\n", gamma.x, gamma.y, gamma.z);std::putchar('\n');}return 0;}
分段打表
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;ull v[2500001];std::stringstream oss;int main(){std::freopen("out.txt", "w", stdout);oss << "{0";for (ull i = 1; i <= 4000; ++i) {ull l = (i - 1) * 2500000 + 1;ull r = i * 2500000;for (ull d = 1; d * d <= r; ++d) {for (ull a = std::max((l + d - 1) / d, d); a * d <= r; ++a) {v[a * d - l + 1] = d;}}ull g = 0;for (ul j = 1; j <= 2500000; ++j) {g += v[j];}oss << ", " << g;}oss << "};\n";std::cout << oss.str();std::cerr << double(std::clock()) / double(CLOCKS_PER_SEC) << std::endl;return 0;}
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;ul T;ull n;ul m;const ul maxm = 1e5;ull k;ull p[maxm + 1];ull g[4001] = {0, 876804130, 1563212084, 2002063203, 2354317781, 2656733732, 2925711704, 3170453898, 3396438608, 3607003882, 3805141120, 3992850026, 4171496143, 4342381148, 4506248314, 4663920548, 4816343829, 4963323315, 5106068055, 5244637694, 5379239197, 5510576882, 5638406672, 5763277881, 5885273702, 6004611649, 6121491911, 6236207560, 6348621224, 6458737714, 6567208205, 6673519997, 6778204006, 6881218772, 6982516261, 7082317814, 7180625602, 7277588377, 7372946342, 7467494111, 7560199220, 7652003830, 7742655785, 7832126306, 7920669641, 8007834664, 8094421101, 8179564557, 8264105204, 8347670862, 8430063727, 8512607591, 8592814367, 8673268528, 8752693851, 8831052973, 8909346200, 8986432928, 9062139581, 9138686315, 9213456643, 9287955306, 9361822485, 9434993654, 9507766127, 9579922414, 9650840476, 9722096732, 9792157823, 9862088957, 9931335255, 9999822464, 10068888693, 10136703575, 10202919089, 10271306698, 10336034232, 10402976823, 10468266692, 10533777507, 10597973483, 10662291485, 10725848841, 10789479554, 10852326481, 10915329341, 10977449357, 11039240482, 11100750009, 11162211406, 11222963707, 11283689287, 11343155094, 11403034701, 11462439946, 11521637500, 11580021523, 11639525364, 11697108953, 11755025796, 11812054069, 11869984099, 11926764019, 11984012354, 12039309964, 12095872616, 12151449134, 12207504976, 12262438889, 12318022364, 12372214180, 12426738793, 12481607845, 12534981617, 12588495594, 12642140251, 12695627735, 12748804273, 12801426803, 12853967764, 12906904768, 12958401044, 13010399730, 13062369195, 13112953880, 13164978712, 13216035823, 13267163122, 13317504058, 13367618467, 13417354827, 13468217414, 13518786502, 13567121264, 13617318586, 13665894015, 13715376757, 13764105477, 13812896411, 13860763742, 13910515319, 13958249955, 14005439269, 14054325127, 14100931210, 14147539972, 14197979581, 14242601150, 14289597007, 14337520608, 14383449267, 14430039817, 14476485577, 14522991584, 14568458231, 14614795255, 14659517469, 14706141637, 14750126879, 14797080888, 14841887237, 14886334659, 14931103983, 14975142940, 15021324552, 15064103306, 15110281980, 15152098347, 15197342376, 15241013743, 15284700840, 15329274722, 15370786786, 15414962960, 15458593539, 15501261899, 15542719005, 15587220816, 15629458010, 15672940561, 15714102155, 15756967471, 15799110472, 15841048275, 15883225551, 15924394099, 15966678852, 16008827117, 16049378701, 16091379502, 16131818876, 16173654505, 16214723437, 16255570734, 16296890703, 16337300894, 16377384526, 16418238412, 16458588808, 16499611286, 16539040277, 16579621877, 16618868558, 16659513775, 16698367345, 16739836556, 16777551664, 16818523903, 16856171740, 16896655941, 16935450348, 16973926760, 17014863925, 17051920773, 17092384518, 17129753719, 17168290745, 17208303275, 17245980443, 17284773320, 17320932388, 17361343532, 17398646751, 17436965464, 17474181297, 17512963048, 17550433580, 17587120120, 17625299153, 17663103422, 17701555379, 17736819119, 17774535099, 17812743497, 17847494120, 17885631466, 17923526442, 17959117300, 17996933288, 18033429293, 18069162914, 18106744186, 18142307432, 18179131590, 18215555985, 18250085650, 18288755945, 18323655912, 18358385950, 18397032412, 18431596024, 18465914273, 18502820743, 18538133557, 18574490067, 18608755338, 18645332793, 18680523358, 18714645230, 18749891803, 18785427920, 18819893925, 18855125367, 18891909782, 18926068981, 18959653489, 18993376107, 19028925753, 19064370720, 19099473483, 19131660921, 19166008548, 19201570859, 19236959169, 19269896699, 19303172154, 19338384692, 19370492076, 19407043575, 19439538914, 19473431659, 19507026966, 19540294861, 19575055800, 19607580531, 19641703994, 19675088394, 19708176270, 19740924676, 19774026186, 19808666377, 19842408610, 19874663879, 19906447074, 19940041276, 19972174554, 20005465227, 20040137295, 20071395347, 20103304032, 20136827907, 20169403231, 20202168502, 20232047232, 20268619392, 20298403141, 20330431037, 20363017913, 20394211228, 20427939964, 20457925374, 20493935294, 20522793432, 20555425974, 20586816285, 20618911006, 20650570701, 20682593322, 20713708152, 20746648865, 20775879284, 20809502533, 20839364151, 20870923968, 20902958983, 20934489584, 20964709028, 20997484942, 21028071818, 21058446668, 21088472986, 21122623551, 21150996079, 21183130066, 21212387768, 21244529323, 21276150752, 21303977911, 21336279988, 21366910986, 21397391902, 21430572980, 21456663577, 21489070769, 21519737838, 21549267191, 21579950890, 21609840501, 21642490194, 21668573324, 21700017704, 21732198579, 21759689907, 21792387046, 21818552197, 21852590357, 21879270994, 21911459419, 21939671713, 21969723732, 21999797249, 22028669322, 22059384243, 22087213300, 22117434195, 22147016089, 22176092793, 22206438999, 22234685237, 22264105432, 22293710400, 22322855915, 22351215681, 22382636284, 22411453494, 22439430853, 22467533229, 22497418963, 22526590617, 22556399019, 22583529510, 22612789761, 22643316737, 22670053877, 22698780712, 22727569582, 22758413414, 22783540335, 22814725504, 22840178391, 22873248800, 22899340125, 22928136916, 22953543724, 22985919157, 23012228753, 23040379259, 23070217897, 23097434233, 23126446079, 23153449338, 23180090453, 23210312516, 23237358978, 23266943874, 23293948361, 23321546433, 23349116448, 23377177364, 23405472690, 23433662726, 23459474430, 23487940568, 23515271066, 23545102968, 23570434254, 23598572447, 23625525791, 23655594812, 23682428660, 23707311519, 23735279232, 23763991315, 23790511341, 23817547772, 23845194790, 23872749450, 23900330625, 23926355034, 23954227133, 23981637439, 24007970423, 24033099999, 24063508976, 24088356288, 24115621450, 24144481135, 24168490030, 24197007268, 24223067229, 24249528767, 24278046976, 24302620066, 24330270407, 24358313609, 24382043079, 24410191188, 24437304928, 24460845608, 24489674148, 24517248973, 24544261037, 24567752208, 24594197332, 24623039101, 24647786448, 24674283142, 24699885203, 24726908162, 24754528754, 24777857418, 24806020082, 24829921381, 24859230378, 24881546849, 24909160385, 24936861221, 24961018703, 24987138565, 25012536193, 25039573699, 25065655984, 25090859156, 25116956494, 25141113236, 25167200513, 25194925559, 25219584303, 25246030747, 25269461711, 25296649666, 25322816536, 25346500113, 25372766904, 25399771261, 25422193505, 25450232342, 25475682720, 25500098387, 25524796651, 25552291090, 25573965879, 25602609529, 25626335596, 25653188707, 25676577175, 25702153450, 25727671818, 25753950870, 25776447864, 25803629010, 25825876236, 25852807509, 25877889248, 25903963287, 25926657509, 25952004432, 25979271239, 26002468852, 26026582654, 26052337042, 26075863322, 26103853116, 26123593382, 26152704203, 26174412260, 26200445065, 26226338287, 26248172131, 26274106632, 26299100989, 26322791027, 26347553468, 26372000325, 26396630980, 26423412461, 26443943609, 26469081633, 26493779604, 26520312195, 26542368288, 26567390292, 26591148589, 26615492376, 26640383006, 26663807647, 26688313210, 26713806890, 26735483901, 26761720757, 26783725134, 26808301307, 26833863251, 26857591854, 26880311449, 26906895236, 26930149817, 26950946087, 26977259036, 26998560392, 27025714735, 27049885920, 27069510308, 27096453872, 27119235417, 27141728971, 27168543157, 27192319076, 27213512828, 27239304959, 27262401969, 27286541811, 27307921141, 27334296367, 27354042110, 27378620886, 27404715197, 27425212865, 27452988845, 27474162407, 27496920095, 27520671916, 27542454807, 27568867996, 27591048820, 27613562770, 27637802449, 27660816204, 27682479758, 27709778608, 27729824013, 27753228187, 27778283343, 27798413915, 27822370967, 27847780316, 27868525590, 27892846216, 27916505000, 27937943532, 27960598880, 27984371190, 28007382693, 28031372478, 28053084507, 28077511190, 28100249538, 28121111707, 28144850624, 28168110833, 28191425439, 28213498128, 28236914697, 28258933769, 28283996229, 28303228342, 28325103826, 28351662345, 28370907208, 28396548174, 28418655320, 28441089216, 28460374760, 28485629867, 28509009781, 28529294785, 28554706895, 28576659618, 28596115797, 28623249230, 28641294246, 28665341804, 28690120518, 28710907668, 28730389978, 28753769056, 28777489356, 28798795532, 28824345104, 28844811537, 28865918937, 28889047880, 28910908001, 28932190628, 28955663267, 28979224737, 28997612630, 29021790743, 29043565874, 29066194545, 29091133154, 29108623004, 29133386356, 29152393464, 29175703300, 29196997854, 29222083463, 29241220717, 29262963568, 29287189463, 29309712783, 29326913081, 29351594343, 29375673653, 29393645784, 29417112881, 29440773212, 29460124460, 29482610224, 29503266305, 29525246499, 29549437000, 29569840901, 29588605752, 29614427377, 29634497509, 29656358324, 29677972436, 29699355990, 29719557007, 29741333413, 29762832362, 29787518050, 29807097100, 29826124116, 29852827009, 29870511883, 29891479995, 29914432989, 29934104078, 29956023742, 29981978406, 30001166432, 30017856984, 30042947862, 30063537983, 30082745579, 30109550646, 30127830696, 30151016369, 30170049341, 30188383050, 30212674335, 30235416145, 30254005360, 30275693353, 30300736441, 30314434110, 30338930475, 30361638909, 30384230419, 30401308258, 30422973535, 30445945275, 30466189745, 30488343179, 30505158453, 30529861318, 30550244286, 30570210714, 30592038376, 30612710633, 30634466757, 30653749326, 30675135565, 30694428262, 30717707615, 30739347598, 30758198787, 30780286787, 30801227412, 30818325229, 30842253480, 30862562674, 30882606224, 30905951397, 30921807336, 30946258107, 30966675713, 30982755181, 31009255924, 31027723739, 31047716589, 31067153033, 31092586596, 31107411601, 31134136798, 31146898089, 31173704104, 31191121558, 31213492850, 31233454825, 31252312750, 31274387870, 31291732677, 31318961219, 31332711560, 31357141819, 31375193672, 31397687913, 31419228862, 31436242072, 31455825041, 31478976012, 31495647531, 31519501812, 31539532020, 31557208049, 31580939853, 31599197528, 31618223362, 31640934390, 31658130716, 31679214698, 31699760382, 31721935731, 31736324154, 31763834743, 31780911682, 31798637848, 31819537498, 31841082148, 31862567660, 31882289147, 31899379987, 31921769328, 31943761880, 31959372466, 31979340103, 32000794336, 32022580785, 32039330115, 32059884772, 32079465128, 32105097652, 32119114133, 32138028430, 32161603798, 32178024243, 32200388542, 32219331269, 32239568493, 32258306192, 32281330722, 32296782196, 32319153217, 32337298900, 32357023210, 32378518768, 32396636360, 32418486036, 32433648574, 32456748873, 32476746778, 32497119715, 32514691919, 32533870704, 32555626619, 32574499716, 32592253659, 32615637268, 32627904404, 32654732610, 32670475152, 32692327229, 32709815509, 32731414409, 32750081820, 32766089242, 32787951710, 32809785657, 32828328938, 32845838610, 32867034386, 32884761928, 32906124705, 32923606732, 32942948280, 32965578522, 32980494478, 33003620003, 33017387170, 33038859989, 33061069683, 33080663519, 33096626980, 33119198843, 33135750195, 33158881100, 33174477926, 33191885645, 33213249531, 33229817878, 33256594741, 33269555643, 33288034360, 33309904159, 33327817652, 33347208484, 33368072772, 33385282812, 33403187242, 33424715702, 33443838700, 33461702851, 33480467072, 33497224216, 33520647853, 33536425600, 33558029325, 33576600980, 33593724444, 33615621188, 33630790192, 33650026089, 33672036133, 33688925400, 33708056080, 33726977790, 33746296540, 33763256436, 33780977863, 33806148321, 33818525553, 33839606667, 33860172953, 33877693796, 33896077538, 33914295415, 33937308623, 33951859662, 33971471988, 33990804218, 34009856394, 34026528468, 34047369916, 34063947217, 34081324793, 34103300592, 34122505191, 34138396955, 34159237299, 34172310268, 34196295415, 34212952224, 34232957693, 34251518224, 34269667098, 34288144112, 34307456206, 34323566579, 34346919371, 34363211500, 34381404111, 34395641438, 34418021668, 34435719132, 34456288149, 34474855471, 34488640294, 34512833004, 34526740021, 34548242474, 34565512063, 34581440685, 34604395350, 34617571178, 34640866087, 34656910809, 34674785909, 34691980863, 34712781352, 34729024164, 34751445424, 34763045716, 34787488776, 34803096271, 34820973099, 34838947916, 34857021984, 34877338899, 34897652347, 34912142598, 34932992304, 34947572338, 34964707101, 34987664365, 35003060484, 35021240315, 35041782579, 35055924687, 35077674814, 35093205497, 35113275634, 35131266832, 35147523885, 35167546187, 35180265000, 35205862981, 35218625601, 35237635968, 35253509795, 35279557446, 35292159332, 35307028618, 35334091407, 35345675742, 35364176886, 35380782228, 35402422557, 35415745734, 35438422301, 35454570810, 35470636591, 35490094047, 35508231797, 35521501895, 35547885258, 35561548162, 35577989065, 35595485032, 35617457897, 35632439427, 35652964320, 35666248781, 35686845812, 35702828944, 35723412576, 35737874917, 35757305416, 35774182994, 35795187454, 35807406934, 35830945712, 35845895303, 35862965277, 35879635173, 35902821717, 35914943533, 35931882868, 35951727309, 35971543673, 35985701810, 36006720122, 36021926020, 36041546532, 36055927096, 36075636160, 36088731268, 36114997597, 36130362916, 36142230781, 36161296774, 36182199814, 36197426642, 36210177993, 36238347185, 36248362452, 36269642045, 36283985401, 36300926460, 36324087050, 36334858816, 36355228428, 36373130947, 36391626220, 36405910511, 36424097381, 36445383067, 36458701369, 36476695829, 36495263633, 36510015189, 36530533329, 36547896696, 36561190498, 36582392941, 36598755633, 36616144983, 36632817446, 36650848448, 36665948326, 36683066669, 36701381520, 36721840999, 36732744740, 36756585157, 36773512445, 36786741455, 36805125400, 36822389034, 36840209892, 36856967908, 36873520592, 36890995627, 36909320300, 36926937289, 36946779580, 36956905568, 36977379154, 36996504150, 37011460271, 37029577296, 37044028384, 37060615576, 37079063875, 37098372292, 37113333354, 37131641082, 37149010640, 37163489696, 37182175936, 37200010095, 37216899278, 37231953121, 37249139570, 37267259121, 37282591026, 37304468305, 37316942330, 37332434312, 37356661131, 37365506139, 37383502150, 37406266679, 37420425633, 37435710751, 37452520104, 37471902916, 37485431915, 37505991943, 37520174861, 37535980969, 37556667350, 37571659861, 37587217192, 37605139697, 37621945442, 37636302481, 37658505104, 37673375814, 37686707256, 37707643960, 37719680133, 37740954012, 37755200654, 37772974770, 37787094232, 37807159791, 37822672255, 37840295782, 37863959924, 37870453357, 37889993023, 37900263223, 37927308628, 37942603226, 37959061324, 37967133804, 37994420874, 38002405702, 38026470312, 38037647967, 38057184947, 38074010544, 38090173145, 38104545572, 38124927599, 38134864643, 38159738749, 38175567966, 38190093661, 38202238933, 38223444692, 38238268131, 38254662224, 38275129143, 38287803476, 38300949871, 38320687953, 38339239714, 38352885586, 38372781919, 38386571036, 38401519359, 38425001126, 38433805232, 38451403654, 38469400554, 38488997641, 38497996300, 38521841903, 38535763115, 38549562702, 38566922520, 38585841371, 38597825343, 38617238641, 38635344482, 38648539839, 38667362672, 38680667091, 38701130986, 38715491000, 38733406515, 38742915602, 38764823150, 38780827252, 38798424449, 38810007582, 38828615697, 38847915769, 38864164231, 38874239697, 38895893324, 38908924296, 38927122423, 38940938095, 38955531280, 38977700633, 38992302403, 39006702828, 39023153377, 39035982104, 39061263950, 39074472278, 39087941704, 39100994477, 39118749930, 39137882333, 39158770698, 39167872291, 39182930225, 39199224197, 39222835745, 39230318013, 39248339753, 39265112936, 39283256917, 39297887371, 39312974438, 39331458183, 39343942882, 39362023459, 39380716770, 39393987731, 39407632998, 39423438211, 39442732145, 39456850752, 39477007571, 39488984725, 39505365475, 39522464663, 39540167666, 39554980979, 39566149293, 39588328812, 39600983301, 39615113044, 39634546836, 39647868266, 39662263786, 39683330912, 39696074238, 39715675382, 39726631932, 39743905463, 39762791551, 39776325756, 39791696699, 39807831864, 39826712362, 39832818068, 39857243374, 39870126651, 39889234795, 39901333227, 39920673646, 39932503757, 39952590626, 39964318536, 39979838908, 40003811798, 40009405519, 40030904676, 40040545086, 40063014911, 40077719778, 40087388718, 40108678723, 40125256580, 40138430897, 40157539896, 40169991162, 40187570156, 40203338837, 40212673651, 40232710848, 40248843984, 40263833678, 40282522664, 40293695314, 40312026031, 40327249843, 40344918738, 40355582507, 40377210894, 40390685701, 40405203350, 40417345013, 40440303123, 40449294450, 40467787207, 40487690524, 40495883827, 40512560775, 40529202388, 40540934282, 40563183416, 40577250330, 40590395121, 40606484613, 40625213243, 40636092978, 40654719517, 40669996316, 40685331003, 40702044782, 40716682341, 40729508947, 40747104342, 40760760035, 40780950603, 40791365470, 40810257052, 40823734905, 40836170729, 40856326873, 40865580910, 40885608268, 40902167479, 40917115429, 40929500652, 40948163496, 40962485520, 40977052331, 40995759620, 41007508568, 41024804551, 41038884650, 41057937906, 41067135467, 41083893403, 41099217570, 41113509055, 41137080727, 41142301607, 41163152143, 41179801636, 41189533527, 41213316744, 41218871725, 41239467454, 41252011021, 41269455946, 41285349461, 41298765814, 41314136612, 41327957516, 41344236157, 41359289673, 41380018773, 41392548047, 41402545988, 41417220566, 41435429436, 41450237127, 41470791937, 41480620716, 41496749879, 41513608686, 41530006263, 41538287371, 41555619241, 41569747097, 41586820042, 41603870315, 41616163358, 41635534600, 41647112127, 41661924818, 41681755299, 41691797696, 41705317549, 41727771022, 41739577316, 41749466397, 41768530695, 41786200907, 41800330966, 41812344818, 41826988684, 41842801622, 41859010213, 41871587494, 41891807737, 41902290447, 41919611435, 41936193752, 41945757677, 41972634742, 41971897405, 41995044934, 42006758925, 42025413721, 42036302695, 42052576517, 42069795532, 42086230441, 42098905278, 42110702892, 42128121715, 42142303876, 42161181919, 42172367385, 42187385061, 42202051477, 42221761603, 42229917902, 42249661183, 42263087622, 42272533881, 42294526160, 42306310833, 42326235981, 42331657129, 42350736397, 42366290428, 42383919431, 42389979730, 42411424627, 42434273394, 42439001881, 42454023568, 42467652425, 42483494915, 42507586260, 42508382077, 42531924051, 42541129984, 42558455790, 42574831237, 42588957697, 42600953621, 42619572452, 42629991055, 42647287950, 42662489085, 42677921856, 42689708000, 42705686337, 42724200416, 42732803082, 42750061913, 42770234643, 42774000213, 42795669727, 42805901285, 42825405437, 42840454713, 42846414184, 42872383529, 42883365916, 42896743724, 42906222937, 42927300463, 42941684415, 42959301252, 42965550668, 42982586684, 43000774622, 43016227565, 43029815300, 43047141694, 43051696629, 43070128754, 43090104325, 43102939495, 43115239661, 43136107349, 43137707716, 43162658554, 43175935072, 43183926177, 43207004517, 43212165592, 43233850312, 43246918127, 43262215160, 43277747055, 43287492293, 43306064525, 43314528106, 43337155590, 43346446777, 43369371057, 43372157965, 43385050046, 43413768616, 43417521161, 43439605600, 43449805581, 43461977420, 43474751233, 43494158904, 43503952261, 43524615132, 43538158894, 43548070641, 43561524960, 43580829989, 43598006400, 43605235400, 43619784571, 43637585617, 43649448215, 43669419269, 43680918924, 43693254261, 43710414488, 43724538083, 43735739327, 43750401317, 43765166724, 43782546084, 43794117295, 43810309240, 43821165952, 43836350037, 43851898043, 43864823018, 43879734557, 43894419465, 43910265156, 43925339795, 43941270914, 43950327045, 43961936223, 43985979951, 43999012772, 44007772045, 44024599868, 44028906102, 44057615173, 44063882630, 44079970870, 44096074229, 44104797115, 44124869057, 44137800009, 44152372697, 44163793437, 44187525700, 44190129262, 44205418240, 44225146821, 44233242963, 44250455444, 44264088841, 44279238121, 44290114012, 44309229299, 44319379142, 44338606745, 44347357035, 44364589077, 44380383107, 44390659888, 44405576186, 44421895986, 44429549418, 44444063460, 44466892590, 44481018244, 44490841835, 44504508401, 44516056617, 44535716335, 44542290461, 44560125004, 44578366866, 44591153722, 44599313451, 44620813016, 44633948052, 44644009548, 44657257179, 44672122847, 44690294994, 44702120244, 44719648397, 44724061727, 44743435737, 44762509373, 44767751704, 44785896555, 44797727772, 44814700399, 44831333928, 44839114982, 44849010783, 44871688002, 44886454522, 44892559830, 44915706013, 44918930064, 44941518074, 44958843407, 44966219538, 44979135602, 44994159991, 45008857679, 45021575530, 45036614689, 45053307932, 45063389892, 45078631258, 45091064824, 45107882458, 45122538519, 45132656307, 45148191392, 45162445321, 45169042565, 45191478985, 45203803442, 45217370230, 45226683960, 45247241721, 45259552378, 45273433922, 45285188357, 45305337244, 45312847218, 45326529486, 45339866311, 45358568465, 45366901283, 45381996251, 45400699034, 45406763681, 45425930466, 45442231293, 45449470051, 45463218173, 45477918605, 45497608644, 45503183048, 45520580439, 45533575690, 45550734621, 45558109335, 45574817948, 45589720423, 45604772496, 45618861193, 45631178657, 45643167781, 45653364302, 45675059334, 45684017600, 45697192232, 45710076761, 45727322676, 45741717641, 45758017510, 45763067808, 45783425295, 45796794432, 45803784748, 45822732553, 45832988694, 45850441021, 45870021761, 45877039775, 45888971252, 45903823613, 45916461149, 45929859851, 45948005383, 45956336424, 45969326451, 45990859146, 45997900082, 46013612193, 46023597415, 46039074822, 46054737458, 46070949465, 46078898723, 46090259997, 46114409678, 46121600410, 46132348174, 46146459534, 46166600765, 46175275186, 46188213024, 46204944074, 46217195602, 46228077567, 46239303067, 46259610888, 46268686774, 46284960007, 46293467068, 46317341835, 46321491194, 46338180302, 46352684291, 46367275333, 46380920583, 46389909542, 46399921823, 46420038699, 46435654852, 46449617506, 46455549452, 46471625049, 46486220602, 46495818849, 46515547842, 46527395338, 46538999149, 46553134548, 46570476646, 46577360634, 46596873003, 46610516785, 46614505847, 46635326992, 46644547239, 46663402313, 46673495539, 46690278880, 46696353379, 46714439619, 46728577399, 46742840867, 46758915073, 46761674919, 46780624498, 46800611762, 46802900743, 46819011395, 46836558708, 46846719186, 46866890511, 46866791004, 46887102951, 46901928693, 46910833612, 46927850888, 46947754035, 46955294544, 46966627733, 46979315457, 46997282775, 47006424047, 47024268455, 47028331605, 47047949198, 47063489690, 47072358127, 47085578553, 47105390754, 47107210723, 47127179159, 47143010476, 47156415566, 47167717718, 47177572777, 47194432588, 47204320334, 47224138794, 47230557584, 47245190277, 47258997887, 47274770284, 47287965501, 47301533483, 47304747233, 47327167736, 47339462729, 47345245317, 47372110591, 47380790137, 47388395511, 47406350046, 47416491241, 47430057631, 47446183498, 47457037138, 47469427941, 47484214775, 47494961886, 47510986621, 47522564723, 47533037996, 47550036371, 47559329084, 47580586199, 47588090207, 47604136540, 47617208724, 47628525743, 47638467502, 47655071769, 47664136198, 47682996063, 47689930907, 47709899887, 47718010123, 47733842328, 47745852818, 47758554964, 47775869455, 47782060241, 47797811911, 47812662253, 47821635697, 47837306048, 47846178191, 47865887922, 47876502143, 47893696983, 47898741916, 47918043086, 47922649449, 47947873068, 47950143797, 47971054815, 47974107271, 47993543670, 48004926797, 48023195078, 48035498886, 48042026187, 48058555716, 48071323751, 48091937249, 48096100535, 48109858670, 48126470976, 48136169291, 48146486615, 48160345074, 48172809636, 48187478152, 48205322258, 48210201298, 48223033430, 48240238548, 48259557952, 48263816206, 48282757592, 48285388513, 48305321231, 48320467920, 48332312548, 48340854444, 48351937073, 48373488385, 48385387083, 48392344988, 48405384071, 48422466002, 48431560559, 48450539134, 48459123439, 48471956665, 48480312353, 48500619623, 48511006650, 48526306842, 48532733055, 48553326737, 48556522749, 48576798004, 48585322835, 48602954954, 48613963328, 48622699198, 48642132271, 48654796405, 48664229754, 48674515702, 48691621033, 48699755980, 48720074181, 48726452961, 48742103063, 48756326766, 48762884094, 48780890612, 48793043292, 48805663366, 48819578459, 48831250267, 48840697478, 48858402328, 48870429209, 48874835455, 48895394244, 48918897541, 48916507083, 48930300260, 48949938775, 48957913630, 48966445246, 48984734389, 48998564187, 49008293463, 49021024629, 49034749814, 49042216679, 49064479732, 49074035303, 49084862199, 49097653883, 49109124533, 49127196818, 49138849623, 49140879759, 49164246832, 49175543069, 49185217652, 49206492986, 49211337127, 49220243912, 49238815286, 49251328868, 49259477114, 49276804447, 49293168378, 49302015566, 49311658976, 49323700027, 49337229714, 49352124440, 49367154747, 49371967524, 49395204465, 49402704096, 49411035037, 49429676961, 49444239857, 49443160870, 49466286681, 49485116922, 49484666622, 49505335738, 49512812709, 49528933564, 49544699558, 49552266532, 49562767981, 49582621845, 49589231006, 49601328071, 49621170418, 49625526312, 49639273204, 49653974351, 49661472221, 49690614346, 49689415446, 49701438386, 49711857307, 49730206230, 49742058378, 49747178263, 49770397291, 49775530155, 49790164667, 49810093877, 49819742923, 49827255941, 49836074032, 49857394670, 49861113839, 49887704144, 49887945621, 49899948410, 49914284122, 49939727509, 49935502403, 49956946432, 49960086794, 49981119065, 49995749105, 50004120931, 50008417911, 50035528509, 50037593181, 50048351420, 50072891035, 50075316039, 50093974026, 50101390386, 50112648709, 50132095772, 50141008679, 50148137965, 50166150956, 50180119826, 50189121027, 50203210339, 50210998723, 50225266276, 50242551067, 50248957637, 50265776781, 50277931787, 50288847308, 50305526098, 50312550688, 50328250844, 50337155599, 50345257220, 50360891466, 50379713879, 50387728181, 50400168534, 50411988062, 50427875136, 50437664391, 50447882327, 50463376531, 50478747898, 50483285752, 50498624534, 50508311398, 50527213894, 50537692361, 50543953345, 50567333171, 50568601679, 50583803703, 50601351199, 50610527085, 50618840889, 50626935844, 50652727694, 50660596502, 50672134367, 50684791197, 50693196576, 50711849013, 50720759592, 50734476920, 50748616691, 50755191409, 50764344160, 50784354798, 50787047929, 50809500751, 50820717090, 50821735104, 50846620863, 50855137366, 50874370318, 50874870658, 50890050704, 50907265670, 50912670776, 50932594505, 50938038205, 50949920740, 50966252832, 50971545894, 50993503677, 51007548175, 51017203036, 51022737497, 51038944621, 51050768515, 51064056573, 51073911194, 51083703500, 51103923361, 51112716853, 51121545953, 51133748952, 51149240118, 51160991667, 51167857439, 51185376708, 51201083384, 51203041274, 51224712067, 51234703805, 51240787193, 51254706037, 51269774174, 51278550379, 51297210914, 51303147965, 51317682008, 51337177682, 51338994232, 51352013810, 51375321093, 51370622357, 51387269948, 51404964433, 51413955565, 51426392556, 51435599869, 51447727187, 51468972416, 51475711741, 51484867831, 51497896378, 51512419668, 51521838873, 51544997316, 51543980870, 51556140527, 51574384486, 51583616785, 51596842565, 51610933282, 51610853560, 51631644410, 51646713673, 51653807232, 51670882884, 51675989113, 51695250100, 51701773675, 51715259349, 51736291159, 51737141776, 51753432135, 51758728352, 51776592058, 51789143264, 51802823079, 51816790673, 51824505768, 51831853936, 51847009197, 51861127892, 51867797089, 51885638547, 51900977262, 51901330122, 51921418834, 51932140212, 51947843645, 51949021792, 51961747550, 51984703172, 51988680213, 52004947038, 52011727645, 52034120046, 52040922761, 52048665650, 52066442417, 52075339675, 52089103899, 52097835766, 52107218308, 52124703057, 52130780468, 52149168179, 52167356837, 52163007016, 52180726482, 52196049617, 52208522272, 52218309433, 52229702030, 52238295063, 52257768211, 52264602677, 52271708427, 52286828636, 52304030247, 52317032335, 52322650829, 52338175812, 52347033888, 52362886052, 52376696526, 52382255704, 52398486194, 52405384911, 52422570199, 52425474938, 52448054461, 52457998729, 52470788498, 52477247906, 52486493803, 52501440807, 52522626925, 52521036883, 52538344781, 52551256074, 52556027828, 52574850320, 52587219068, 52599744091, 52606551914, 52619597066, 52633845601, 52647723998, 52654296160, 52666752127, 52681673637, 52688814259, 52707259967, 52714868607, 52725494085, 52737880081, 52757192336, 52764746750, 52770013356, 52788090966, 52794467993, 52809569478, 52820347849, 52835136497, 52841355109, 52859510179, 52863590166, 52883910871, 52890497621, 52907198582, 52913268470, 52925433326, 52945557834, 52938971041, 52962021495, 52978441239, 52981381026, 53006261417, 53006481734, 53028983006, 53022928836, 53043201957, 53057646618, 53073627479, 53075006056, 53084307543, 53109514079, 53109236127, 53127832560, 53139509976, 53144076351, 53167709196, 53168822375, 53181960624, 53199093498, 53209279404, 53218496451, 53230078889, 53241473881, 53249521641, 53270885887, 53272696442, 53291803495, 53300681075, 53318050834, 53317544561, 53330960574, 53349387426, 53358108628, 53371243180, 53384886705, 53391275876, 53404514129, 53415792183, 53434786905, 53440194232, 53452565832, 53464652192, 53475504457, 53486342184, 53496642435, 53508524573, 53521826495, 53536707268, 53543230000, 53551021733, 53573056299, 53580772992, 53595539017, 53596477072, 53615365662, 53623008647, 53638174261, 53654007714, 53652617304, 53671392929, 53683974659, 53702474787, 53706021707, 53710422877, 53737297426, 53741748916, 53751369952, 53759542244, 53781390088, 53786162727, 53806143035, 53799658944, 53821810124, 53834459268, 53843556041, 53858926816, 53869220535, 53878138329, 53892385180, 53900734004, 53913857437, 53922293707, 53944910237, 53947108684, 53957922515, 53973433553, 53979150689, 53994250338, 54009823996, 54016192550, 54028938221, 54038288845, 54052040462, 54058011788, 54079716033, 54080596429, 54096482134, 54114956876, 54121970070, 54127991934, 54148037548, 54152697596, 54170505583, 54176795789, 54191353325, 54194353149, 54217844521, 54225253205, 54229850545, 54250656968, 54258612141, 54267150688, 54275232442, 54296322450, 54299497872, 54321398747, 54324025918, 54341532560, 54342831153, 54358724761, 54379093374, 54376332567, 54397553041, 54409251465, 54417751374, 54432512721, 54434490607, 54459356700, 54465977431, 54472681377, 54483167530, 54494194920, 54512733621, 54519006039, 54531637494, 54543948759, 54554683885, 54554165716, 54588738197, 54583495297, 54599396427, 54617372614, 54615990449, 54634208459, 54644326433, 54655976969, 54668012932, 54674758406, 54698063110, 54700146875, 54712560954, 54724522062, 54737982724, 54750652970, 54751828428, 54768338925, 54782365021, 54793698681, 54802449327, 54811380927, 54834709110, 54835477463, 54845776047, 54866542521, 54867857902, 54880154713, 54901165908, 54897510430, 54913319144, 54937171358, 54939575659, 54948691430, 54955993271, 54973220270, 54987674756, 54996411154, 55010098140, 55016689744, 55028058815, 55038150570, 55052206959, 55060793600, 55075709850, 55090654967, 55091374453, 55111844194, 55112590104, 55137391826, 55138579275, 55150611990, 55165630589, 55175802891, 55179590636, 55203482187, 55209817424, 55215934980, 55227524359, 55246613207, 55257996088, 55260698180, 55277959723, 55287456830, 55298370736, 55307032803, 55319184006, 55335440799, 55350355447, 55349616917, 55365493407, 55374624770, 55390872244, 55403011011, 55407734426, 55415756888, 55439130453, 55445422912, 55453206407, 55466406860, 55477116176, 55490422386, 55494537888, 55518562196, 55518317837, 55529049210, 55545538201, 55560945091, 55570071078, 55577383648, 55579808731, 55602214751, 55615065566, 55625285145, 55626495472, 55648419964, 55647850004, 55669173262, 55677464284, 55693302373, 55702486411, 55710359963, 55723505703, 55730915272, 55744916710, 55759760345, 55768235243, 55773531594, 55784546990, 55802962346, 55808430169, 55824964950, 55841018216, 55834590976, 55857853504, 55865371107, 55874975169, 55890664903, 55899360368, 55909328183, 55924603778, 55933767952, 55937376964, 55961838070, 55967865090, 55973882983, 55986561988, 55996731030, 56014474555, 56025994717, 56029839888, 56043825780, 56057459892, 56067389878, 56064898992, 56092432206, 56096659492, 56118753190, 56115344868, 56138256490, 56135209159, 56150832030, 56163585188, 56182916357, 56187893049, 56194212395, 56215127123, 56213782313, 56232332188, 56245187874, 56256839621, 56264587164, 56267934644, 56292609484, 56293922098, 56313032395, 56315478192, 56330685465, 56344386437, 56345711803, 56365187698, 56371884162, 56381151594, 56395293527, 56408814434, 56421613160, 56429596325, 56437820445, 56452699620, 56461810808, 56467066303, 56484042419, 56496007718, 56502475716, 56521298542, 56523536998, 56540528918, 56549217969, 56560037045, 56577200009, 56573202294, 56593211770, 56608655651, 56612396465, 56626330939, 56643547085, 56640050308, 56655625256, 56676666935, 56677529127, 56695513172, 56701691051, 56717686809, 56716314735, 56739269091, 56739460314, 56756662398, 56763887654, 56775935317, 56791850613, 56803169127, 56809164838, 56817756946, 56835561722, 56849276787, 56853443232, 56865517893, 56872642906, 56883447507, 56904364642, 56911994335, 56912684155, 56935748645, 56941636464, 56957599944, 56955273507, 56973972713, 56981758167, 56999134187, 57007385500, 57018991995, 57024224398, 57040160675, 57044695029, 57065090341, 57080017303, 57076199786, 57088661992, 57112444713, 57111187853, 57122847675, 57130885690, 57159686533, 57152099556, 57168440020, 57185621419, 57190729965, 57197818691, 57217305188, 57219471371, 57231753019, 57235903310, 57258507938, 57269444765, 57277794070, 57291307057, 57294312439, 57310948685, 57325982285, 57327290404, 57339242778, 57352495529, 57365904848, 57369196420, 57387084179, 57392139643, 57411822488, 57419896086, 57429522328, 57435301077, 57445657476, 57463839121, 57474196276, 57480768946, 57491206931, 57503991483, 57509200362, 57523352954, 57535068075, 57552168598, 57557257154, 57561221239, 57578139511, 57585909598, 57602217547, 57614918700, 57619202647, 57628504143, 57641880335, 57659649972, 57659574905, 57679638472, 57682058851, 57690651404, 57708483785, 57728137918, 57724246154, 57740678224, 57746500575, 57764732334, 57770351333, 57788383449, 57787087432, 57795913958, 57815039372, 57825601281, 57834079811, 57849440542, 57851501810, 57874971755, 57875790618, 57886618427, 57906901263, 57901085176, 57916686618, 57933537627, 57950827113, 57955391457, 57955183783, 57986338004, 57980073403, 57989340886, 58002856398, 58022640890, 58026011904, 58032166355, 58055632528, 58060042500, 58066681000, 58085196339, 58087719852, 58101462080, 58111806588, 58125015688, 58140091003, 58141479909, 58155575396, 58163322452, 58168994381, 58193042849, 58193777134, 58208901117, 58226993344, 58220584656, 58242841294, 58252504738, 58265226887, 58261613004, 58288224593, 58288150278, 58309900755, 58307082562, 58321295413, 58335371036, 58343950124, 58357419474, 58363304878, 58386033587, 58387195631, 58399338557, 58405160391, 58415623541, 58428245793, 58444848782, 58449160746, 58466554403, 58468274945, 58490019798, 58487283578, 58505974023, 58515938528, 58530724199, 58537966702, 58546196954, 58551289034, 58577632620, 58563158906, 58589498336, 58602977543, 58609828635, 58620737951, 58636826224, 58633123820, 58650118776, 58668230053, 58669508230, 58683948462, 58688619759, 58704528861, 58711861872, 58722321458, 58747476883, 58751669885, 58756044574, 58766881181, 58780893948, 58785984685, 58805023844, 58802457242, 58821358455, 58827658543, 58832854325, 58853366546, 58862088367, 58877587590, 58886182535, 58886243425, 58902168056, 58918217632, 58929485143, 58930997605, 58949361143, 58953675521, 58964540656, 58981674863, 58987855172, 58995698299, 59009547594, 59016671333, 59032560318, 59037986443, 59058276825, 59057476425, 59070374040, 59078005679, 59095079847, 59101580300, 59105660152, 59128922927, 59136413239, 59140870745, 59152197677, 59167227720, 59180444136, 59183295589, 59203517992, 59208845847, 59213746972, 59228808603, 59240862014, 59247164295, 59264318214, 59268746282, 59273241361, 59288778769, 59297401244, 59310407381, 59323809877, 59332961306, 59342412777, 59354592164, 59364838521, 59371204712, 59382256339, 59399608759, 59397345289, 59419562162, 59430506940, 59434635435, 59449009186, 59447161083, 59472794408, 59475704468, 59482080519, 59496624669, 59512767659, 59525488350, 59529770993, 59534040686, 59551670733, 59563888558, 59567573122, 59582123905, 59593000638, 59601571149, 59609100674, 59626650573, 59622794995, 59649712151, 59645089956, 59665362268, 59673789080, 59682295403, 59701323361, 59706862883, 59712385950, 59728110027, 59733588176, 59742005611, 59763475312, 59772991025, 59778036704, 59780201666, 59794323823, 59808195027, 59817258152, 59833915298, 59840674300, 59849633875, 59862232222, 59867890962, 59875284566, 59896354471, 59904335408, 59910704098, 59911588831, 59944951498, 59928844509, 59958961184, 59961671950, 59966033666, 59986069582, 59994944298, 60008911742, 60006354403, 60022525995, 60037292078, 60052788075, 60048942271, 60075109573, 60067254669, 60092791510, 60085104676, 60109400262, 60118259014, 60124981967, 60138624772, 60146595624, 60162676245, 60172228478, 60182333960, 60183305473, 60196224027, 60208484659, 60221669466, 60226906386, 60242941780, 60249566845, 60258661583, 60268127138, 60283519728, 60294955673, 60302536234, 60310120429, 60323807088, 60322443100, 60346337403, 60357332358, 60362050302, 60374044467, 60382683134, 60388805917, 60407678422, 60413973743, 60418380307, 60434704101, 60442099986, 60455743189, 60461322398, 60477535376, 60491808953, 60493953371, 60499494712, 60520317268, 60521936184, 60530042745, 60550090721, 60551173476, 60568749816, 60578548256, 60590693060, 60589909222, 60611395990, 60619848713, 60626032676, 60638106838, 60634927756, 60670837914, 60667014199, 60675245410, 60688404539, 60706896485, 60707298990, 60713489965, 60730506455, 60747350645, 60747462296, 60753692454, 60768609108, 60776788379, 60786001905, 60805856109, 60808951141, 60820389916, 60834481938, 60838899037, 60854788322, 60864112431, 60863582116, 60880983311, 60895465525, 60906491151, 60902867612, 60919580335, 60934819200, 60944452593, 60956462233, 60956708885, 60968450252, 60984114680, 60987274323, 61007432731, 61010592107, 61018616761, 61039727453, 61041021386, 61052098795, 61065696152, 61072230773, 61078828433, 61097570993, 61094935518, 61119163095, 61128427484, 61129350613, 61141270221, 61158160909, 61167209291, 61165225815, 61187561406, 61188529960, 61204618913, 61213945958, 61222316983, 61240957898, 61246278006, 61245926721, 61271608523, 61272375870, 61287998602, 61289938743, 61302237689, 61313122163, 61333033157, 61331746739, 61344262815, 61358016854, 61364540452, 61377860957, 61383924804, 61386633388, 61406210813, 61410107579, 61432429544, 61438753998, 61449036414, 61448937094, 61463508227, 61478378646, 61480608606, 61493096650, 61507701965, 61517383839, 61525558355, 61534941592, 61548431850, 61554379917, 61563042774, 61575735816, 61586061925, 61597598142, 61604721242, 61622529352, 61628408961, 61620836535, 61651449302, 61648349239, 61670342902, 61671514337, 61681527576, 61694978588, 61708522291, 61710947524, 61728325755, 61738254033, 61743481718, 61761584750, 61755255878, 61767851852, 61791062302, 61796513227, 61801799042, 61816583340, 61827190477, 61829177204, 61850632522, 61845889283, 61869718238, 61880131797, 61888047966, 61887004139, 61903033997, 61911320595, 61925678241, 61938621404, 61944020541, 61948369696, 61963985375, 61970736403, 61986157282, 61993715685, 62005446161, 62008644542, 62029920928, 62027680160, 62043453224, 62060261933, 62062692286, 62065783143, 62088637285, 62093610427, 62100034830, 62117415966, 62117782529, 62139639626, 62139939942, 62143400468, 62171568000, 62172230767, 62186666485, 62188964220, 62199442124, 62205107446, 62226326004, 62237489077, 62234454917, 62243059548, 62258958228, 62274675815, 62281940312, 62290500542, 62304567077, 62308626581, 62323526051, 62331453953, 62343414150, 62349535084, 62357515134, 62368905288, 62379137522, 62388945039, 62397265987, 62407227282, 62421019968, 62438034942, 62427401892, 62454921065, 62453431631, 62476001770, 62474176086, 62492753575, 62495457127, 62503526466, 62522303704, 62525479452, 62537478825, 62539782106, 62559439115, 62581195638, 62561843109, 62590769889, 62598347618, 62600647289, 62617877559, 62627751574, 62642378483, 62639191429, 62650663187, 62664207300, 62678474028, 62686354393, 62704896411, 62695686337, 62714355852, 62729425273, 62727939656, 62734740272, 62755439668, 62765271657, 62776622289, 62784092106, 62792632882, 62785919608, 62815158586, 62829275667, 62827962088, 62848051919, 62844900140, 62863068957, 62869807108, 62882444951, 62890773204, 62899586486, 62916842571, 62911508127, 62926653449, 62943662502, 62953412383, 62964025277, 62967722254, 62978944786, 62984684713, 62997857308, 63002930139, 63021685133, 63023939023, 63040495033, 63046695791, 63053447578, 63071960124, 63066172178, 63091952928, 63097670328, 63101932109, 63111631801, 63130711868, 63124216202, 63151275676, 63154396532, 63163522240, 63168747923, 63192746417, 63185827873, 63205234031, 63217635963, 63219193064, 63229405219, 63243331540, 63250792150, 63258730849, 63271035645, 63270463660, 63294764786, 63296835518, 63307746767, 63322281824, 63331147391, 63333620106, 63353424009, 63350869385, 63372998580, 63380401732, 63379554126, 63400715388, 63412489342, 63418505272, 63421730108, 63439332371, 63435937399, 63459995586, 63462630170, 63474243903, 63494582589, 63482106853, 63501626479, 63518962132, 63520875076, 63535560481, 63541785788, 63544941505, 63563399837, 63573358754, 63578411895, 63587021446, 63605165523, 63603936263, 63631579085, 63629953107, 63634731259, 63652482075, 63649470632, 63664988827, 63681644510, 63683754615, 63700820337, 63695877850, 63722259212, 63729291910, 63728897565, 63750294116, 63752005706, 63764048373, 63777253589, 63782516328, 63785213604, 63808119829, 63813454229, 63818008308, 63834239362, 63842577602, 63853882799, 63855724051, 63869569346, 63878203839, 63889845485, 63897192827, 63913373765, 63907833621, 63940519844, 63941421561, 63939884597, 63961211331, 63966077245, 63978195190, 63975338519, 64000814915, 63996938900, 64024411358, 64019167796, 64030433648, 64045228061, 64050121585, 64056675525, 64079873251, 64078519155, 64097877347, 64089495334, 64108088257, 64124887477, 64136702642, 64134100438, 64150097185, 64166602801, 64162599093, 64178071890, 64181635310, 64195266996, 64214296325, 64220924310, 64219884365, 64233833214, 64251723888, 64247672169, 64266071274, 64266499154, 64281494770, 64289954065, 64307615532, 64306424137, 64324551967, 64326287039, 64334062583, 64355240083, 64353358335, 64368950995, 64385512749, 64377899353, 64404449014, 64398485470, 64430791402, 64413557742, 64444250957, 64443715006, 64453964287, 64453160960, 64478843475, 64477861309, 64491179375, 64508134254, 64504999688, 64522394602, 64527116631, 64544714714, 64544913204, 64561986669, 64570819926, 64579161624, 64588748174, 64593036842, 64605162314, 64612651672, 64629733870, 64634426891, 64639497703, 64662125390, 64657751672, 64674241891, 64690748351, 64690060191, 64700989939, 64717221352, 64719958975, 64726717337, 64741170144, 64750747897, 64757545266, 64763960062, 64772395338, 64787023461, 64798646295, 64810076651, 64816793670, 64824059990, 64832622503, 64848575447, 64857119497, 64861168829, 64875178327, 64870844282, 64896977838, 64893930952, 64913837016, 64918860967, 64932656690, 64937215588, 64945901307, 64959749624, 64965403616, 64973244539, 64988084026, 64989858826, 64999137438, 65018319567, 65020188334, 65034329353, 65037301975, 65066075027, 65058912378, 65068888855, 65081699133, 65089409432, 65089568826, 65113423635, 65119753034, 65120427527, 65143201840, 65146583488, 65157669042, 65159068649, 65174957886, 65183425290, 65197505269, 65202448826, 65212347166, 65217213701, 65233022760, 65225782650, 65262267300, 65257568088, 65274860159, 65275145706, 65291346948, 65293345303, 65306400031, 65312894946, 65328522268, 65329068397, 65339574367, 65352013166, 65362568783, 65371618517, 65379595493, 65396292933, 65403796131, 65404401617, 65425930812, 65422223561, 65434470141, 65447663748, 65462715000, 65460813377, 65479440849, 65481872656, 65489718187, 65509157704, 65505173102, 65521324124, 65530424459, 65538703713, 65561534518, 65560728688, 65559591759, 65575759704, 65588726020, 65595408092, 65610250211, 65612891842, 65623856368, 65626709228, 65660462513, 65643786085, 65657844307, 65672218443, 65680276723, 65693262200, 65692783757, 65712746496, 65717206746, 65730665133, 65735707996, 65750279735, 65764367621, 65761919452, 65770030198, 65787879410, 65790934716, 65800254534, 65808110320, 65829002147, 65836313472, 65826880242, 65848114686, 65855717559, 65866907216, 65876479382, 65883368575, 65897360151, 65905122758, 65923040440, 65917443567, 65933849256, 65940852862, 65950027874, 65958024985, 65971819912, 65985791899, 65983488806, 65998363509, 66010227819, 66012818985, 66024688985, 66034705356, 66043065620, 66061651103, 66063199279, 66074667187, 66078668491, 66083910431, 66101606269, 66103087165, 66128130629, 66126812602, 66139050497, 66142283268, 66157083556, 66163054628, 66167206132, 66182815662, 66208266719, 66188515662, 66218409412, 66215254188, 66226264052, 66243728674, 66251880978, 66255471544, 66258776986, 66279733369, 66279111445, 66304553021, 66302059216, 66313065803, 66325722706, 66324991362, 66353204531, 66351276620, 66355771483, 66366465985, 66378830620, 66382298889, 66393256802, 66412047778, 66416926148, 66420655148, 66437026490, 66435696914, 66456371501, 66454322001, 66466041239, 66483085020, 66489009715, 66495493517, 66513356393, 66510413063, 66524303240, 66538987169, 66552648848, 66546953927, 66561771500, 66565009969, 66577400530, 66585117227, 66606236614, 66611621332, 66613675505, 66632155485, 66636214759, 66639374689, 66652767806, 66659740729, 66678232966, 66680553650, 66684813477, 66703035919, 66709958911, 66731882525, 66722811742, 66733648385, 66744370638, 66754950773, 66771452066, 66768136944, 66783755034, 66799142815, 66802827857, 66809207815, 66815498645, 66836335154, 66827033016, 66849192614, 66859522318, 66862087986, 66880136969, 66880772048, 66899277019, 66892849004, 66915506891, 66921667562, 66931613309, 66936854141, 66945606856, 66959404791, 66964393168, 66973871543, 66986430311, 66989536934, 67003589993, 67022670737, 67013057377, 67025962118, 67050122814, 67042944910, 67054248484, 67067707453, 67075639395, 67088442126, 67094874407, 67103460841, 67109055727, 67122042479, 67128202945, 67141095565, 67143473445, 67171757619, 67167608740, 67167519395, 67191532571, 67199590362, 67197099164, 67209761804, 67230194687, 67226864925, 67241054618, 67247410906, 67250576046, 67267820658, 67280543723, 67288910957, 67296057645, 67298316526, 67317316921, 67319667663, 67334589279, 67339462327, 67350360323, 67360029168, 67363749210, 67383000413, 67376063461, 67402560082, 67403444013, 67410911755, 67424856800, 67434984580, 67440321703, 67446722845, 67468195851, 67462197134, 67477403047, 67470444880, 67500851920, 67503861356, 67528632994, 67511446973, 67535676585, 67535291863, 67549814220, 67550237124, 67571208036, 67576309811, 67583290864, 67600083050, 67598467475, 67615225815, 67622317883, 67646796471, 67629051198, 67639444446, 67659590403, 67671096972, 67672111748, 67676971078, 67690654542, 67724170374, 67709131600, 67716421373, 67726058526, 67734360885, 67754104608, 67767360170, 67764396838, 67777140457, 67788570523, 67782317749, 67796465448, 67822991650, 67822552634, 67833253754, 67831146435, 67848252375, 67864958090, 67866195846, 67872844975, 67887516833, 67889307038, 67893778977, 67911158343, 67929098211, 67924837827, 67947204761, 67949623431, 67956345289, 67960502314, 67977721774, 67980003948, 67988710291, 67997452959, 68015011573, 68013538892, 68025871589, 68045987426, 68048005462, 68045562002, 68073104669, 68077856146, 68087258909, 68084216537, 68106448192, 68104914741, 68110386661, 68126803179, 68138819563, 68153314701, 68158358641, 68160602338, 68173067631, 68174671217, 68190558601, 68196845493, 68214162161, 68227030849, 68219014499, 68232324710, 68248280809, 68250801900, 68264103872, 68267800318, 68277737308, 68300504635, 68294051528, 68296838180, 68315357681, 68335384704, 68331699510, 68343130629, 68350236264, 68355799158, 68367625915, 68380849964, 68387953884, 68392930617, 68409084693, 68413202909, 68422972888, 68434278070, 68444777089, 68444735416, 68451425316, 68470091426, 68473152489, 68494424527, 68490343832, 68499786367, 68515899379, 68526105278, 68532370307, 68537012461, 68549764752, 68557435075, 68571380321, 68570939402, 68586137837, 68589230860, 68597137682, 68610807514, 68629062220, 68621746656, 68645028867, 68646803049, 68660917823, 68661632329, 68666275266, 68677804362, 68700384992, 68697618125, 68699849627, 68716172774, 68730265723, 68741378826, 68742475986, 68761162602, 68757957610, 68773143312, 68776801811, 68789794128, 68796569769, 68807749438, 68817499775, 68824209396, 68836995280, 68845138161, 68840534470, 68865475091, 68860112938, 68884254735, 68884667789, 68892450513, 68912629623, 68912067778, 68936358872, 68931824653, 68929356345, 68949081416, 68956251120, 68966574995, 68979387337, 68980141846, 68989533673, 69008355438, 69003009766, 69028964340, 69017067051, 69040529679, 69044579562, 69057331171, 69072735512, 69065425448, 69088451974, 69091635913, 69094914564, 69104138986, 69119560145, 69127485770, 69135630540, 69150532198, 69150155639, 69163158623, 69158173633, 69195506477, 69174413280, 69204006159, 69213069844, 69214437250, 69218477584, 69230925170, 69245518535, 69254843599, 69258195033, 69270505000, 69265914102, 69295767894, 69288801799, 69317830509, 69310841546, 69323690718, 69320446598, 69333117767, 69342212902, 69360080386, 69364806698, 69374377583, 69379965747, 69399756708, 69406073863, 69398208296, 69418348509, 69426725177, 69436049781, 69446175469, 69452680200, 69456741472, 69482357535, 69469819967, 69484507929, 69506592939, 69508312882, 69513872900, 69527917192, 69535108963, 69531507928, 69544311741, 69571495937, 69561846932, 69579330250, 69584029165, 69597769484, 69599524558, 69615450171, 69616990035, 69634911852, 69634145905, 69644671186, 69657214609, 69659228669, 69680555641, 69676369757, 69691035091, 69694857832, 69711087151, 69721894901, 69726545635, 69732380690, 69747006225, 69747675094, 69762610750, 69772143221, 69780647742, 69782525091, 69795296814, 69804512973, 69812825120, 69823518554, 69824957333, 69840258548, 69845056260, 69868958688, 69867664004, 69869034206, 69889478924, 69884441168, 69907985010, 69900071210, 69928580984, 69918879951, 69940880679, 69953749319, 69948286698, 69957708457, 69980039785, 69979057450, 69989362295, 69987072705, 70009268751, 70011144679, 70026796307, 70032017337, 70041587226, 70051442883, 70051138049, 70075680718, 70074001933, 70081276440, 70097004671, 70099710527, 70099327845, 70115116683, 70145087735, 70140602036, 70142579247, 70151144964, 70165752556, 70170593958, 70180376112, 70183129259, 70193881751, 70203503813, 70225959333, 70220038807, 70232324288, 70232401880, 70254080955, 70256487527, 70271380234, 70273568765, 70285239519, 70293627865, 70302521632, 70314449635, 70317636482, 70326940096, 70333195611, 70350009668, 70357487880, 70360315232, 70372137034, 70377390518, 70384531940, 70399824673, 70409060988, 70415950567, 70428722151, 70418626893, 70444782152, 70455128012, 70455229707, 70476446178, 70473215301, 70489795672, 70492462342, 70502632775, 70505403661, 70523266184, 70529263157, 70530068700, 70550140559, 70545973962, 70555865429, 70582711782, 70581902143, 70579552246, 70603236102, 70604504309, 70622199969, 70613478305, 70638079020, 70642302396, 70638592202, 70662306138, 70667990774, 70678482902, 70676488343, 70691762509, 70705318494, 70719041970, 70712711028, 70724510778, 70730521015, 70740086854, 70753961098, 70754146431, 70778438069, 70777731564, 70795396023, 70783594649, 70808574663, 70810709039, 70832798943, 70832283669, 70832860727, 70848101172, 70856088067, 70870683710, 70871576695, 70880446240};ull v[1250001];int main(){for (ul i = 1; i <= 4000; ++i) {g[i] += g[i - 1];}std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {std::scanf("%llu%u%llu", &n, &m, &k);for (ul i = 1; i <= m; ++i) {std::scanf("%llu", &p[i]);}bool flag = true;for (ul i = m; i >= 1; --i) {if (p[i] == 1) {flag = false;break;}k = (k - 1) / (p[i] - 1) * p[i] + (k - 1) % (p[i] - 1) + 1;if (k > n) {flag = false;break;}}if (!flag) {std::printf("-1\n");continue;}ull ans;ull l, r;if ((k - 1) % 2500000 + 1 <= 1250000) {ans = g[(k - 1) / 2500000];l = (k - 1) / 2500000 * 2500000 + 1;r = k;} else {ans = g[(k - 1) / 2500000 + 1];l = k + 1;r = ((k - 1) / 2500000 + 1) * 2500000;}for (ull d = 1; d * d <= r; ++d) {for (ull a = std::max((l + d - 1) / d, d); a * d <= r; ++a) {v[a * d - l + 1] = d;}}if ((k - 1) % 2500000 + 1 <= 1250000) {for (ul i = 1; i <= r - l + 1; ++i) {ans += v[i];}} else {for (ul i = 1; i <= r - l + 1; ++i) {ans -= v[i];}}std::printf("%llu\n", ans);}return 0;}
自己证明，的时候所有都是对的，的时候，串必定同构于。
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;ul T;ul n;const ul ans[5] = {1, 26, 26 * 26, 26 * 26 * 26, 26 * 25 * 24};int main(){std::freopen("distinct-sub-palindromes.in", "r", stdin);std::freopen("out.txt", "w", stdout);std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {std::scanf("%u", &n);std::printf("%u\n", ans[std::min(n, ul(4))]);}return 0;}
注意在这个域里是能开平方根的。
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;const ul mod = 1e9 + 9;const ul sqrt5 = 383008016;void exgcd(li a, li b, li& x, li& y){if (b) {exgcd(b, a % b, y, x);y -= a / b * x;} else {x = 1;y = 0;}}ul mul(ul a, ul b){return ull(a) * ull(b) % mod;}ul inverse(ul a){li x, y;exgcd(a, mod, x, y);return x < 0 ? x + li(mod) : x;}ul minus(ul a, ul b){return a < b ? a + mod - b : a - b;}ul plus(ul a, ul b){return a + b < mod ? a + b : a + b - mod;}const ul maxk = 1e5;ul at[maxk + 1];ul bt[maxk + 1];ul alphat[maxk + 1];ul betat[maxk + 1];ul fac[maxk + 1];ul fiv[maxk + 1];ul T;ul power(ul a, ull b){ul ret = 1;while (b) {if (b & 1) {ret = mul(ret, a);}a = mul(a, a);b >>= 1;}return ret;}ul qt[maxk + 1];ul qtnp1[maxk + 1];ul alphact[maxk + 1];ul betact[maxk + 1];ul alphacnp1t[maxk + 1];ul betacnp1t[maxk + 1];int main(){fac[0] = 1;for (ul i = 1; i <= maxk; ++i) {fac[i] = mul(fac[i - 1], i);}fiv[maxk] = inverse(fac[maxk]);for (ul i = maxk; i; --i) {fiv[i - 1] = mul(fiv[i], i);}const ul a = inverse(sqrt5);const ul b = minus(0, a);const ul alpha = mul(inverse(2), plus(1, sqrt5));const ul beta = mul(inverse(2), minus(1, sqrt5));at[0] = bt[0] = 1;for (ul i = 1; i <= maxk; ++i) {at[i] = mul(at[i - 1], a);bt[i] = mul(bt[i - 1], b);}std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {ull n, c;ul k;std::scanf("%llu%llu%u", &n, &c, &k);ul ans = 0;ul alphac = power(alpha, c);ul betac = power(beta, c);ul alphacnp1 = power(alphac, n + 1);ul betacnp1 = power(betac, n + 1);alphact[0] = betact[0] = alphacnp1t[0] = betacnp1t[0] = 1;for (ul i = 1; i <= k; ++i) {alphact[i] = mul(alphact[i - 1], alphac);betact[i] = mul(betact[i - 1], betac);alphacnp1t[i] = mul(alphacnp1t[i - 1], alphacnp1);betacnp1t[i] = mul(betacnp1t[i - 1], betacnp1);}for (ul t = 0; t <= k; ++t) {ul cc = mul(mul(fiv[t], fiv[k - t]), fac[k]);ul q = mul(alphact[t], betact[k - t]);ul fqn;if (q == 1) {fqn = (n + 1) % mod;} else {fqn = mul(minus(1, mul(alphacnp1t[t], betacnp1t[k - t])), inverse(minus(1, q)));}ans = plus(ans, mul(cc, mul(mul(at[t], bt[k - t]), fqn)));}printf("%u\n", ans);}return 0;}
度数根号分类。
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;ul n, m;const ul maxn = 1e5;const ul maxm = 1e5;ul a[maxn + 1];ul root[maxn + 1];const ul sz = 1 << 17;ul tree[351][sz << 1];ul tot;void change(ul pos, ul v, ul tree[]){for (tree[pos |= sz] += v, pos >>= 1; pos; pos >>= 1) {tree[pos] = std::min(tree[pos << 1], tree[pos << 1 | 1]);}}ul query(const ul tree[]){ul ret = 1;while (ret < sz) {if (tree[ret << 1]) {ret = ret << 1 | 1;} else {ret = ret << 1;}}return ret & ~sz;}std::set<ul> edges[maxn + 1];std::vector<ul> eedges[maxn + 1];std::vector<ul> spedges[maxn + 1];ul q;std::vector<ul> stack;ul T;int main(){std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {std::scanf("%u%u", &n, &m);for (ul i = 1; i <= n; ++i) {std::scanf("%u", &a[i]);edges[i].clear();spedges[i].resize(0);eedges[i].resize(0);}for (ul i = 1; i <= m; ++i) {ul u, v;std::scanf("%u%u", &u, &v);edges[u].insert(v);edges[v].insert(u);}for (ul i = 1; i <= n; ++i) {for (ul j : edges[i]) {eedges[i].push_back(j);}}ul D = 350;tot = 0;for (ul i = 1; i <= n; ++i) {if (eedges[i].size() > D) {++tot;root[i] = tot;std::memset(tree[tot], 0, sizeof(ul) * (sz + sz));for (ul j : eedges[i]) {if (a[j] <= eedges[i].size()) {change(a[j], 1, tree[root[i]]);}spedges[j].push_back(i);}}}std::scanf("%u", &q);for (ul i = 1; i <= q; ++i) {ul qt;std::scanf("%u", &qt);if (qt == 1) {ul u, x;std::scanf("%u%u", &u, &x);if (x != a[u]) {for (ul v : spedges[u]) {if (a[u] <= eedges[v].size()) {change(a[u], -1, tree[root[v]]);}if (x <= eedges[v].size()) {change(x, 1, tree[root[v]]);}}a[u] = x;}} else {ul u;std::scanf("%u", &u);if (eedges[u].size() > D) {std::printf("%u\n", query(tree[root[u]]));} else {stack.resize(0);stack.push_back(-1);for (ul v : eedges[u]) {if (a[v] <= eedges[u].size()) {stack.push_back(a[v]);}}std::sort(std::next(stack.begin()), stack.end());for (ul i = 0; i != stack.size(); ++i) {if (stack.size() == i + 1 || stack[i + 1] > stack[i] + 1) {std::printf("%u\n", stack[i] + 1);break;}}}}}}return 0;}
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;const ul base = 1e9 + 9;ul plus(ul a, ul b){return a + b < base ? a + b : a + b - base;}ul minus(ul a, ul b){return a < b ? a + base - b : a - b;}ul mul(ul a, ul b){return ull(a) * ull(b) % base;}void exgcd(li a, li b, li& x, li& y){if (b) {exgcd(b, a % b, y, x);y -= x * (a / b);} else {x = 1;y = 0;}}ul inverse(ul a){li x, y;exgcd(a, base, x, y);return x < 0 ? x + li(base) : x;}ul pow(ul a, ul b){ul ret = 1;ul temp = a;while (b) {if (b & 1) {ret = mul(ret, temp);}temp = mul(temp, temp);b >>= 1;}return ret;}class polynomial {public:ul v[1 << 21];ul size = 0;ul& operator[](ul x) {return v[x];}ul operator[](ul x) const {return v[x];}void clearzero() {while (size && !v[size - 1]) {--size;}}void resize(ul x) {if (x > size) {std::memset(v + size, 0, sizeof(ul) * (x - size));}size = x;}polynomial& operator=(const polynomial& b) {size = b.size;std::memcpy(v, b.v, size * sizeof(ul));return *this;}};using llf = double;class num {public:llf x = 0;llf y = 0;num(llf a = 0, llf b = 0): x(a), y(b) {}num conj() const {return num(x, -y);}};num operator+(const num& a, const num& b){return num(a.x + b.x, a.y + b.y);}num operator-(const num& a, const num& b){return num(a.x - b.x, a.y - b.y);}num operator*(const num& a, const num& b){return num(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);}const llf pi = std::acos(llf(-1));class ntt_t {public:static const ul lgsz = 21;static const ul sz = 1 << lgsz;num w[sz + 1];ntt_t() {for (ul i = 0; i <= sz; ++i) {w[i] = num(std::cos(pi * (i + i) / sz), std::sin(pi * (i + i) / sz));}}void operator()(num v[], ul& n, bool inv) {ul lgn = 0;while ((1 << lgn) < n) {++lgn;}for (ul i = 0, j = 0; i != n; ++i) {if (i < j) {std::swap(v[i], v[j]);}ul k = n >> 1;while (k & j) {j &= ~k;k >>= 1;}j |= k;}num t1;for (ul lgmid = 0; (1 << lgmid) != n; ++lgmid) {ul mid = 1 << lgmid;ul len = mid << 1;for (ul i = 0; i != n; i += len) {for (ul j = 0; j != mid; ++j) {t1 = w[inv ? (len - j << lgsz - lgmid - 1) : (j << lgsz - lgmid - 1)] * v[i + j + mid];v[i + j + mid] = v[i + j] - t1;v[i + j] = v[i + j] + t1;}}}if (inv) {for (ul i = 0; i != n; ++i) {v[i].x /= n;v[i].y /= n;}}}} ntt;const ul M = 31622;const num inv2(0.5, 0);const num inv2i(0, -0.5);const num I(0, 1);polynomial& operator*=(polynomial& a, const polynomial& b){if (!b.size || !a.size) {a.resize(0);return a;}static polynomial temp;ul npmp1 = a.size + b.size - 1;ul lgnpmp1 = 0;while ((1 << lgnpmp1) < npmp1) {++lgnpmp1;}npmp1 = 1 << lgnpmp1;if (ull(a.size) * ull(b.size) <= ull(npmp1) * ull(50)) {temp.resize(0);temp.resize(npmp1);for (ul i = 0; i != a.size; ++i) {for (ul j = 0; j != b.size; ++j) {temp[i + j] = plus(temp[i + j], mul(a[i], b[j]));}}a = temp;a.clearzero();return a;}static num p1[1 << 21];static num p2[1 << 21];std::memset(p1, 0, sizeof(num) * npmp1);std::memset(p2, 0, sizeof(num) * npmp1);for (ul i = 0; i != a.size; ++i) {p1[i].x = a[i] / M;p2[i].x = a[i] % M;}for (ul i = 0; i != b.size; ++i) {p1[i].y = b[i] / M;p2[i].y = b[i] % M;}ntt(p1, npmp1, false);ntt(p2, npmp1, false);static num q1[1 << 21];static num q2[1 << 21];for (ul i = 0; i != npmp1; ++i) {num a1 = (p1[i] + (p1[-i & npmp1 - 1].conj())) * inv2;num b1 = (p1[i] - (p1[-i & npmp1 - 1].conj())) * inv2i;num a2 = (p2[i] + (p2[-i & npmp1 - 1].conj())) * inv2;num b2 = (p2[i] - (p2[-i & npmp1 - 1].conj())) * inv2i;q1[i] = a1 * b1 + a2 * b2 * I;q2[i] = a1 * b2 + a2 * b1 * I;}ntt(q1, npmp1, true);ntt(q2, npmp1, true);a.size = npmp1;ul a1b1, a2b2, a1b2, a2b1;for (ul i = 0; i != npmp1; ++i) {a1b1 = std::llround(q1[i].x) % base;a2b2 = std::llround(q1[i].y) % base;a1b2 = std::llround(q2[i].x) % base;a2b1 = std::llround(q2[i].y) % base;a[i] = plus(mul(plus(mul(a1b1, M), plus(a1b2, a2b1)), M), a2b2);}a.clearzero();return a;}const polynomial& inverse(const polynomial& a, ul lgdeg){static polynomial ret;static polynomial tempa;ret.size = 1;ret[0] = inverse(a[0]);for (ul i = 0; i != lgdeg; ++i) {tempa.resize(0);tempa.resize(1 << i << 1);std::memcpy(tempa.v, a.v, sizeof(ul) * std::min(tempa.size, a.size));tempa *= ret;for (ul i = 0; i != tempa.size; ++i) {tempa[i] = minus(0, tempa[i]);}tempa[0] = plus(tempa[0], 2);tempa *= ret;if (tempa.size > (1 << i << 1)) {tempa.resize(1 << i << 1);}tempa.clearzero();ret = tempa;}return ret;}const ul maxn = 1e5;ul T;ul n;ul fac[maxn * 4 + 2];ul fiv[maxn * 4 + 2];polynomial p;int main(){fac[0] = 1;for (ul i = 1; i <= maxn * 4 + 1; ++i) {fac[i] = mul(fac[i - 1], i);}fiv[maxn * 4 + 1] = inverse(fac[maxn * 4 + 1]);for (ul i = maxn * 4 + 1; i >= 1; --i) {fiv[i - 1] = mul(fiv[i], i);}p.size = maxn * 4 + 1;for (ul i = 0; i <= maxn * 4; ++i) {p[i] = fiv[i + 1];}p = inverse(p, 19);p.resize(maxn * 4 + 1);for (ul i = 0; i <= maxn * 4; ++i) {p[i] = mul(p[i], fac[i]);}std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {std::scanf("%u", &n);std::printf("%u\n", minus(0, mul(mul(n + n, p[4 * n]), inverse(mul(p[2 * n], p[2 * n])))));}return 0;}
简单题
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;class data {public:ll p = 0;ll a = 0;bool kill = false;data()=default;};ul T, n;const ul maxn = 50000;data v[maxn + 1];std::vector<data> stack;bool check(const data& a, const data& b, data& c){if (c.a == b.a && c.p == b.p) {c.kill = true;return true;}return (b.p - c.p) * (b.a - a.a) <= (a.p - b.p) * (c.a - b.a);}bool check(const data& a, data& b){if (b.a == a.a && b.p == a.p) {b.kill = true;return true;}return (a.p - b.p) <= 0;}int main(){std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {std::scanf("%u", &n);for (ul i = 1; i <= n; ++i) {std::scanf("%lld%lld", &v[i].p, &v[i].a);v[i].kill = false;}std::sort(v + 1, v + n + 1, [](const data& a, const data& b){return a.a != b.a ? a.a < b.a : a.p < b.p;});stack.resize(0);for (ul i = 1; i <= n; ++i) {while (stack.size() > 1 && check(stack[stack.size() - 2], stack[stack.size() - 1], v[i]) || stack.size() == 1 && check(stack.back(), v[i])) {stack.pop_back();}stack.push_back(v[i]);}ul cnt = 0;for (const auto& s : stack) {cnt += !s.kill;}std::printf("%u\n", cnt);}return 0;}
对于，设
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;const ul mod = 998244353;ul plus(ul a, ul b){return a + b < mod ? a + b : a + b - mod;}ul minus(ul a, ul b){return a < b ? a + mod - b : a - b;}ul mul(ul a, ul b){return ull(a) * ull(b) % mod;}void exgcd(li a, li b, li& x, li& y){if (b) {exgcd(b, a % b, y, x);y -= a / b * x;} else {x = 1;y = 0;}}ul inverse(ul a){static li x, y;exgcd(a, mod, x, y);return x < 0 ? x + li(mod) : x;}const ul maxn = 1e8;ul h[maxn + 1];ul T, n;std::vector<ul> facs;int main(){if (true) {ul* fac = h;fac[0] = 1;for (ul i = 1; i <= maxn; ++i) {fac[i] = mul(fac[i - 1], i);}ul fiv = inverse(fac[maxn]);ul* inv = h;for (ul i = maxn; i >= 1; --i) {ul nextfiv = mul(fiv, i);inv[i] = mul(fac[i - 1], fiv);fiv = nextfiv;}h[0] = 0;for (ul i = 1; i <= maxn; ++i) {h[i] = plus(h[i - 1], inv[i]);}}std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {std::scanf("%u", &n);if (n == 2) {std::printf("%u\n", minus(h[2], 1));continue;}facs.resize(0);ul tn = n;for (ul i = 2; i * i <= tn; ++i) {if (tn % i == 0) {facs.push_back(i);while (tn % i == 0) {tn /= i;}}}if (tn != 1) {facs.push_back(tn);tn = 1;}ul tmp = facs.back();ul ans = 0;for (ul i = (1 << facs.size()) - 1; ; --i) {ul mask = i ^ i >> 1;if (__builtin_popcount(mask) & 1) {ans = minus(ans, mul(minus(h[tmp], h[tmp - 1]), h[n / tmp]));} else {ans = plus(ans, mul(minus(h[tmp], h[tmp - 1]), h[n / tmp]));}if (!i) {break;}ul nextmask = i - 1 ^ i - 1 >> 1;ul change = facs[__builtin_ctz(mask ^ nextmask)];if (mask < nextmask) {tmp *= change;} else {tmp /= change;}}ans = mul(ans, minus(h[n], h[n - 1]));ans = plus(ans, minus(h[2], 1));std::printf("%u\n", ans);}return 0;}
注意到一个字符串的所有非空后缀中字典序最小的那个一定是其林登分解中最后边那个，这就意味着只要完全理解了Duval算法到底是怎样执行的，就能直到该怎么做了（Duval算法见https://www.zybuluo.com/qq290637843/note/1770933）。下方代码中的ans[i]表示的最小字典序非空后缀的长度。
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;const ul maxn = 1e6;ul T;char s[maxn + 2];ul n;ul ans[maxn + 1];ul out;const ul mod = 1e9 + 7;const ul base = 1112;int main(){std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {std::scanf("%s", s + 1);for (ul i = 1, j, k; s[i]; ) {ans[i] = 1;for (k = i, j = k + 1; s[j] >= s[k]; ++j) {if (s[j] > s[k]) {ans[j] = j - i + 1;k = i;} else {ans[j] = ans[k];++k;}}while (i <= k) {i += j - k;}}out = 0;for (ul i = std::strlen(s + 1); i >= 1; --i) {out = ull(out) * ull(base) % mod;out = out + i - ans[i] + 1 < mod ? out + i - ans[i] + 1 : out + i - ans[i] + 1 - mod;}std::printf("%u\n", out);}return 0;}
裸半平面交
#include <bits/stdc++.h>using ul = std::uint32_t;using li = std::int32_t;using ull = std::uint64_t;using ll = std::int64_t;using lf = double;const ul maxn = 200;class vec {public:lf x = 0;lf y = 0;vec()=default;vec(lf a, lf b): x(a), y(b) {}};vec operator+(const vec& a, const vec& b){return vec(a.x + b.x, a.y + b.y);}vec operator-(const vec& a, const vec& b){return vec(a.x - b.x, a.y - b.y);}lf operator*(const vec& a, const vec& b){return a.x * b.x + a.y * b.y;}lf operator^(const vec& a, const vec& b){return a.x * b.y - a.y * b.x;}vec operator*(const vec& a, lf b){return vec(a.x * b, a.y * b);}vec operator*(lf a, const vec& b){return vec(a * b.x, a * b.y);}vec operator/(const vec& a, lf b){return vec(a.x / b, a.y / b);}lf mysqrt(lf x){return std::sqrt(std::max(lf(0), x));}lf len(const vec& a){return mysqrt(a * a);}vec p[maxn + 1];ul T, n;lf r, a, b;vec getcross(const vec& a, const vec& b, const vec& c, const vec& d){return a + (c - a ^ d - c) / (b - a ^ d - c) * (b - a);}std::deque<vec> hull;vec rotate(const vec& a){return vec(-a.y, a.x);}const lf inf = 1e6;bool insert(const vec& dir, lf val){vec a = rotate(dir) * val;if (hull.empty()) {hull.push_back(a - inf * dir);hull.push_back(a + inf * dir);return true;}vec b = a + dir;while ((dir ^ hull.front()) < val) {vec d = hull.front();hull.pop_front();vec c = hull.front();if ((dir ^ d - c) >= 0) {return false;}vec x = getcross(a, b, c, d);if ((d - c) * (x - c) >= 0) {hull.push_front(x);break;}}if ((dir ^ hull.back()) >= val) {return true;}while ((dir ^ hull.back()) < val) {vec d = hull.back();hull.pop_back();vec c = hull.back();if ((dir ^ d - c) >= 0) {return false;}vec x = getcross(a, b, c, d);if ((d - c) * (x - c) >= 0) {hull.push_back(x);break;}}if (len(hull.front()) > 0.5 * inf) {hull.push_back(hull.back() + inf * dir);} else {hull.push_back(hull.front());}return true;}lf in(){double tmp;std::scanf("%lf", &tmp);return tmp;}int main(){std::scanf("%u", &T);for (ul Case = 1; Case <= T; ++Case) {std::scanf("%u", &n);r = in();a = in();b = in();for (ul i = 1; i <= n; ++i) {p[i].x = in();p[i].y = in();}p[0] = p[n];lf area = 0;for (ul i = 1; i <= n; ++i) {area += p[i - 1] ^ p[i];}area *= 0.5;if (area < 0) {std::reverse(p, p + n + 1);area = -area;}if (a <= b) {std::printf("%.20lf\n", double(area * a));continue;}bool flag = true;while (hull.size()) {hull.pop_front();}for (ul i = 1; i <= n; ++i) {vec tmp = p[i] - p[i - 1];tmp = tmp / len(tmp);if (!insert(tmp, (tmp ^ p[i - 1]) + r)) {flag = false;break;}}if (!flag) {std::printf("%.20lf\n", double(area * a));} else {lf area2 = std::acos(lf(-1)) * r * r;for (auto i = hull.begin(), j = std::next(i); j != hull.end(); i = j, ++j) {area2 += len(*j - *i) * r;area2 += 0.5 * (*i ^ *j);}std::printf("%.20lf\n", double((area - area2) * a + area2 * b));}}return 0;}