SN-NOI Pro 迷惑行为大赏

CXiii · 2025-12-05 17:21:57 · 休闲·娱乐

前言

本文内容不代表作者观点
upd1:2025 12 6 10:49 修改了部分格式错误

概述

在本次 NOI Pro 中，共 230 位选手提交了 216 份文件夹。
以下选手没有提交文件夹（默哀）

SN-0073  SN-0083  SN-0090  SN-0100
SN-0101  SN-0105  SN-0113  SN-0123
SN-0148  SN-0150  SN-0151  SN-0159
SN-0169  SN-0170

选手代码

SN-0002 还有第二关

query.cpp

//  system("fc sale.out sale11.ans");
//  freopen("query.in","r",stdin);
//  freopen("query.out","w",stdout);

SN-0005 SN rank 1 313pts

query.cpp

  // ll can't pass more tests.

SN-0009 我看不懂

该考生的四份cpp文件的末尾均有以下注释

SN-0031 祈使句

query.cpp

cout << "give me 1=";

SN-0035 河移位

tree.cpp

    //freopen("","r",stdin);
    //freopen("","w",stdout);

SN-0036 复刻经典

candy.cpp

/*
复刻经典
freopen,数组大小,return/continue,long long
不慌不急不躁，拿能拿的所有分
kill it!
D
T1 : 9:00 killed
T2 : ??
T3 : ??
T4 : ??
*/

sale.cpp

/*
复刻经典
freopen,数组大小,return/continue,long long
不慌不急不躁，拿能拿的所有分
kill it!
D
T1 : ??
T2 : wcnm
T3 : ??
T4 : ??
*/

tree.cpp

/*
复刻经典
freopen,数组大小,return/continue,long long
不慌不急不躁，拿能拿的所有分
kill it!
D
T1 : ??
T2 : wcnm
T3 : ??
T4 : ??
*/

query.cpp

/*
复刻经典
freopen,数组大小,return/continue,long long
不慌不急不躁，拿能拿的所有分
kill it!
D
T1 : ??
T2 : ??
T3 : ??????????????
T4 : ？？？？？？？？？？？？？？？？？？？？？？？？？？？？？ 
*/

SN-0043 正确的

candy.cpp

//tanxin?  9:38 maybe ac;

SN-0046 幸运码

candy.cpp

//lucky code

SN-0048 祝好

candy.cpp

/*
最后一场了
考完就退役了~~
千万别挂！！ 
*/

sale.cpp

//      cout<<"给点分吧！！"评测姬给点分吧！！！

tree.cpp

/*
坏了，推测是假的，那就只有部分分13,14了！！！~~~
评测姬给点分吧！！！
最好情况100+16+16+15，我就是个...... 
*/

query.cpp

//评测姬给点分吧！！！

SN-0051 QAQ

candy.cpp

//please give me 100pts

tree.cpp

//QAQ

SN-0058 单目运算符&psuh

query.cpp

bool check1(){
    if(nv.top().first<)
}

nc.psuh({val[y][2],y});

    //freopen("candy.in", "r", stdin);
    //freopen("candy.out", "w", stdout);

sale.cpp

    //freopen("candy.in", "r", stdin);
    //freopen("candy.out", "w", stdout);

query.cpp

    //freopen("candy.in", "r", stdin);
    //freopen("candy.out", "w", stdout);

SN-0059 欲说还休

这位选手的 T1 T3 T4 代码一致并且没有加freopen
唯一写了freopen的 T2

//  freopen("sale4.in", "r", stdin);
    //freopen("candy.out", "w", stdout);

/*
没必要写了……话说就算拿一等又如何？
人间多少事，欲说还休。 
*/

SN-0062 曼哈顿

query.cpp

cout<<"CCF工作室"<<"\n"<<"快让组合死一死"<<"\n"<<"不然我就曼哈顿"<<"\n"<<"你的工作室！";

SN-0063 唔~~

query.cpp

cout<<"Wuuuu~~";

SN-0065 空格tree

tree.cpp

    freopen("tree.in","r",stdin);
    freopen(" tree.out","w",stdout);

SN-0068 btis

tree.cpp

#include<btis/stdc++.h>

SN-0070 第二关

sale.cpp

    freopen("sale2.in","r",stdin);
//  freopen("sale.out","w",stdout);

SN-0071 不会

tree.cpp

    std::cout << buhui << std::endl;

SN-0072 祝好

candy.cpp

//AFO-NOIP 2025

SN-0074 rp++

/*
NOIP 2025 RP++

Remember to use long long when the data is too big !
Check the file name !
Do not output extra things which do not form the standard !
*/

SN-0088 bts

sale.cpp&query.cpp

#include <bts/stdc++.h>

SN-0107 %%vvauted

candy.cpp

//看着像是完全背包的变式
//但是你怎么知道我没有复习dp
//特殊性质写了
//运气好能40pts吧...
//vvauted 大神保佑我能骗到这点分。。。

sale.cpp

//haha
//找规律找了1h
//特殊性质还不知道对不对
//vvauted 大神保佑我能骗到这点分。。。

tree.cpp

//没学图论。

query.cpp

//输出格式都看不懂。
//唉唉 
//回去写篇游记进食学弟们吧

SN-0118 我是李华

query.cpp

    //idk QAQ 
    /*
    Dear Jerry
            Hi,I'm Li Hua.In the winter I want to go to the UK
        but I don't go to the UK beacuse my son is OK.I have to
        go to ICU because I love my son.My son want to go to the mon.
        But he is go to the earth.In the earth are sleep.
            My son is KO,my are sad.The last summe I go to the UK because 
        I want.This winter I don't go to the UK because I love my son.
        And he is go to the earth.Thank you from my and my son.
                                                            Yours
                                                            LiHua
    */

笔者在此提供翻译（百度）

亲爱的杰瑞
   嗨，我是李华。冬天我想去英国,但我去英国是因为我儿子没问题。我必须去重症监护室是因为我爱我的儿子。我的儿子想去月亮。但他正前往地球。在地球上，万物沉睡。我的儿子去世了，我们都很悲伤。去年夏天我去了英国，因为我想要。这个冬天我不去英国，因为我爱我的儿子。他即将踏上地球之旅。我和我的儿子在此向您致谢。
                  你的，
                   李华

SN-0127 评论内容过短

candy.cpp

//ez，这题为啥不能用dp（不能吧。。） 
//我一直在哭
//求noip善待我这个才学了一年的蒟蒻行不
//在弱省的弱校学OI这辈子有了 
//说到底我为什么在这里
//T1骗分中。。。
//骗你的其实连骗分都不会
//我不想在这里，
//我也不想在那里，
//但天黑的太快我早就来不及。
//哦我爱你，
//可是关系变成没关系，
//问题是没问题，
//于是，
//我们继续。

//但是我不能继续了对（） 
//T3T4都是个啥阴

sale.cpp

//你TLE你很NB呗！
//小x再见我不喜欢吃糖。

tree.cpp

//请输入文本
//虽然应该能用dp但我不会树。 
//依旧马扁
//你为啥没有特殊性质。

query.cpp

//请输入文本X2
//私密马赛我看不懂
//骗分也骗不了
//那彳亍呗

//这题到底是啥呀。。
//特殊性质我也看不懂啊
//qwq
//(`^`| 
//放弃挣扎

SN-0137 祖宗

candy.cpp

//十年OI一场空，不开long long 见祖宗

SN-140 强调

candy.cpp

//  **GET THE FREOPENS OUT REMEBER!!!!**

sale.cpp&tree.cpp

//本. 题. 包. 含. 多. 组. 测. 试. 数. 据。

SN-0146 疑骂无证

candy.cpp

//if feels i like a piece of shirt oh fak U!

SN-0157 谢谢

tree.cpp

//祝看到这条代码的人开心快乐~

SN-0158 二

candy.cpp

    freopen(candy.in,"r",stdin);
    freopen(candy.out,"w",stdout);

SN-0160 作业更重要

candy.cpp

//9:21 后两个样例少了1，重新检查 
//9:45 改的有问题，先放，还有3时15分 
//9:50 后面题有些诡异，又回来了，求AC 
//10:40 我真傻，真的，我单是知道样例出错要改，但没想到要改这么久，样例6还是没过，不求AC，但求心安，我还有3道题啊TAT；

sale.cpp

//排列组合忘了，这题看不懂

tree.cpp

//建树也忘了TAT

query.cpp

//啊啊啊，我都干了些什么，花了一早上打这个？我的作业啊    12:42

SN-0165 堵桥吗

candy.cpp

//就我这代码其实开不开longlong都无所谓了 反正那4个点过不了

/*8:44 T1看着还好 ，比S组第二轮T1还简单qwq，贪心或者dp吧 
反正那个反悔贪心我没做出来qaq */

//10^18不开longlong见祖宗

/*
9:28 看到后面题吓哭了:( 
我要回家打三角洲啊啊啊啊啊啊啊啊 
11:18 补兑这T1补兑 贪心好像只有40pts啊啊啊啊啊啊啊啊啊推了看dp吧
11:46 f  k 洗吸爱抚 再这么搞我去化竞了(好像也没机会了) 
*/

sale.cpp&tree.cpp

//成  这一块./

SN-0167 二

candy.cpp

    //freopen("candy.in","r",stdin);
    //freopen("candy.out","w",stdout);

(其余的三份空代码的freopen都写对了)

SN-0193 盒

candy.cpp

//luogu 1038651

SN-0197 ciallo

candy.cpp

//Ciallo~(∠> ω< )⌒☆
//你知道这个上圆弧我找了多久吗，我在win+句点找了一万年 
//不知道win10是不是删了用搜狗的更多符号才找到 
//你说的对但是我不是 CuteMurasame，我是 UKE_Automation
//哈哈哈哈旁边的哥们电脑坏了走了我可以独占整个位置了！
//T1这么简单？？？ 
//贪心伪了怎么办急急急急急急急
//噢噢噢噢是反悔贪心啊哈哈哈哈哈哈哈
//他都考了一次了不能考第二次了吧.jpg

sale.cpp

//Ciallo~(∠> ω< )⌒☆
//题目描述居然是连续剧！ 
//妈的思路居然也是连续剧，T1贪心不写反悔的你.jpg 
//已过去 2.5h 啥都不会，决定 2^n 跑路

tree.cpp

