#981040 (C90) No.2752 文字列の数え上げ mod 998244353

• 問題: No.2752 文字列の数え上げ mod 998244353
• ユーザー: tails
• 提出日時: 2024-05-11 00:04:25
• 言語: C90 (gcc 11.4.0)
• 結果: AC
• 実行時間: 8 ms / 2,000 ms
• コード長: 9,462 bytes
• コンパイル時間: 218 ms
• コンパイル使用メモリ: 24,832 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-12-20 08:02:44
• 合計ジャッジ時間: 1,422 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,820 KB
testcase_01	AC	0 ms; 6,816 KB
testcase_02	AC	1 ms; 6,820 KB
testcase_03	AC	0 ms; 6,820 KB
testcase_04	AC	1 ms; 6,820 KB
testcase_05	AC	0 ms; 6,816 KB
testcase_06	AC	1 ms; 6,820 KB
testcase_07	AC	1 ms; 6,816 KB
testcase_08	AC	1 ms; 6,816 KB
testcase_09	AC	0 ms; 6,816 KB
testcase_10	AC	0 ms; 6,816 KB
testcase_11	AC	0 ms; 6,816 KB
testcase_12	AC	1 ms; 6,816 KB
testcase_13	AC	1 ms; 6,820 KB
testcase_14	AC	1 ms; 6,820 KB
testcase_15	AC	0 ms; 6,816 KB
testcase_16	AC	0 ms; 6,820 KB
testcase_17	AC	1 ms; 6,816 KB
testcase_18	AC	1 ms; 6,816 KB
testcase_19	AC	0 ms; 6,816 KB
testcase_20	AC	4 ms; 6,820 KB
testcase_21	AC	7 ms; 6,820 KB
testcase_22	AC	8 ms; 6,820 KB
testcase_23	AC	7 ms; 6,816 KB
testcase_24	AC	7 ms; 6,820 KB

コンパイルメッセージ

main.c: In function ‘main’:
main.c:144:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
  144 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:145:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
  145 |         _exit(0);
      |         ^~~~~
main.c:145:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]

ソースコード

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define rd_long() ({long _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})

#define WTHI(v) {unsigned _z=v,_n=0;ulong _d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(ulong*)wp=_d;wp+=_n;}
#define WTLO(v) {unsigned _z=v,_n=8;ulong _d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(ulong*)wp=_d;wp+=8;}
#define wt(v) if(v>=100000000){WTLO(v/10);*wp++=v%10+'0';}else{WTHI(v);}
#define MD 998244353

typedef unsigned long ulong;

char wbuf[1<<25];