//Ciallo~(∠> ω< )⌒☆
//此时还剩 1.5h，我们的 UKE_Automation 获得了 125 分的好成绩，真是堂堂又比比啊 
//此时还剩 0.75h，我们的 UKE_Automation 获得了 145 分的好成绩，真是堂堂又比比啊 
//我打的再炸心态不能炸，我注释的第一行和 string main 的返回值不会变，这是重要的
//Xzz 考前问那个立牌是不是比 NOIp 重要我说是，因为这个东西的背后是我乐观的本质，没了这个我也不剩啥了。 
//这种哗众的表演不一定能取宠，但能逃避苦难

query.cpp

//Ciallo~(∠> ω< )⌒☆

SN-0200 祝好

tree/cpp

    /*写到这里已然崩溃，若有来世绝对不当oier*/

query.cpp

/*写了有一会儿的T4，因为自己太着急，想假了，现在只剩10分钟了，绝望说不上，但挺难过的。*/

SN-0203 there's always hope for you

candy.cpp

//1.5h, Is there hope?

SN-0204 just do it

candy.cpp&sale.cpp&tree.cpp

// Just do it 尽管我无法证明他的对错，但我坚信他是对的！

query.cpp

// Just do it 尽管我无法证明他的对错，但我坚信他是对的！ 
/*
第一次参加NOIP，听说可以进抽象代码大赏
ccf fa you
freopen("query.out","r",stdout); 
freopen("query,out","r",stdout); 
freopen("query.in","r",stdout); 
freopen("query.out","w",stin); 
froepen("query.out","w",stdout); 
*/

SN-0211 recall

query.cpp

/*
我常常追忆过去……
我觉得这就是一道根号题…… 
*/

SN-0215 %%%ccf

candy.cpp&sale.cpp&tree.cpp&query.cpp

//tyy 8z03 hhh %%%ccf

SN-0221 要素过多

candy.cpp

/*
知周所众，背包dp的复杂度是O(nm)的
那么现在给你一个无限容量的背包
你惊奇的发现
复杂度变成了O(∞)
太难了，根本不会！ 

//freopen
freeopen
froepen
freopon
114514

我们使用分块差差分的方法
fk it all~ fk it all~
为什么我旁边的同学打题会爽得叫出来啊

宁芙奖请投 “囚徒”
祝巴尔克纪念日安康

ccf i love you so please let me ac this fking dm candy 
*/

sale.cpp ::::info[ta把2的幂次打表了]

//高雅人士品鉴中
int pow2[5010]= {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,75497471,150994942,301989884,603979768,209715183,419430366,838860732,679477111,360709869,721419738,444595123,889190246,780136139,562027925,125811497,251622994,503245988,8247623,16495246,32990492,65980984,131961968,263923936,527847872,57451391,114902782,229805564,459611128,919222256,840200159,682155965,366067577,732135154,466025955,932051910,865859467,733474581,468704809,937409618,876574883,754905413,511566473,24888593,49777186,99554372,199108744,398217488,796434976,594625599,191006845,382013690,764027380,529810407,61376461,122752922,245505844,491011688,982023376,965802399,933360445,868476537,738708721,479173089,958346178,918448003,838651653,679058953,359873553,719747106,441249859,882499718,766755083,535265813,72287273,144574546,289149092,578298184,158352015,316704030,633408060,268571767,537143534,76042715,152085430,304170860,608341720,218439087,436878174,873756348,749268343,500292333,2340313,4680626,9361252,18722504,37445008,74890016,149780032,299560064,599120128,199995903,399991806,799983612,601722871,205201389,410402778,820805556,643366759,288489165,576978330,155712307,311424614,622849228,247454103,494908206,989816412,981388471,964532589,930820825,863397297,728550241,458856129,917712258,837180163,676115973,353987593,707975186,417706019,835412038,672579723,346915093,693830186,389416019,778832038,559419723,120595093,241190186,482380372,964760744,931277135,864309917,730375481,462506609,925013218,851782083,705319813,412395273,824790546,651336739,304429125,608858250,219472147,438944294,877888588,757532823,516821293,35398233,70796466,141592932,283185864,566371728,134499103,268998206,537996412,77748471,155496942,310993884,621987768,245731183,491462366,982924732,967605111,936965869,875687385,753130417,508016481,17788609,35577218,71154436,142308872,284617744,569235488,140226623,280453246,560906492,123568631,247137262,494274524,988549048,978853743,959463133,920681913,843119473,687994593,377744833,755489666,512734979,27225605,54451210,108902420,217804840,435609680,871219360,744194367,490144381,980288762,962333171,926421989,854599625,710954897,423665441,847330882,696417411,394590469,789180938,580117523,161990693,323981386,647962772,297681191,595362382,192480411,384960822,769921644,541598935,84953517,169907034,339814068,679628136,361011919,722023838,445803323,891606646,784968939,571693525,145142697,290285394,580570788,162897223,325794446,651588892,304933431,609866862,221489371,442978742,885957484,773670615,549096877,99949401,199898802,399797604,799595208,600946063,203647773,407295546,814591092,630937831,263631309,527262618,56280883,112561766,225123532,450247064,900494128,802743903,607243453,216242553,432485106,864970212,731696071,465147789,930295578,862346803,726449253,454654153,909308306,820372259,642500165,286755977,573511954,148779555,297559110,595118220,191992087,383984174,767968348,537692343,77140333,154280666,308561332,617122664,236000975,472001950,944003900,889763447,781282541,564320729,130397105,260794210,521588420,44932487,89864974,179729948,359459896,718919792,439595231,879190462,760136571,522028789,45813225,91626450,183252900,366505800,733011600,467778847,935557694,872871035,747497717,496751081,993502162,988759971,979275589,960306825,922369297,846494241,694744129,391243905,782487810,566731267,135218181,270436362,540872724,83501095,167002190,334004380,668008760,337773167,675546334,352848315,705696630,413148907,826297814,654351275,310458197,620916394,243588435,487176870,974353740,950463127,902681901,807119449,615994545,233744737,467489474,934978948,871713543,745182733,492121113,984242226,970240099,942235845,886227337,774210321,550176289,102108225,204216450,408432900,816865800,635487247,272730141,545460282,92676211,185352422,370704844,741409688,484575023,969150046,940055739,881867125,765489897,532735441,67226529,134453058,268906116,537812232,77380111,154760222,309520444,619040888,239837423,479674846,959349692,920455031,842665709,687087065,375929777,751859554,505474755,12705157,25410314,50820628,101641256,203282512,406565024,813130048,628015743,257787133,515574266,32904179,65808358,131616716,263233432,526466864,54689375,109378750,218757500,437515000,875030000,751815647,505386941,12529529,25059058,50118116,100236232,200472464,400944928,801889856,605535359,212826365,425652730,851305460,704366567,410488781,820977562,643710771,289177189,578354378,158464403,316928806,633857612,269470871,538941742,79639131,159278262,318556524,637113048,275981743,551963486,105682619,211365238,422730476,845460952,692677551,387110749,774221498,550198643,102152933,204305866,408611732,817223464,636202575,274160797,548321594,98398835,196797670,393595340,787190680,576137007,154029661,308059322,616118644,233992935,467985870,935971740,873699127,749153901,500063449,1882545,3765090,7530180,15060360,30120720,60241440,120482880,240965760,481931520,963863040,929481727,860719101,723193849,448143345,896286690,794329027,590413701,182583049,365166098,730332196,462420039,924840078,851435803,704627253,411010153,822020306,645796259,293348165,586696330,175148307,350296614,700593228,402942103,805884206,613524059,228803765,457607530,915215060,832185767,666127181,334010009,668020018,337795683,675591366,352938379,705876758,413509163,827018326,655792299,313340245,626680490,255116627,510233254,22222155,44444310,88888620,177777240,355554480,711108960,423973567,847947134,697649915,397055477,794110954,589977555,181710757,363421514,726843028,455441703,910883406,823522459,648800565,299356777,598713554,199182755,398365510,796731020,595217687,192191021,384382042,768764084,539283815,80323277,160646554,321293108,642586216,286928079,573856158,149467963,298935926,597871852,197499351,394998702,789997404,581750455,165256557,330513114,661026228,323808103,647616206,296988059,593976118,189707883,379415766,758831532,519418711,40593069,81186138,162372276,324744552,649489104,300733855,601467710,204691067,409382134,818764268,639284183,280324013,560648026,123051699,246103398,492206796,984413592,970582831,942921309,887598265,776952177,555660001,113075649,226151298,452302596,904605192,810966031,623687709,249131065,498262130,996524260,994804167,991363981,984483609,970722865,943201377,888158401,778072449,557900545,117556737,235113474,470226948,940453896,882663439,767082525,535920697,73597041,147194082,294388164,588776328,179308303,358616606,717233212,436222071,872444142,746643931,495043509,990087018,981929683,965615013,932985673,867726993,737209633,476174913,952349826,906455299,814666245,631088137,263931921,527863842,57483331,114966662,229933324,459866648,919733296,841222239,684200125,370155897,740311794,482379235,964758470,931272587,864300821,730357289,462470225,924940450,851636547,705028741,411813129,823626258,649008163,299771973,599543946,200843539,401687078,803374156,608503959,218763565,437527130,875054260,751864167,505483981,12723609,25447218,50894436,101788872,203577744,407155488,814310976,630377599,262510845,525021690,51799027,103598054,207196108,414392216,828784432,659324511,320404669,640809338,283374323,566748646,135252939,270505878,541011756,83779159,167558318,335116636,670233272,342222191,684444382,370644411,741288822,484333291,968666582,939088811,879933269,761622185,525000017,51755681,103511362,207022724,414045448,828090896,657937439,317630525,635261050,272277747,544555494,90866635,181733270,363466540,726933080,455621807,911243614,824242875,650241397,302238441,604476882,210709411,421418822,842837644,687430935,376617517,753235034,508225715,18207077,36414154,72828308,145656616,291313232,582626464,167008575,334017150,668034300,337824247,675648494,353052635,706105270,413966187,827932374,657620395,316996437,633992874,269741395,539482790,80721227,161442454,322884908,645769816,293295279,586590558,174936763,349873526,699747052,401249751,802499502,606754651,215264949,430529898,861059796,723875239,449506125,899012250,799780147,601315941,204387529,408775058,817550116,636855879,275467405,550934810,103625267,207250534,414501068,829002136,659759919,321275485,642550970,286857587,573715174,149185995,298371990,596743980,195243607,390487214,780974428,563704503,129164653,258329306,516658612,35072871,70145742,140291484,280582968,561165936,124087519,248175038,496350076,992700152,987155951,976067549,953890745,909537137,820829921,643415489,288586625,577173250,156102147,312204294,624408588,250572823,501145646,4046939,8093878,16187756,32375512,64751024,129502048,259004096,518008192,37772031,75544062,151088124,302176248,604352496,210460639,420921278,841842556,685440759,372637165,745274330,492304307,984608614,970972875,943701397,889158441,780072529,561900705,125557057,251114114,502228228,6212103,12424206,24848412,49696824,99393648,198787296,397574592,795149184,592054015,185863677,371727354,743454708,488665063,977330126,956415899,914587445,830930537,663616721,328989089,657978178,317712003,635424006,272603659,545207318,92170283,184340566,368681132,737362264,476480175,952960350,907676347,817108341,635972329,273700305,547400610,96556867,193113734,386227468,772454936,546665519,95086685,190173370,380346740,760693480,523142607,48040861,96081722,192163444,384326888,768653776,539063199,79882045,159764090,319528180,639056360,279868367,559736734,121229115,242458230,484916460,969832920,941421487,884598621,770952889,543661425,89078497,178156994,356313988,712627976,427011599,854023198,709802043,421359733,842719466,687194579,376144805,752289610,506334867,14425381,28850762,57701524,115403048,230806096,461612192,923224384,848204415,698164477,398084601,796169202,594094051,189943749,379887498,759774996,521305639,44366925,88733850,177467700,354935400,709870800,421497247,842994494,687744635,377244917,754489834,510735315,23226277,46452554,92905108,185810216,371620432,743240864,488237375,976474750,954705147,911165941,824087529,649930705,301617057,603234114,208223875,416447750,832895500,667546647,336848941,673697882,349151411,698302822,398361291,796722582,595200811,192157269,384314538,768629076,539013799,79783245,159566490,319132980,638265960,278287567,556575134,114905915,229811830,459623660,919247320,840250287,682256221,366268089,732536178,466828003,933656006,869067659,739890965,481537577,963075154,927905955,857567557,716890761,435537169,871074338,743904323,489564293,979128586,960012819,921781285,845318217,692392081,386539809,773079618,547914883,97585413,195170826,390341652,780683304,563122255,128000157,256000314,512000628,25756903,51513806,103027612,206055224,412110448,824220896,650197439,302150525,604301050,210357747,420715494,841430988,684617623,370990893,741981786,485719219,971438438,944632523,891020693,783797033,569349713,140455073,280910146,561820292,125396231,250792462,501584924,4925495,9850990,19701980,39403960,78807920,157615840,315231680,630463360,262682367,525364734,52485115,104970230,209940460,419880920,839761840,681279327,364314301,728628602,459012851,918025702,837807051,677369749,356495145,712990290,427736227,855472454,712700555,427156757,854313514,710382675,422520997,845041994,691839635,385434917,770869834,543495315,88746277,177492554,354985108,709970216,421696079,843392158,688539963,378835573,757671146,517097939,35951525,71903050,143806100,287612200,575224400,152204447,304408894,608817788,219391223,438782446,877564892,756885431,515526509,32808665,65617330,131234660,262469320,524938640,51632927,103265854,206531708,413063416,826126832,654009311,309774269,619548538,240852723,481705446,963410892,928577431,858910509,719576665,440908977,881817954,765391555,532538757,66833161,133666322,267332644,534665288,71086223,142172446,284344892,568689784,139135215,278270430,556540860,114837367,229674734,459349468,918698936,839153519,680062685,361881017,723762034,449279715,898559430,798874507,599504661,200764969,401529938,803059876,607875399,217506445,435012890,870025780,741807207,485370061,970740122,943235891,888227429,778210505,558176657,118108961,236217922,472435844,944871688,891499023,784753693,571263033,144281713,288563426,577126852,156009351,312018702,624037404,249830455,499660910,1077467,2154934,4309868,8619736,17239472,34478944,68957888,137915776,275831552,551663104,105081855,210163710,420327420,840654840,683065327,367886301,735772602,473300851,946601702,894959051,791673749,585103145,171961937,343923874,687847748,377451143,754902286,511560219,24876085,49752170,99504340,199008680,398017360,796034720,593825087,189405821,378811642,757623284,517002215,35760077,71520154,143040308,286080616,572161232,146078111,292156222,584312444,170380535,340761070,681522140,364799927,729599854,460955355,921910710,845577067,692909781,387575209,775150418,552056483,105868613,211737226,423474452,846948904,695653455,393062557,786125114,574005875,149767397,299534794,599069588,199894823,399789646,799579292,600914231,203584109,407168218,814336436,630428519,262612685,525225370,52206387,104412774,208825548,417651096,835302192,672360031,346475709,692951418,387658483,775316966,552389579,106534805,213069610,426139220,852278440,706312527,414380701,828761402,659278451,320312549,640625098,283005843,566011686,133779019,267558038,535116076,71987799,143975598,287951196,575902392,153560431,307120862,614241724,230239095,460478190,920956380,843668407,689092461,379940569,759881138,521517923,44791493,89582986,179165972,358331944,716663888,435083423,870166846,742089339,485934325,971868650,945492947,892741541,787238729,576233105,154221857,308443714,616887428,235530503,471061006,942122012,885999671,773754989,549265625,100286897,200573794,401147588,802295176,606345999,214447645,428895290,857790580,717336807,436429261,872858522,747472691,496701029,993402058,988559763,978875173,959505993,920767633,843290913,688337473,378430593,756861186,515478019,32711685,65423370,130846740,261693480,523386960,48529567,97059134,194118268,388236536,776473072,554701791,111159229,222318458,444636916,889273832,780303311,562362269,126480185,252960370,505920740,13597127,27194254,54388508,108777016,217554032,435108064,870216128,742187903,486131453,972262906,946281459,894318565,790392777,582541201,166838049,333676098,667352196,336460039,672920078,347595803,695191606,392138859,784277718,570311083,142377813,284755626,569511252,140778151,281556302,563112604,127980855,255961710,511923420,25602487,51204974,102409948,204819896,409639792,819279584,640314815,282385277,564770554,131296755,262593510,525187020,52129687,104259374,208518748,417037496,834074992,669905631,341566909,683133818,368023283,736046566,473848779,947697558,897150763,796057173,593869993,189495633,378991266,757982532,517720711,37197069,74394138,148788276,297576552,595153104,192061855,384123710,768247420,538250487,78256621,156513242,313026484,626052968,253861583,507723166,17201979,34403958,68807916,137615832,275231664,550463328,102682303,205364606,410729212,821458424,644672495,291100637,582201274,166158195,332316390,664632780,331021207,662042414,325840475,651680950,305117547,610235094,222225835,444451670,888903340,779562327,560880301,123516249,247032498,494064996,988129992,978015631,957786909,917329465,836414577,674584801,350925249,701850498,405456643,810913286,623582219,248920085,497840170,995680340,993116327,987988301,977732249,957220145,916195937,834147521,670050689,341857025,683714050,369183747,738367494,478490635,956981270,915718187,833192021,668139689,338035025,676070050,353895747,707791494,417338635,834677270,671110187,343976021,687952042,377659731,755319462,512394571,26544789,53089578,106179156,212358312,424716624,849433248,700622143,402999933,805999866,613755379,229266405,458532810,917065620,835886887,673529421,348814489,697628978,397013603,794027206,589810059,181375765,362751530,725503060,452761767,905523534,812802715,627361077,256477801,512955602,27666851,55333702,110667404,221334808,442669616,885339232,772434111,546623869,95003385,190006770,380013540,760027080,521809807,45375261,90750522,181501044,363002088,726004176,453763999,907527998,816811643,635378933,272513513,545027026,91809699,183619398,367238796,734477592,470710831,941421662,884598971,770953589,543662825,89081297,178162594,356325188,712650376,427056399,854112798,709981243,421718133,843436266,688628179,379012005,758024010,517803667,37362981,74725962,149451924,298903848,597807696,197371039,394742078,789484156,580723959,163203565,326407130,652814260,307384167,614768334,231292315,462584630,925169260,852094167,705943981,413643609,827287218,656330083,314415813,628831626,259418899,518837798,39431243,78862486,157724972,315449944,630899888,263555423,527110846,55977339,111954678,223909356,447818712,895637424,793030495,587816637,177388921,354777842,709555684,420867015,841734030,685223707,372203061,744406122,490567891,981135782,964027211,929810069,861375785,724507217,450770081,901540162,804835971,611427589,224610825,449221650,898443300,798642247,599040141,199835929,399671858,799343716,600443079,202641805,405283610,810567220,622890087,247535821,495071642,990143284,982042215,965840077,933435801,868627249,739010145,479775937,959551874,920859395,843474437,688704521,379164689,758329378,518414403,38584453,77168906,154337812,308675624,617351248,236458143,472916286,945832572,893420791,788597229,578950105,159655857,319311714,638623428,279002503,558005006,117765659,235531318,471062636,942125272,886006191,773768029,549291705,100339057,200678114,401356228,802712456,607180559,216116765,432233530,864467060,730689767,463135181,926270362,854296371,710348389,422452425,844904850,691565347,384886341,769772682,541301011,84357669,168715338,337430676,674861352,351478351,702956702,407669051,815338102,632431851,266619349,533238698,68233043,136466086,272932172,545864344,93484335,186968670,373937340,747874680,497505007,995010014,991775675,985306997,972369641,946494929,894745505,791246657,584248961,170253569,340507138,681014276,363784199,727568398,456892443,913784886,829325419,660406485,322568617,645137234,292030115,584060230,169876107,339752214,679504428,360764503,721529006,444813659,889627318,781010283,563776213,129308073,258616146,517232292,36220231,72440462,144880924,289761848,579523696,160803039,321606078,643212156,288179959,576359918,154475483,308950966,617901932,237559511,475119022,950238044,902231735,806219117,614193881,230143409,460286818,920573636,842902919,687561485,376878617,753757234,509270115,20295877,40591754,81183508,162367016,324734032,649468064,300691775,601383550,204522747,409045494,818090988,637937623,277630893,555261786,112279219,224558438,449116876,898233752,798223151,598201949,198159545,396319090,792638180,587032007,175819661,351639322,703278644,408312935,816625870,635007387,271770421,543540842,88837331,177674662,355349324,710698648,423152943,846305886,694367419,390490485,780980970,563717587,129190821,258381642,516763284,35282215,70564430,141128860,282257720,564515440,130786527,261573054,523146108,48047863,96095726,192191452,384382904,768765808,539287263,80330173,160660346,321320692,642641384,287038415,574076830,149909307,299818614,599637228,201030103,402060206,804120412,609996471,221748589,443497178,886994356,775744359,553244365,108244377,216488754,432977508,865955016,733665679,469087005,938174010,878103667,757962981,517681609,37118865,74237730,148475460,296950920,593901840,189559327,379118654,758237308,518230263,38216173,76432346,152864692,305729384,611458768,224673183,449346366,898692732,799141111,600037869,201831385,403662770,807325540,616406727,234569101,469138202,938276404,878308455,758372557,518500761,38757169,77514338,155028676,310057352,620114704,241985055,483970110,967940220,937636087,877027821,755811289,513378225,28512097,57024194,114048388,228096776,456193552,912387104,826529855,654815357,311386361,622772722,247301091,494602182,989204364,980164375,962084397,925924441,853604529,708964705,419685057,839370114,680495875,362747397,725494794,452745235,905490470,812736587,627228821,256213289,512426578,26608803,53217606,106435212,212870424,425740848,851481696,704719039,411193725,822387450,646530547,294816741,589633482,181022611,362045222,724090444,449936535,899873070,801501787,604759221,211274089,422548178,845096356,691948359,385652365,771304730,544365107,90485861,180971722,361943444,723886888,449529423,899058846,799873339,601502325,204760297,409520594,819041188,639838023,281431693,562863386,127482419,254964838,509929676,21614999,43229998,86459996,172919992,345839984,691679968,385115583,770231166,542217979,86191605,172383210,344766420,689532840,380821327,761642654,525040955,51837557,103675114,207350228,414700456,829400912,660557471,322870589,645741178,293238003,586476006,174707659,349415318,698830636,399416919,798833838,599423323,200602293,401204586,802409172,606573991,214903629,429807258,859614516,720984679,443725005,887450010,776655667,555066981,111889609,223779218,447558436,895116872,791989391,585734429,173224505,346449010,692898020,387551687,775103374,551962395,105680437,211360874,422721748,845443496,692642639,387040925,774081850,549919347,101594341,203188682,406377364,812754728,627265103,256285853,512571706,26899059,53798118,107596236,215192472,430384944,860769888,723295423,448346493,896692986,795141619,592038885,185833417,371666834,743333668,488422983,976845966,955447579,912650805,827057257,655870161,313495969,626991938,255739523,511479046,24713739,49427478,98854956,197709912,395419824,790839648,583434943,168625533,337251066,674502132,350759911,701519822,404795291,809590582,620936811,243629269,487258538,974517076,950789799,903335245,808426137,618607921,238971489,477942978,955885956,913527559,828810765,659377177,320510001,641020002,283795651,567591302,136938251,273876502,547753004,97261655,194523310,389046620,778093240,557942127,117639901,235279802,470559604,941119208,883994063,769743773,541243193,84242033,168484066,336968132,673936264,349628175,699256350,400268347,800536694,602829035,207413717,414827434,829654868,661065383,323886413,647772826,297301299,594602598,190960843,381921686,763843372,529442391,60640429,121280858,242561716,485123432,970246864,942249375,886254397,774264441,550284529,102324705,204649410,409298820,818597640,638950927,279657501,559315002,120385651,240771302,481542604,963085208,927926063,857607773,716971193,435698033,871396066,744547779,490851205,981702410,965160467,932076581,865908809,733573265,468902177,937804354,877364355,756484357,514724361,31204369,62408738,124817476,249634952,499269904,295455,590910,1181820,2363640,4727280,9454560,18909120,37818240,75636480,151272960,302545920,605091840,211939327,423878654,847757308,697270263,396296173,792592346,586940339,175636325,351272650,702545300,406846247,813692494,629140635,260036917,520073834,41903315,83806630,167613260,335226520,670453040,342661727,685323454,372402555,744805110,491365867,982731734,967219115,936193877,874143401,750042449,501840545,5436737,10873474,21746948,43493896,86987792,173975584,347951168,695902336,393560319,787120638,575996923,153749493,307498986,614997972,231751591,463503182,927006364,855768375,713292397,428340441,856680882,715117411,431990469,863980938,729717523,461190693,922381386,846518419,694792485,391340617,782681234,567118115,135991877,271983754,543967508,89690663,179381326,358762652,717525304,436806255,873612510,748980667,499716981,1189609,2379218,4758436,9516872,19033744,38067488,76134976,152269952,304539904,609079808,219915263,439830526,879661052,761077751,523911149,49577945,99155890,198311780,396623560,793247120,588249887,178255421,356510842,713021684,427799015,855598030,712951707,427659061,855318122,712391891,426539429,853078858,707913363,417582373,835164746,672085139,345925925,691851850,385459347,770918694,543593035,88941717,177883434,355766868,711533736,424823119,849646238,701048123,403851893,807703786,617163219,236082085,472164170,944328340,890412327,782580301,566916249,135588145,271176290,542352580,86460807,172921614,345843228,691686456,385128559,770257118,542269883,86295413,172590826,345181652,690363304,382482255,764964510,531684667,65124981,130249962,260499924,520999848,43755343,87510686,175021372,350042744,700085488,401926623,803853246,609462139,220679925,441359850,882719700,767195047,536145741,74047129,148094258,296188516,592377032,186509711,373019422,746038844,493833335,987666670,977088987,955933621,913622889,829001425,659758497,321272641,642545282,286846211,573692422,149140491,298280982,596561964,194879575,389759150,779518300,560792247,123340141,246680282,493360564,986721128,975197903,952151453,906058553,813872753,629501153,260757953,521515906,44787459,89574918,179149836,358299672,716599344,434954335,869908670,741572987,484901621,969803242,941362131,884479909,770715465,543186577,88128801,176257602,352515204,705030408,411816463,823632926,649021499,299798645,599597290,200950227,401900454,803800908,609357463,220470573,440941146,881882292,765520231,532796109,67347865,134695730,269391460,538782920,79321487,158642974,317285948,634571896,270899439,541798878,85353403,170706806,341413612,682827224,367410095,734820190,471396027,942792054,887339755,776435157,554625961,111007569,222015138,444030276,888060552,777876751,557509149,116773945,233547890,467095780,934191560,870138767,742033181,485822009,971644018,945043683,891843013,785441673,572638993,147033633,294067266,588134532,178024711,356049422,712098844,425953335,851906670,705568987,412893621,825787242,653330131,308415909,616831818,235419283,470838566,941677132,885109911,771975469,545706585,93168817,186337634,372675268,745350536,492456719,984913438,971582523,944920693,891597033,784949713,571655073,145065793,290131586,580263172,162281991,324563982,649127964,300011575,600023150,201801947,403603894,807207788,616171223,234098093,468196186,936392372,874540391,750836429,503428505,8612657,17225314,34450628,68901256,137802512,275605024,551210048,104175743,208351486,416702972,833405944,668567535,338890717,677781434,357318515,714637030,431029707,862059414,725874475,453504597,907009194,815774035,633303717,268363081,536726162,75207971,150415942,300831884,601663768,205083183,410166366,820332732,642421111,286597869,573195738,148147123,296294246,592588492,186932631,373865262,747730524,497216695,994433390,990622427,983000501,967756649,937268945,876293537,754342721,510441089,22637825,45275650,90551300,181102600,362205200,724410400,450576447,901152894,804061435,609878517,221512681,443025362,886050724,773857095,549469837,100695321,201390642,402781284,805562568,612880783,227517213,455034426,910068852,821893351,645542349,292840345,585680690,173117027,346234054,692468108,386691863,773383726,548523099,98801845,197603690,395207380,790414760,582585167,166925981,333851962,667703924,337163495,674326990,350409627,700819254,403394155,806788310,615332267,232420181,464840362,929680724,861117095,723989837,449735321,899470642,800696931,603149509,208054665,416109330,832218660,666192967,334141581,668283162,338321971,676643942,355043531,710087062,421929771,843859542,689474731,380705109,761410218,524576083,50907813,101815626,203631252,407262504,814525008,630805663,263366973,526733946,55223539,110447078,220894156,441788312,883576624,768908895,539573437,80902521,161805042,323610084,647220168,296195983,592391966,186539579,373079158,746158316,494072279,988144558,978044763,957845173,917445993,836647633,675050913,351857473,703714946,409185539,818371078,638497803,278751253,557502506,116760659,233521318,467042636,934085272,869926191,741608029,484971705,969943410,941642467,885040581,771836809,545429265,92614177,185228354,370456708,740913416,483582479,967164958,936085563,873926773,749609193,500974033,3703713,7407426,14814852,29629704,59259408,118518816,237037632,474075264,948150528,898056703,797869053,597493753,196743153,393486306,786972612,575700871,153157389,306314778,612629556,227014759,454029518,908059036,817873719,637503085,276761817,553523634,108802915,217605830,435211660,870423320,742602287,486960221,973920442,949596531,900948709,803653065,609061777,219879201,439758402,879516804,760789255,523334157,48423961,96847922,193695844,387391688,774783376,551322399,104400445,208800890,417601780,835203560,672162767,346081181,692162362,386080371,772160742,546077131,93909909,187819818,375639636,751279272,504314191,10384029,20768058,41536116,83072232,166144464,332288928,664577856,330911359,661822718,325401083,650802166,303359979,606719958,215195563,430391126,860782252,723320151,448395949,896791898,795339443,592434533,186624713,373249426,746498852,494753351,989506702,980769051,963293749,928343145,858441937,718639521,439034689,878069378,757894403,517544453,36844553,73689106,147378212,294756424,589512848,180781343,361562686,723125372,448006391,896012782,793781211,589318069,180391785,360783570,721567140,444889927,889779854,781315355,564386357,130528361,261056722,522113444,45982535,91965070,183930140,367860280,735720560,473196767,946393534,894542715,790841077,583437801,168631249,337262498,674524996,350805639,701611278,404978203,809956406,621668459,245092565,490185130,980370260,962496167,926747981,855251609,712258865,426273377,852546754,706849155,415453957,830907914,663571475,328898597,657797194,317350035,634700070,271155787,542311574,86378795,172757590,345515180,691030360,383816367,767632734,537021115,75797877,151595754,303191508,606383016,214521679,429043358,858086716,717929079,437613805,875227610,752210867,506177381,14110409,28220818,56441636,112883272,225766544,451533088,903066176,807887999,617531645,236818937,473637874,947275748,896307143,794369933,590495513,182746673,365493346,730986692,463729031,927458062,856671771,715099189,431954025,863908050,729571747,460899141,921798282,845352211,692460069,386675785,773351570,548458787,98673221,197346442,394692884,789385768,580527183,162810013,325620026,651240052,304235751,608471502,218698651,437397302,874794604,751344855,504445357,10646361,21292722,42585444,85170888,170341776,340683552,681367104,364489855,728979710,459715067,919430134,840615915,682987477,367730601,735461202,472678051,945356102,892467851,786691349,575138345,152032337,304064674,608129348,218014343,436028686,872057372,745870391,493496429,986992858,975741363,953238373,908232393,818220433,638196513,278148673,556297346,114350339,228700678,457401356,914802712,831361071,664477789,330711225,661422450,324600547,649201094,300157835,600315670,202386987,404773974,809547948,620851543,243458733,486917466,973834932,949425511,900606669,802968985,607693617,217142881,434285762,868571524,738898695,479553037,959106074,919967795,841691237,685138121,372031889,744063778,489883203,979766406,961288459,924332565,850420777,702597201,406950049,813900098,629555843,260867333,521734666,45224979,90449958,180899916,361799832,723599664,448954975,897909950,797575547,596906741,195569129,391138258,782276516,566308679,134373005,268746010,537492020,76739687,153479374,306958748,613917496,229590639,459181278,918362556,838480759,678717165,359189977,718379954,438515555,877031110,755817867,513391381,28538409,57076818,114153636,228307272,456614544,913229088,828213823,658183293,318122233,636244466,274244579,548489158,98733963,197467926,394935852,789871704,581499055,164753757,329507514,659015028,319785703,639571406,280898459,561796918,125349483,250698966,501397932,4551511,9103022,18206044,36412088,72824176,145648352,291296704,582593408,166942463,333884926,667769852,337295351,674590702,350937051,701874102,405503851,811007702,623771051,249297749,498595498,997190996,996137639,994030925,989817497,981390641,964536929,930829505,863414657,728584961,458925569,917851138,837457923,676671493,355098633,710197266,422150179,844300358,690356363,382468373,764936746,531629139,65013925,130027850,260055700,520111400,41978447,83956894,167913788,335827576,671655152,345065951,690131902,382019451,764038902,529833451,61422549,122845098,245690196,491380392,982760784,967277215,936310077,874375801,750507249,502770145,7295937,14591874,29183748,58367496,116734992,233469984,466939968,933879936,869515519,740786685,483329017,966658034,935071715,871899077,745553801,492863249,985726498,973208643,948172933,898101513,797958673,597672993,197101633,394203266,788406532,578568711,158893069,317786138,635572276,272900199,545800398,93356443,186712886,373425772,746851544,495458735,990917470,983590587,968936821,939629289,881014225,763784097,529323841,60403329,120806658,241613316,483226632,966453264,934662175,871079997,743915641,489586929,979173858,960103363,921962373,845680393,693116433,387988513,775977026,553709699,109175045,218350090,436700180,873400360,748556367,498868381,997736762,997229171,996213989,994183625,990122897,982001441,965758529,933272705,868301057,738357761,478471169,956942338,915640323,833036293,667828233,337412113,674824226,351404099,702808198,407372043,814744086,631243819,264243285,528486570,58728787,117457574,234915148,469830296,939660592,881076831,763909309,529574265,60904177,121808354,243616708,487233416,974466832,950689311,903134269,808024185,617804017,237363681,474727362,949454724,900665095,803085837,607927321,217610289,435220578,870441156,742637959,487031565,974063130,949881907,901519461,804794569,611344785,224445217,448890434,897780868,797317383,596390413,194536473,389072946,778145892,558047431,117850509,235701018,471402036,942804072,887363791,776483229,554722105,111199857,222399714,444799428,889598856,780953359,563662365,129080377,258160754,516321508,34398663,68797326,137594652,275189304,550378608,102512863,205025726,410051452,820102904,641961455,285678557,571357114,144469875,288939750,577879500,157514647,315029294,630058588,261872823,523745646,49246939,98493878,196987756,393975512,787951024,577657695,157071037,314142074,628284148,258323943,516647886,35051419,70102838,140205676,280411352,560822704,123401055,246802110,493604220,987208440,976172527,954100701,909957049,821669745,645095137,291945921,583891842,169539331,339078662,678157324,358070295,716140590,434036827,868073654,737902955,477561557,955123114,912001875,825759397,653274441,308304529,616609058,234973763,469947526,939895052,881545751,764847149,531449945,64655537,129311074,258622148,517244296,36244239,72488478,144976956,289953912,579907824,161571295,323142590,646285180,294326007,588652014,179059675,358119350,716238700,434233047,868466094,738687835,479131317,958262634,918280915,838317477,678390601,358536849,717073698,435903043,871806086,745367819,492491285,984982570,971720787,945197221,892150089,786055825,573867297,149490241,298980482,597960964,197677575,395355150,790710300,583176247,168108141,336216282,672432564,346620775,693241550,388238747,776477494,554710635,111176917,222353834,444707668,889415336,780586319,562928285,127612217,255224434,510448868,22653383,45306766,90613532,181227064,362454128,724908256,451572159,903144318,808044283,617844213,237444073,474888146,949776292,901308231,804372109,610499865,222755377,445510754,891021508,783798663,569352973,140461593,280923186,561846372,125448391,250896782,501793564,5342775,10685550,21371100,42742200,85484400,170968800,341937600,683875200,369506047,739012094,479779835,959559670,920874987,843505621,688766889,379289425,758578850,518913347,39582341,79164682,158329364,316658728,633317456,268390559,536781118,75317883,150635766,301271532,602543064,206841775,413683550,827367100,656489847,314735341,629470682,260697011,521394022,44543691,89087382,178174764,356349528,712699056,427153759,854307518,710370683,422497013,844994026,691743699,385243045,770486090,542727827,87211301,174422602,348845204,697690408,397136463,794272926,590301499,182358645,364717290,729434580,460624807,921249614,844254875,690265397,382286441,764572882,530901411,63558469,127116938,254233876,508467752,18691151,37382302,74764604,149529208,299058416,598116832,197989311,395978622,791957244,585670135,173095917,346191834,692383668,386522983,773045966,547847579,97450805,194901610,389803220,779606440,560968527,123692701,247385402,494770804,989541608,980838863,963433373,928622393,859000433,719756513,441268673,882537346,766830339,535416325,72588297,145176594,290353188,580706376,163168399,326336798,652673596,307102839,614205678,230167003,460334006,920668012,843091671,687938989,377633625,755267250,512290147,26335941,52671882,105343764,210687528,421375056,842750112,687255871,376267389,752534778,506825203,15406053,30812106,61624212,123248424,246496848,492993696,985987392,973730431,949216509,900188665,802132977,606021601,213798849,427597698,855195396,712146439,426048525,852097050,705949747,413655141,827310282,656376211,314508069,629016138,259787923,519575846,40907339,81814678,163629356,327258712,654517424,310790495,621580990,244917627,489835254,979670508,961096663,923948973,849653593,701062833,403881313,807762626,617280899,236317445,472634890,945269780,892295207,786346061,574447769,150651185,301302370,602604740,206965127,413930254,827860508,657476663,316708973,633417946,268591539,537183078,76121803,152243606,304487212,608974424,219704495,439408990,878817980,759391607,520538861,42833369,85666738,171333476,342666952,685333904,372423455,744846910,491449467,982898934,967553515,936862677,875481001,752717649,507190945,16137537,32275074,64550148,129100296,258200592,516401184,34558015,69116030,138232060,276464120,552928240,107612127,215224254,430448508,860897016,723549679,448855005,897710010,797175667,596106981,193969609,387939218,775878436,553512519,108780685,217561370,435122740,870245480,742246607,486248861,972497722,946751091,895257829,792271305,586298257,174352161,348704322,697408644,396572935,793145870,588047387,177850421,355700842,711401684,424559015,849118030,699991707,401739061,803478122,608711891,219179429,438358858,876717716,755191079,512137805,26031257,52062514,104125028,208250056,416500112,833000224,667756095,337267837,674535674,350826995,701653990,405063627,810127254,622010155,245775957,491551914,983103828,967963303,937682253,877120153,755995953,513747553,29250753,58501506,117003012,234006024,468012048,936024096,873803839,749363325,500482297,2720241,5440482,10880964,21761928,43523856,87047712,174095424,348190848,696381696,394519039,789038078,579831803,161419253,322838506,645677012,293109671,586219342,174194331,348388662,696777324,395310295,790620590,582996827,167749301,335498602,670997204,343750055,687500110,376755867,753511734,508779115,19313877,38627754,77255508,154511016,309022032,618044064,237843775,475687550,951375100,904505847,810767341,623290329,248336305,496672610,993345220,988446087,978647821,959051289,919858225,841472097,684699841,371155329,742310658,486376963,972753926,947263499,896282645,794320937,590397521,182550689,365101378,730202756,462161159,924322318,850400283,702556213,406868073,813736146,629227939,260211525,520423050,42601747,85203494,170406988,340813976,681627952,365011551,730023102,461801851,923603702,848963051,699681749,401119145,802238290,606232227,214220101,428440202,856880404,715516455,432788557,865577114,732909875,467575397,935150794,872057235,745870117,493495881,986991762,975739171,953233989,908223625,818202897,638161441,278078529,556157058,114069763,228139526,456279052,912558104,826871855,655499357,312754361,625508722,252773091,505546182,12848011,25696022,51392044,102784088,205568176,411136352,822272704,646301055,294357757,588715514,179186675,358373350,716746700,435249047,870498094,742751835,487259317,974518634,950792915,903341477,808438601,618632849,239021345,478042690,956085380,913926407,829608461,660972569,323700785,647401570,296558787,593117574,187990795,375981590,751963180,505682007,13119661,26239322,52478644,104957288,209914576,419829152,839658304,681072255,363900157,727800314,457356275,914712550,831180747,664117141,329989929,659979858,321715363,643430726,288617099,577234198,156224043,312448086,624896172,251547991,503095982,7947611,15895222,31790444,63580888,127161776,254323552,508647104,19049855,38099710,76199420,152398840,304797680,609595360,220946367,441892734,883785468,769326583,540408813,82573273,165146546,330293092,660586184,322928015,645856030,293467707,586935414,175626475,351252950,702505900,406767447,813534894,628825435,259406517,518813034,39381715,78763430,157526860,315053720,630107440,261970527,523941054,49637755,99275510,198551020,397102040,794204080,590163807,182083261,364166522,728333044,458421735,916843470,835442587,672640821,347037289,694074578,389904803,779809606,561374859,124505365,249010730,498021460,996042920,993841487,989438621,980632889,963021425,927798497,857352641,716460929,434677505,869355010,740465667,482686981,965373962,932503571,866762789,735281225,472318097,944636194,891028035,783811717,569379081,140513809,281027618,562055236,125866119,251732238,503464476,8684599,17369198,34738396,69476792,138953584,277907168,555814336,113384319,226768638,453537276,907074552,815904751,633565149,268885945,537771890,77299427,154598854,309197708,618395416,238546479,477092958,954185916,910127479,822010605,645776857,293309361,586618722,174993091,349986182,699972364,401700375,803400750,608557147,218869941,437739882,875479764,752715175,507185997,16127641,32255282,64510564,129021128,258042256,516084512,33924671,67849342,135698684,271397368,542794736,87345119,174690238,349380476,698760952,399277551,798555102,598865851,199487349,398974698,797949396,597654439,197064525,394129050,788258100,578271847,158299341,316598682,633197364,268150375,536300750,74357147,148714294,297428588,594857176,191469999,382939998,765879996,533515639,68786925,137573850,275147700,550295400,102346447,204692894,409385788,818771576,639298799,280353245,560706490,123168627,246337254,492674508,985349016,972453679,946663005,895081657,791918961,585593569,172942785,345885570,691771140,385297927,770595854,542947355,87650357,175300714,350601428,701202856,404161359,808322718,618401083,238557813,477115626,954231252,910218151,822191949,646139545,294034737,588069474,177894595,355789190,711578380,424912407,849824814,701405275,404566197,809132394,620020435,241796517,483593034,967186068,936127783,874011213,749778073,501311793,4379233,8758466,17516932,35033864,70067728,140135456,280270912,560541824,122839295,245678590,491357180,982714360,967184367,936124381,874004409,749764465,501284577,4324801,8649602,17299204,34598408,69196816,138393632,276787264,553574528,108904703,217809406,435618812,871237624,744230895,490217437,980434874,962625395,927006437,855768521,713292689,428341025,856682050,715119747,431995141,863990282,729736211,461228069,922456138,846667923,695091493,391938633,783877266,569510179,140776005,281552010,563104020,127963687,255927374,511854748,25465143,50930286,101860572,203721144,407442288,814884576,631524799,264805245,529610490,60976627,121953254,243906508,487813016,975626032,953007711,907771069,817297785,636351217,274458081,548916162,99587971,199175942,398351884,796703768,595163183,192082013,384164026,768328052,538411751,78579149,157158298,314316596,628633192,259022031,518044062,37843771,75687542,151375084,302750168,605500336,212756319,425512638,851025276,703806199,409368045,818736090,639227827,280211301,560422602,122600851,245201702,490403404,980806808,963369263,928494173,858743993,719243633,440242913,880485826,762727299,527210245,56176137,112352274,224704548,449409096,898818192,799392031,600539709,202835065,405670130,811340260,624436167,250627981,501255962,4267571,8535142,17070284,34140568,68281136,136562272,273124544,546249088,94253823,188507646,377015292,754030584,509816815,21389277,42778554,85557108,171114216,342228432,684456864,370669375,741338750,484433147,968866294,939488235,880732117,763219881,528195409,58146465,116292930,232585860,465171720,930343440,862442527,726640701,455037049,910074098,821903843,645563333,292882313,585764626,173284899,346569798,693139596,388034839,776069678,553895003,109545653,219091306,438182612,876365224,754486095,510727837,23211321,46422642,92845284,185690568,371381136,742762272,487280191,974560382,950876411,903508469,808772585,619300817,240357281,480714562,961429124,924613895,850983437,703722521,409200689,818401378,638558403,278872453,557744906,117245459,234490918,468981836,937963672,877682991,757121629,515998905,33753457,67506914,135013828,270027656,540055312,81866271,163732542,327465084,654930168,311615983,623231966,248219579,496439158,992878316,987512279,976780205,955316057,912387761,826531169,654817985,311391617,622783234,247322115,494644230,989288460,980332567,962420781,926597209,854950065,711655777,425067201,850134402,702024451,405804549,811609098,624973843,251703333,503406666,8568979,17137958,34275916,68551832,137103664,274207328,548414656,98584959,197169918,394339836,788679672,579114991,159985629,319971258,639942516,281640679,563281358,128318363,256636726,513273452,28302551,56605102,113210204,226420408,452840816,905681632,813118911,627993469,257742585,515485170,32725987,65451974,130903948,261807896,523615792,48987231,97974462,195948924,391897848,783795696,569347039,140449725,280899450,561798900,125353447,250706894,501413788,4583223,9166446,18332892,36665784,73331568,146663136,293326272,586652544,175060735,350121470,700242940,402241527,804483054,610721755,223199157,446398314,892796628,787348903,576453453,154662553,309325106,618650212,239056071,478112142,956224284,914204215,830164077,662083801,325923249,651846498,305448643,610897286,223550219,447100438,894200876,790157399,582070445,165896537,331793074,663586148,328927943,657855886,317467419,634934838,271625323,543250646,88256939,176513878,353027756,706055512,413866671,827733342,657222331,316200309,632400618,266556883,533113766,67983179,135966358,271932716,543865432,89486511,178973022,357946044,715892088,433539823,867079646,735914939,473585525,947171050,896097747,793951141,589657929,181071505,362143010,724286020,450327687,900655374,803066395,607888437,217532521,435065042,870130084,742015815,485787277,971574554,944904755,891565157,784885961,571527569,144810785,289621570,579243140,160241927,320483854,640967708,283691063,567382126,136519899,273039798,546079596,93914839,187829678,375659356,751318712,504393071,10541789,21083578,42167156,84334312,168668624,337337248,674674496,351104639,702209278,406174203,812348406,626452459,254660565,509321130,20397907,40795814,81591628,163183256,326366512,652733024,307221695,614443390,230642427,461284854,922569708,846895063,695545773,392847193,785694386,573144419,148044485,296088970,592177940,186111527,372223054,744446108,490647863,981295726,964347099,930449845,862655337,727066321,455888289,911776578,825308803,652373253,306502153,613004306,227764259,455528518,911057036,823869719,649495085,300745817,601491634,204738915,409477830,818955660,639666967,281089581,562179162,126113971,252227942,504455884,10667415,21334830,42669660,85339320,170678640,341357280,682714560,367184767,734369534,470494715,940989430,883734507,769224661,540204969,82165585,164331170,328662340,657324680,316405007,632810014,267375675,534751350,71258347,142516694,285033388,570066776,141889199,283778398,567556796,136869239,273738478,547476956,96709559,193419118,386838236,773676472,549108591,99972829,199945658,399891316,799782632,601320911,204397469,408794938,817589876,636935399,275626445,551252890,104261427,208522854,417045708,834091416,669938479,341632605,683265210,368286067,736572134,474899915,949799830,901355307,804466261,610688169,223131985,446263970,892527940,786811527,575378701,152513049,305026098,610052196,221860039,443720078,887440156,776635959,555027565,111810777,223621554,447243108,894486216,790728079,583211805,168179257,336358514,672717028,347189703,694379406,390514459,781028918,563813483,129382613,258765226,517530452,36816551,73633102,147266204,294532408,589064816,179885279,359770558,719541116,440837879,881675758,765107163,531969973,65695593,131391186,262782372,525564744,52885135,105770270,211540540,423081080,846162160,694079967,389915581,779831162,561417971,124591589,249183178,498366356,996732712,995221071,992197789,986151225,974058097,949871841,901499329,804754305,611264257,224284161,448568322,897136644,796028935,593813517,189382681,378765362,757530724,516817095,35389837,70779674,141559348,283118696,566237392,134230431,268460862,536921724,75599095,151198190,302396380,604792760,211341167,422682334,845364668,692484983,386725613,773451226,548658099,99071845,198143690,396287380,792574760,586905167,175565981,351131962,702263924,406283495,812566990,626889627,255534901,511069802,23895251,47790502,95581004,191162008,382324016,764648032,531051711,63859069,127718138,255436276,510872552,23500751,47001502,94003004,188006008,376012016,752024032,505803711,13363069,26726138,53452276,106904552,213809104,427618208,855236416,712228479,426212605,852425210,706606067,414967781,829935562,661626771,325009189,650018378,301792403,603584806,208925259,417850518,835701036,673157719,348071085,696142170,394039987,788079974,577915595,157586837,315173674,630347348,262450343,524900686,51557019,103114038,206228076,412456152,824912304,651580255,304916157,609832314,221420275,442840550,885681100,773117847,547991341,97738329,195476658,390953316,781906632,565568911,132893469,265786938,531573876,64903399,129806798,259613596,519227192,40210031,80420062,160840124,321680248,643360496,288476639,576953278,155662203,311324406,622648812,247053271,494106542,988213084,978181815,958119277,917994201,837744049,677243745,356243137,712486274,426728195,853456390,708668427,419092501,838185002,678125651,358006949,716013898,433783443,867566886,736889419,475534485,951068970,903893587,809542821,620841289,243438225,486876450,973752900,949261447,900278541,802312729,606381105,214517857,429035714,858071428,717898503,437552653,875105306,751966259,505688165,13131977,26263954,52527908,105055816,210111632,420223264,840446528,682648703,367053053,734106106,469967859,939935718,881627083,765009813,531775273,65306193,130612386,261224772,522449544,46654735,93309470,186618940,373237880,746475760,494707167,989414334,980584315,962924277,927604201,856964049,715683745,433123137,866246274,734248195,470252037};