unsigned const t0[]={
        1,       26,      676,    17576,   456976, 11881376,308915776, 45855352,
193994799, 52643009,370473881,648121729,879255306,899262190,421196821,968673816,
229410391,973448401,353549601,208090449,419129909,914934104,828666585,582199797,
163529427,258787690,739013822,247716665,451167172,749658589,524480607,659319193,
172145017,482793030,573686544,940429202,493294780,846732044, 53657378,396847475,
335590820,739406496,257926189,716614796,663586342,283090891,372652695,704770893,
355644864,262567287,837283344,806235531,997236746,972046571,317102021,258697722,
736674654,186898297,866378310,564460294,700546702,245815898,401747230,462984450,
 58663464,527005711,724971897,880870968,941269402,515139980,416462891,845591636,
 24006770,624176020,256666872,683872554,810532403,110711065,881998984,970597818,
279434443,277585047,229500751,975797761,414632961,798013456,783462796,405145636,
551343006,359497214,362728387,446738885,634523127,525691654,690806415,990812789,
805023689,965728854,152841379,979142795,501603845, 64523381,679363553,693298377,
 57359448,493101295,841701434,921105871,989132527,761336877,828116095,567887057,
789642540,565818980,735872538,166043281,324147894,441890420,508463037,242862373,
324955580,462890256, 56214420,463330567, 67662506,760980803,818858171,327181033,
520752034,562376295,646362728,833521280,708421867,450570188,734137005,120919423,
149171939,883737355, 17551111,456328886,883863153, 20821859,541368334,100155742,
607560586,822909941,432527053,265015495,900936752,464735433,104189022,712425866,
554674162,446107270,618101137, 98719914,570229058,850534566,152522950,970863641,
286345841,457281395,908628387,664717943,312512517,139370618,628903009,379568586,
884584059, 39565415, 30456437,791867362,623664352,243363504,337984986,801654812,
878138052,870213586,664177470,298460219,772255223,113748738,960978482, 29331707,
762624382,861591225,439996084,459210301,958779943,970414046,274656371,153355175,
992501491,848929941,110802700,884381494, 34298725,891766850,226317981,893045741,
259569147,759331704,775981597,210634462,485274247,638198186,621243188,180413240,
697766828,173539174,519041112,517892323,488023809,709686798,483458394,590986008,
391970913,208800208,437583643,396486835,326214180,495613856,907028020,623108401,
228908778,960406463, 14459213,375939538,790228811,581062026,133947381,487898847,
706437786,398984082,391142602,187264122,875889760,811757994,142576431,712254147,
550209468,330025226,594701052,488562057,723681246,847314042, 68789326,790278123,
582344138,167282293,356362206,281218179,323962183,437061934,382922401,971783249,
};
unsigned const t1[]={
        1,310255649, 21292268,708970540, 17714050,879753653,644849645, 85267069,
435724833,318545626,701565486,559737857,186254472,216549379,887664334,634033164,
659011181,972869614,968016948, 37422256, 52437386, 71885890,521454126,577621855,
128074564,803981463,  6611870,832158749,305161923,325609455,982324716, 23245519,
671526670,305242632,787433944,483206862,960244419,868874624,220238072,491599888,
406509201,725479179,584491943,452856780,826105486,256978022,947176566, 86254292,
633466570,503896269,684580427, 34500800,709945971,246396524,546012643,743713281,
307266542,659656532,906860085,122699618,565872129,936232733,492323049,789359763,
544153302,132979377, 93186781,271775600,521601917,214132512,467453896,548790311,
587081854,175555375,890665208,194291762,447906589,996170205, 91810692, 13333409,
934071321,818521471,486959353, 66799238,434900092,737582560,211576521,126155702,
987293930,225776791,592300846,706214826,505643104,285314935,527124153,376791422,
190473980,814183987,792814125,766076380,690523353,198738417,630611506,882229107,
981344269,813418341, 17152810,754780095,555507088,653236328,117814360,996705472,
773474542,105970764,887846433,241813674,778654661,857059584,353059002, 51133051,
 49965792,427217159,125420388,436462352,187457091,771851535,409571070,610848711,
379370758,188872711,317989034,181758395,610666017,844684398,377506360,853689083,
239300121,223572659,487448769,198731039,538734613,512239224,997109869,889167684,
777728535,686685683,349014396,222235114,753637047,743520069,764453957,502950429,
377492971,535557455,655008827,122565276,896189333,460436422,462246805,862992215,
817319764,381657186,996798211,176876281,202282582,742445148,913135939,743465185,
745587715,842250880,803255551,607637077,336627832,948184711,867901201, 80422518,
655707863,424042507,136495398, 13390658,997947993,923217190,724255186,960429393,
 31194427,662246519,251123532,807227355,479751847,784986203,382900586,342303608,
544421568,555493930,130566203,460815209,955818937,282938891,947166331, 34973670,
324372544,428621326, 63506570,918170758, 67247079,  3509831, 59871739,695288069,
156148461,667032004,240809042,840513566,343270292,195093693,649978735,956281648,
465894047,442020769,452002985,225779611, 52933445,855749406,319126845,326718285,
795208408, 51579156, 66719487,719414504,671561745,660439254,926958000,359819779,
374316250,498813663,100986173,493963475,333982246,364268000,272367590,786500604,
192420501, 85164470,532321546,910029811,104402077,918888720,593852938,927050158,
186917342, 78752596,716446427,462888918,423010342,904743360,227266086,424183426,
};
unsigned const t2[]={
        1,944368488,747103536,187140280,368772981,182786253,897364219,211263171,
 25615497,786077300, 44720034,112002094,728573209,393273306,492113322,710070803,
685619638,181037678,571925278, 93776363,700649662,491333458,452835393,825669926,
536368711,  1481288,968975171,849767155,187229952,714875221,276047909,654734096,
979577925,660462606,753028138,752703065,144592825,823720420,580596153,607450957,
230453107,313012486,576979344, 26671436,106498182,263398439,372982546,356428657,
980827323,877450479, 73051050,658917433,695403701,250788539,473190954,611929167,
467216733, 14534483,963337113,327262955,952551430,308178920,123652471,677912738,
339353240,795299465, 97013587,719585297,561330887,925669473,150317617,260521750,
 57679810,986012998,791268126,954131553, 93171365,816608776,405099753,833988860,
524362035,728301557,619292953,383515927,270649121,581585988,600444648, 59863737,
 96946194,961043381,461405853,799935235,722465725, 81889341,628506542,288092281,
450565142,676222010,973866063,385040867,315816627,353649752,203392208,764469092,
391396530,253764839,721346903,596153172,672159088,387562106,487665661,724445389,
391131913,795928351,729606723,  4299683,448973326,969532267, 35596413,578181588,
174319134,546090626,236930207,221032255,520510969,142674362,458761942,312336268,
480750826,645351770,915511305,757555511,632584205,294530908,769462228,753313389,
580150385,981395803,660709672,448768950,269859564,461313404,330457150,274450131,
721269817,974574082,162196268,121083229,258092676,682389226,513631567,721503487,
660735215,876512042, 98183311,991523280,464995925,394871529,408682148,760778617,
608784924,206640887,550381306,583560570,189636075,768634406,818426085,115139061,
679912066,370844985,844510077,936308791,578238030,963290395,725910112,385114874,
112621454,486814540,251940646,545862939,644394798,287203988,173542061,656213304,
210496054,803088149,  5529007, 73196557,556332987,679574753,362049365,894630512,
 68703106,884769660,348150898,753044990,240742962,475601461, 59563500, 73530187,
339313155,208568098,780607380,  9529939,298766726, 54024635, 42615004,881403067,
453921802,660444943, 37318871,455049004,871124321,730960342,349247016,587087694,
126455248, 71180884,674335321,746238470,333819506,841006748,769031195,870648095,
942285026,480030728,779451548,975584479,410885659,909297127,786727282,114138844,
 11066772,471146413,753700347,218249767,119140020,449078233, 75445045,269116123,
431845097, 81536386,827757320,591343175,185387046,491656472,187984132,154909680,
779976716,335011238,328954822,844578258,166931913,431581162,815401029,257764309,
};
unsigned const t3[]={
        1,852127815,737081821,637093082,148579152,785023286,735857345,497444627,
820873187,598597635,161711596,753863840,473379239,330820723,870177108,220050301,
255016623,683624219,917380677,751659788,319248120,487018703,997222412, 99416753,
 92407826,395868439,826627739,576569501,634461433,870181655,658891113,659763689,
640755667,695357840,530734902,147524579,346033774, 73723481,708756820,687191030,
243640717, 68958051,464157011,289156217,199814243,259537708,566172240,307542799,
503749204,704647280,515592166,690489812,915251816,626269029,866414704,529980905,
340808120,434112692,962770563,446401701,480750826,206923682,659775328,   503044,
};

int main(){
	char*wp=wbuf;
	rd_init();
	int t=rd();
	while(t--){
		ulong l=(ulong)rd_long()%(MD-1);
		ulong x=319438194;
		x=x*t0[l&255]%MD; l>>=8;
		x=x*t1[l&255]%MD; l>>=8;
		x=x*t2[l&255]%MD; l>>=8;
		x=(x*t3[l&255]+(MD-319438194))%MD;
		wt(x);
		*wp++='\n';
	}
	write(1,wbuf,wp-wbuf);
	_exit(0);
}