:::: tree.cpp

梦到哪句说哪句

query.cpp ::::info[复制了pdf]

/*CCF 全国青少年信息学奥林匹克联赛
CCF NOIP 2025
时间：2025 年 11 月 29 日 08:30 ～ 13:00
题目名称 糖果店 清仓甩卖 树的价值 序列询问
题目类型 传统型 传统型 传统型 传统型
目录 candy sale tree query
可执行文件名 candy sale tree query
输入文件名 candy.in sale.in tree.in query.in
输出文件名 candy.out sale.out tree.out query.out
每个测试点时限 1.0 秒 1.0 秒 2.0 秒 2.0 秒
内存限制 512 MiB 512 MiB 512 MiB 512 MiB
测试点数目 20 25 25 20
测试点是否等分 是 是 是 是
提交源程序文件名
对于 C++ 语言 candy.cpp sale.cpp tree.cpp query.cpp
编译选项
对于 C++ 语言 ‐O2 ‐std=c++14 ‐static
注. 意. 事. 项（. 请. 仔. 细. 阅. 读）.
1. 文件名（程序名和输入输出文件名）必须使用英文小写。
2. main 函数的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末换行）。
4. 选手提交的程序源文件大小不得超过 100 KiB。
5. 提交的程序源文件的放置位置请参考各省的具体要求。
6. 程序可使用的栈空间内存限制与题目的内存限制一致。
7. 禁止在源代码中改变编译器参数（如使用 #pragma 命令），禁止使用系统结构相
关指令（如内联汇编）或其他可能造成不公平的方法。
8. 因违反上述规定而出现的问题，申诉时一律不予受理。
9. 只提供 Linux 格式附加样例文件。
10. 全国统一评测时采用的机器配置为：Intel Core Ultra 9 285K CPU @ 3.70 GHz
（关闭睿频与能效核），内存 96 GB。上述时限以此配置为准。
11. 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准。
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 糖果店（candy）
糖果店（candy）
【题目描述】
小 X 开了一家糖果店，售卖 n 种糖果，每种糖果均有无. 限. 颗。对于不同种类的糖
果，小 X 采用了不同的促销策略。具体地，对于第 i (1 ≤ i ≤ n) 种糖果，购买第一颗
的价格为 xi 元，第二颗为 yi 元，第三颗又变回 xi 元，第四颗则为 yi 元，以此类推。
小 R 带了 m 元钱买糖果。小 R 不关心糖果的种类，只想得到数量尽可能多的糖
果。你需要帮助小 R 求出，m 元钱能购买的糖果数量的最大值。
【输入格式】
从文件 candy.in 中读入数据。
输入的第一行包含两个正整数 n, m，代表糖果的种类数和小 R 的钱数。
输入的第 i + 1 (1 ≤ i ≤ n) 行包含两个正整数 xi
, yi，分别表示购买第 i 种糖果时第
奇数颗的价格和第偶数颗的价格。
【输出格式】
输出到文件 candy.out 中。
输出一行一个非负整数，表示 m 元钱能购买的糖果数量的最大值。
【样例 1 输入】
1 2 10
2 4 1
3 3 3
【样例 1 输出】
1 4
【样例 1 解释】
小 R 可以购买 4 颗第一种糖果，共花费 4 + 1 + 4 + 1 = 10 元。
第 2 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 糖果店（candy）
【样例 2 输入】
1 3 15
2 1 7
3 2 3
4 3 1
【样例 2 输出】
1 8
小 R 可以购买 1 颗第一种糖果、1 颗第二种糖果与 6 颗第三种糖果，共花费 1 +
2 + 12 = 15 元。
【样例 3】
见选手目录下的 candy/candy3.in 与 candy/candy3.ans。
该样例满足测试点 6 的约束条件。
【样例 4】
见选手目录下的 candy/candy4.in 与 candy/candy4.ans。
该样例满足测试点 8, 9 的约束条件。
【样例 5】
见选手目录下的 candy/candy5.in 与 candy/candy5.ans。
该样例满足测试点 11, 12 的约束条件。
【样例 6】
见选手目录下的 candy/candy6.in 与 candy/candy6.ans。
该样例满足测试点 13 的约束条件。
【样例 7】
见选手目录下的 candy/candy7.in 与 candy/candy7.ans。
该样例满足测试点 17, 18 的约束条件。
第 3 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 糖果店（candy）
【数据范围】
对于所有测试数据，均有：
? 1 ≤ n ≤ 105；
? 1 ≤ m ≤ 1018；
? 对于所有 1 ≤ i ≤ n，均有 1 ≤ xi
, yi ≤ 109。
测试点编号 n ≤ m ≤ 特殊性质
1 1 10
2, 3 2 无
20
4, 5 10
6
102 102
A
7 B
8, 9 无
10
103 104
A
11, 12 B
13 无
14
105
109
A
15, 16 B
17, 18 无
19, 20 1018
特殊性质 A：对于所有 1 ≤ i ≤ n，均有 xi = yi。
特殊性质 B：对于所有 1 ≤ i ≤ n，均有 xi ≥ yi。
第 4 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 清仓甩卖（sale）
清仓甩卖（sale）
【题目描述】
小 X 的糖果促销策略很成功，现在糖果店只剩下了 n 颗糖果，其中第 i (1 ≤ i ≤ n)
颗糖果的原价为 ai 元。小 X 计划将它们全部重新定价，清仓甩卖。具体地，小 X 会
将每颗糖果的清仓价格分别定为 1 元或 2 元。设第 i (1 ≤ i ≤ n) 颗糖果的清仓价格为
wi ∈ {1, 2} 元，则它的性. 价. 比. 被定义为原价与清仓价格的比值，即 ai
wi。
小 R 又带了 m 元钱买糖果。这一次，小 R 希望他购买到的糖果的原价总和最大，
于是他采用了以下购买策略：将所有糖果按照性. 价. 比. 从. 大. 到. 小. 排. 序. ，然后依次考虑每一
颗糖果。具体地，若小 R 在考虑第 i (1 ≤ i ≤ n) 颗糖果时剩余的钱至少为 wi 元，则他
会购买这颗糖果，否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果
的性价比相同，则小 R 会先考虑原. 价. 较. 高. 的糖果；若存在两颗糖果的性价比与原价均
相同，则小 R 会先考虑编号较小的糖果。
例如，若小 X 的糖果商店剩余 3 颗糖果，原价分别为 a1 = 1，a2 = 3，a3 = 5，而
清仓价格分别为 w1 = w2 = 1，w3 = 2，则性价比分别为 1, 3,
5
2。因此小 R 会先考虑第
2 颗糖果，然后考虑第 3 颗糖果，最后考虑第 1 颗糖果。
小 R 想知道，在小 X 的所有 2
n 种定价方案中，有多少种定价方案使得他按照上述
购买策略能购买到的糖果的原. 价. 总. 和. 最. 大. 。你需要帮助小 R 求出满足要求的定价方案
的数量。由于答案可能较大，你只需要求出答案对 998, 244, 353 取模后的结果。
【输入格式】
从文件 sale.in 中读入数据。
本. 题. 包. 含. 多. 组. 测. 试. 数. 据. 。
输入的第一行包含两个非负整数 c, t，分别表示测试点编号与测试数据组数。c = 0
表示该测试点为样例。
接下来依次输入每组测试数据，对于每组测试数据：
? 第一行包含两个正整数 n, m，分别表示糖果的数量与小 R 的钱数。
? 第二行包含 n 个正整数 a1, a2, . . . , an，分别表示每颗糖果的原价。
【输出格式】
输出到文件 sale.out 中。
对于每组测试数据，输出一行一个非负整数，表示使得小 R 购买到的糖果的原价
总和达到最大值的定价方案数对 998, 244, 353 取模后的结果。
【样例 1 输入】
第 5 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 清仓甩卖（sale）
1 0 1
2 3 2
3 1 3 5
【样例 1 输出】
1 6
【样例 1 解释】
该样例即为【题目描述】中的例子。共有以下 6 种定价方案使得小 R 购买到的糖
果原价总和最大，分别为：
? w1 = w2 = w3 = 1，小 R 购买到的糖果原价总和为 8；
? w1 = w3 = 1，w2 = 2，小 R 购买到的糖果原价总和为 6；
? w1 = 1，w2 = w3 = 2，小 R 购买到的糖果原价总和为 5；
? w2 = w3 = 1，w1 = 2，小 R 购买到的糖果原价总和为 8；
? w3 = 1，w1 = w2 = 2，小 R 购买到的糖果原价总和为 5；
? w1 = w2 = w3 = 2，小 R 购买到的糖果原价总和为 5。
注意：若 w1 = w2 = 1，w3 = 2，则小 R 会依次购买第 2 颗和第 1 颗糖果，原价总
和为 4，但小 R 可以只购买第 3 颗糖果，原价总和为 5。因此该定价方案无法使小 R 购
买到的糖果的原价总和达到最大值。
【样例 2】
见选手目录下的 sale/sale2.in 与 sale/sale2.ans。
该样例满足测试点 1 ～ 3 的约束条件。
【样例 3】
见选手目录下的 sale/sale3.in 与 sale/sale3.ans。
该样例满足测试点 4, 5 的约束条件。
【样例 4】
见选手目录下的 sale/sale4.in 与 sale/sale4.ans。
该样例满足测试点 7 ～ 9 的约束条件。
第 6 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 清仓甩卖（sale）
【样例 5】
见选手目录下的 sale/sale5.in 与 sale/sale5.ans。
该样例满足测试点 10 ～ 12 的约束条件。
【样例 6】
见选手目录下的 sale/sale6.in 与 sale/sale6.ans。
该样例满足测试点 13 的约束条件。
【样例 7】
见选手目录下的 sale/sale7.in 与 sale/sale7.ans。
该样例满足测试点 14, 15 的约束条件。
【样例 8】
见选手目录下的 sale/sale8.in 与 sale/sale8.ans。
该样例满足测试点 17 的约束条件。
【样例 9】
见选手目录下的 sale/sale9.in 与 sale/sale9.ans。
该样例满足测试点 19, 20 的约束条件。
【样例 10】
见选手目录下的 sale/sale10.in 与 sale/sale10.ans。
该样例满足测试点 21 ～ 23 的约束条件。
【样例 11】
见选手目录下的 sale/sale11.in 与 sale/sale11.ans。
该样例满足测试点 24, 25 的约束条件。
【数据范围】
设 N 为单个测试点内所有测试数据的 n 的和。对于所有测试数据，均有：
? 1 ≤ t ≤ 5 × 104
；
? 1 ≤ n ≤ 5, 000，N ≤ 5 × 104，1 ≤ m ≤ 2n ? 1；
? 对于所有 1 ≤ i ≤ n，均有 1 ≤ ai ≤ 109。
第 7 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 清仓甩卖（sale）
测试点编号 n ≤ N ≤ m 特殊性质
1 ～ 3 5
5, 000
≤ 2n ? 1
无
4, 5 10
6 40
7 ～ 9
300
= 2
10 ～ 12
≤ 2n ? 1
B
13
无
14, 15
103 104
= 2
16 = 2n ? 1
17 = 2n ? 2
18
≤ 2n ? 1
A
19, 20 B
21 ～ 23 无
24, 25 5, 000 5 × 104
特殊性质 A：a1 = a2 = · · · = an。
特殊性质 B：对于所有 1 ≤ i ≤ n, 均有 ai > 5 × 108。
第 8 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 树的价值（tree）
树的价值（tree）
【题目描述】
给定一棵 n 个结点的有根树，其中结点 1 为根，结点 i (2 ≤ i ≤ n) 的父亲结点为
结点 pi。
对于 1 ≤ i ≤ n，定义结点 i 的深. 度.
di 为结点 1 到结点 i 的简单路径的边. 数. ，也就
是说，d1 = 0，di = dpi + 1 (2 ≤ i ≤ n)。定义有根树的高. 度.
h 为所有结点的深. 度. 的. 最. 大.
值. ，即 h = maxn
i=1 di。
给定高度的上界 m。在本题中，给. 定. 的. 有. 根. 树. 的. 高. 度. 不. 超. 过. m。
你需要给每个结点设置一个非. 负. 整. 数. 作为它的权. 值. 。对于 1 ≤ i ≤ n，若结点 i 的权
值为 ai，令 Si 表示结点 i 的子. 树. 中结点权值构成的集合。对于每一种权值设置方案，定
义树的价. 值. 为
∑n
i=1
mex(Si)，其中 mex(S) 表示不. 在. 集合 S 中的最. 小. 非. 负. 整. 数. 。例如，在
下图中，若设置 a1 = 3，a2 = 2，a3 = a4 = 0，a5 = 1，则 S1 = {0, 1, 2, 3}，S2 = {0, 1, 2}，
S3 = {0}，S4 = {0}，S5 = {1}，树的价值为 4 + 3 + 1 + 1 + 0 = 9。
1
2 3
4 5
你需要求出，在所有权值设置方案中，树的价值的最大值。
【输入格式】
从文件 tree.in 中读入数据。
本. 题. 包. 含. 多. 组. 测. 试. 数. 据。.
输入的第一行包含一个正整数 t，表示测试数据组数。
接下来依次输入每组测试数据，对于每组测试数据：
? 第一行包含两个正整数 n, m，分别表示结点数量与高度的上界。
? 第二行包含 n ? 1 个正整数 p2, p3, . . . , pn，分别表示每个结点的父亲结点。
【输出格式】
输出到文件 tree.out 中。
第 9 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 树的价值（tree）
对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。
【样例 1 输入】
1 2
2 5 2
3 1 1 2 2
4 7 2
5 1 1 2 2 2 3
【样例 1 输出】
1 9
2 13
【样例 1 解释】
该样例共包含两组测试数据。
对于第一组测试数据，可以设置 a1 = 3，a2 = 2，a3 = a4 = 0，a5 = 1，则树的价值
为 4 + 3 + 1 + 1 + 0 = 9。
对于第二组测试数据，可以设置 a1 = 4，a2 = 3，a4 = 2，a3 = a6 = 1，a5 = a7 = 0，
则树的价值为 5 + 4 + 2 + 0 + 1 + 0 + 1 = 13。
【样例 2】
见选手目录下的 tree/tree2.in 与 tree/tree2.ans。
该样例满足测试点 3, 4 的约束条件。
【样例 3】
见选手目录下的 tree/tree3.in 与 tree/tree3.ans。
该样例满足测试点 7, 8 的约束条件。
【样例 4】
见选手目录下的 tree/tree4.in 与 tree/tree4.ans。
该样例满足测试点 13, 14 的约束条件。
第 10 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 树的价值（tree）
【样例 5】
见选手目录下的 tree/tree5.in 与 tree/tree5.ans。
该样例满足测试点 18, 19 的约束条件。
【数据范围】
对于所有测试数据，均有：
? 1 ≤ t ≤ 5；
? 2 ≤ n ≤ 8, 000，1 ≤ m ≤ min(n ? 1, 800)；
? 对于所有 2 ≤ i ≤ n，均有 1 ≤ pi ≤ i ? 1；
? 给定的有根树的高度不超过 m。
测试点编号 n ≤ m ≤
1, 2 7
n ? 1
3, 4 13
5, 6 18
7, 8 40
9, 10 120
11, 12 360
13, 14
4, 000
2
15 ～ 17 10
18, 19 50
20 ～ 25 8, 000 800
第 11 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 序列询问（query）
序列询问（query）
【题目描述】
给定一个长度为 n 的整数序列 a1, a2, . . . , an。
有 q 次询问，其中第 j (1 ≤ j ≤ q) 次询问将会给出 Lj
, Rj (1 ≤ Lj ≤ Rj ≤ n)。定义
区间 [l, r] (1 ≤ l ≤ r ≤ n) 是极. 好. 的. ，当且仅当区间 [l, r] 的长度在 [Lj
, Rj
] 内，即 Lj ≤
r?l+1 ≤ Rj。定义区间 [l, r] (1 ≤ l ≤ r ≤ n) 的权. 值. 为
∑r
i=l
ai。对于所有 i = 1, 2, . . . , n，
求出所有包. 含.
i 的极好区间的最大权值，即 max1≤l≤i≤r≤n{
∑r
i=l
ai
| Lj ≤ r?l+ 1 ≤ Rj}。
【输入格式】
从文件 query.in 中读入数据。
输入的第一行包含一个正整数 n，表示序列长度。
输入的第二行包含 n 个整数 a1, a2, . . . , an。
输入的第三行包含一个正整数 q，表示询问次数。
输入的第 j + 3 (1 ≤ j ≤ q) 行包含两个正整数 Lj
, Rj，表示第 j 次询问。
【输出格式】
输出到文件 query.out 中。
对于每次询问，设包含 i (1 ≤ i ≤ n) 的极好区间的最大权值为 ki，输出一行一个
非负整数，表示 ⊕n
i=1 ((i × ki) mod 2
64)，其中 ⊕ 表示二. 进. 制. 按. 位. 异. 或. 。注意：对于任
意整. 数.
x，存在唯. 一. 的. 非. 负. 整. 数.
x
′ 满足 x
′ ≡ x (mod 2
64) 且 0 ≤ x
′ ≤ 2
64 ? 1，则记
x mod 2
64 = x
′。
【样例 1 输入】
1 4
2 2 4 ‐5 1
3 3
4 1 2
5 3 4
6 1 4
【样例 1 输出】
1 18446744073709551603
2 8
第 12 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 序列询问（query）
3 4
【样例 1 解释】
对于第 1 次询问：
? 包含 1 的极好区间为 [1, 1] 和 [1, 2]，权值分别为 2, 6；
? 包含 2 的极好区间为 [1, 2]，[2, 2] 和 [2, 3]，权值分别为 6, 4, ?1；
? 包含 3 的极好区间为 [2, 3]，[3, 3] 和 [3, 4]，权值分别为 ?1, ?5, ?4；
? 包含 4 的极好区间为 [3, 4] 和 [4, 4]，权值分别为 ?4, 1。
因此 k1 = 6，k2 = 6，k3 = ?1，k4 = 1。
对于第 2 次询问，k1 = 2，k2 = 2，k3 = 2，k4 = 2。
对于第 3 次询问，k1 = 6，k2 = 6，k3 = 2，k4 = 2。
【样例 2】
见选手目录下的 query/query2.in 与 query/query2.ans。
该样例满足测试点 2, 3 的约束条件。
【样例 3】
见选手目录下的 query/query3.in 与 query/query3.ans。
该样例满足测试点 4 的约束条件。
【样例 4】
见选手目录下的 query/query4.in 与 query/query4.ans。
该样例满足测试点 6, 7 的约束条件。
【样例 5】
见选手目录下的 query/query5.in 与 query/query5.ans。
该样例满足测试点 8 ～ 10 的约束条件。
【样例 6】
见选手目录下的 query/query6.in 与 query/query6.ans。
该样例满足测试点 11, 12 的约束条件。
第 13 页 共 14 页
CCF 全国青少年信息学奥林匹克联赛 CCF NOIP 2025 序列询问（query）
【样例 7】
见选手目录下的 query/query7.in 与 query/query7.ans。
该样例满足测试点 13 的约束条件。
【样例 8】
见选手目录下的 query/query8.in 与 query/query8.ans。
该样例满足测试点 16 ～ 20 的约束条件。
【数据范围】
对于所有测试数据，均有：
? 1 ≤ n ≤ 5 × 104，1 ≤ q ≤ 1, 024；
? 对于所有 1 ≤ i ≤ n，均有 |ai
| ≤ 105；
? 对于所有 1 ≤ j ≤ q，均有 1 ≤ Lj ≤ Rj ≤ n。
测试点编号 n ≤ q ≤ 特殊性质
1 103 1
无
2, 3 3, 000 50
4 104 128
5 3 × 104 512
6, 7
5 × 104
1, 024 A
8 ～ 10
512
B
11, 12 C
13
1, 024
D
14, 15 E
16 ～ 20 无
特殊性质 A：对于所有 1 ≤ j ≤ q，均有 Lj = Rj。
特殊性质 B：对于所有 1 ≤ j ≤ q，均有 Rj ≤ 32。
特殊性质 C：对于所有 1 ≤ j ≤ q，均有 Lj ≤ 16 且 Rj ≥ n ? 1000。
特殊性质 D：对于所有 1 ≤ j ≤ q，均有 Lj > n/2。
特殊性质 E：对于所有 1 ≤ j ≤ q，均有 Lj > n/4。
第 14 页 共 14 页
*/

::::

SN-229 jdfz英才部

candy.cpp

/*
先找到总和最优的，再寻找每一组第一个小于等于最优总和的一半，即可求出最优解。
为啥不对？？？ 
但是对于原x,y来说，若我们选o(奇数)个i种糖果，花费总和为o/2*(x+y)+x，
平均下来小于上文认为的最优解，也就是我们此文式子的最优解。
对于第i种糖果，选s_i个，总花费m>=sum{s_i/2*(x_i+y_i)+(o_i%2)*x} 
一定对于上文的最优情况：
1.非：
    s_i为奇数；
2.是：
    s_i随意；
则有m>=sum{s_i/2*(x_i+y_i)}+sum{x_i}(i为上文中的更改后的最优解) 
好像第一个更对一些？？？ 
因为平均下来其实只选一个平均值一定是最优的。
额。。。
白写了 
终于对了
居然要回溯一个才行
——10:23 
*/

sale.cpp

/*
666
题看错了，该方案的答案最大，不是所有方案的最大答案次数，本以为这道题挺简单的。
www T~T
——12:16 
*/

tree.cpp

/*
本以为做出来了，没想到只是NOIP爆0前的幻想。
交大附中英才部，我爱你。 
——12：48 
*/

query.cpp

/*
打完线段树运行样例2后发现T炸了，再也不喜欢写线段树了。
怎么一分暴力都不想给啊！？？
唉ε=(′ο｀*)))
——11:50 
*/

后言

果然神人总是压轴出场的

笔者注:压轴指倒数第二出场的，倒数第一出场称为大轴