Problem Statement
You are given a
A 3-rotation is performed as follows:
- Select any three numbers a < b < c that are all valid indices into X.
- Form a new number by rotating the digits at those three indices: the digit from index a goes to index b, the one from b goes to c, and the one from c goes to a.
For example, if X = "25749", one possible 3-rotation looks as follows:
- We select the indices a=0, b=3, and c=4.
- We rotate the three digits, producing the new number "95724".
Two 3-rotations are considered distinct if they use different triples of indices. Note that distinct 3-rotations may sometimes produce the same result. A 3-rotation is considered valid if the resulting number doesn't have any leading zeros.
Consider all valid 3-rotations of the given number X. Report the sum of all their results, modulo 998244353.
Definition
- Class:
- DigitRotation
- Method:
- sumRotations
- Parameters:
- String
- Returns:
- int
- Method signature:
- int sumRotations(String X)
- (be sure your method is public)
Constraints
- X will contain between 1 and 500 characters, inclusive.
- Each character of X will be a digit ('0'-'9').
- X[0] will not be '0'.
Examples
"123"
Returns: 312
There is only one valid 3-rotation. It produces the number 312.
"3570"
Returns: 10407
There are four possible 3-rotations, but only two of them are valid. The other two produce a number with a leading zero. For example, selecting the indices (0,1,3) is not a valid 3-rotation, as it produces the result "0375". The two valid 3-rotations produce the numbers 7350 and 3057, respectively. The answer is their sum.
"5545"
Returns: 21208
In this case there are four 3-rotations, and all four of them are valid. Note that two of them yield the same result: the number 5554. The other two produce the results 4555 and 5545. Therefore, the answer is 4555 + 5545 + 5554 + 5554. Also note that the rotation with indices 0,1,3 is valid, even though it leaves the number unchanged.
"1283749218734901238749213847902"
Returns: 867286291
Do not forget to take the answer modulo 998244353.
"50000000000"
Returns: 551438470
"3050"
Returns: 8305
"1000"
Returns: 1000
"12"
Returns: 0
"4"
Returns: 0
The sum of an empty set is zero.
"1"
Returns: 0
"12938742903847102934710293487129384712093847129038471290384712903847129085790356983576894576894375689437569845769845767777777777777777721342422888888822999229222222222222222222293482934879058713904587309409345090909009459039045902345934534958038457293487590238475091843750756897457809874509387459023874590238745909384759023847590238475903284759023485790234857239048572390485739204857902348750938427509234875938475902384579023487592834750239485793280475290348570983147529308475902384759203845702934857"
Returns: 438713094
"98309459945555444444444444444444444444444444444400000000000000098340592384509238450923845092384509458345349853948573928475982374658237465329485762349857632458972364598723645982374659823746598237465892374563284509238450932845092444444444453249852345782346529387456328947562349857623495876324598723645982374659283475639248576239847562893745689237465892374659837146589372649817465198364189465981374569837465982347569823475689324765892374658923746589237456293847563298475623984756239847563428756384509384"
Returns: 966817600
"11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
Returns: 991407897
"22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222"
Returns: 984571441
"70000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
Returns: 245515970
"9876543210"
Returns: 740791558
"98765"
Returns: 783260
"70000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000000000000000000009000000000000000000000000000000000000000000000000000000000500000000000000000000000000000000000002000000000000000000000000000000000040000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000080000000000000000000000000000000000000000000006000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
Returns: 580252981
"12374"
Returns: 358865
"999999999999999999999999999"
Returns: 18681458
"888888888888"
Returns: 485047013
"80"
Returns: 0
"100"
Returns: 0
"305"
Returns: 530
"350"
Returns: 0
"981"
Returns: 198
"12353"
Returns: 284675
"1993949234923492"
Returns: 145138541
"9149058309485093845094"
Returns: 333422943
"998244353"
Returns: 215087324
"9982443530"
Returns: 374150751
"998244354"
Returns: 980519480
"998244352"
Returns: 447899521
"1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111"
Returns: 445274097
"81747485816648304646357756650603198648925597881115761163411390495675556491959048111497613366174574383895746417912141516525167333405782515429997990532389882200432860212048439188858189604509124622261249181465868142406684429848877215648209247754208497547858521683102378376329236851604757666031169915256846852737921335462428943912943359139017963628244210715371002601758992485325993073636175731938935885376871929546955986970591984941898372039990001518007724448270959404351577168977228617193449368701998022"
Returns: 358272047
"704805678820080738847928015216627310340168837520388329353444415150500848149246784314078815794165452527188848005972905747132825969398031049976745125169311642949867736832699407803140896857236863133357556018095535221566829278244308484976301988209840758710455815524826101994618859351701300875525921130509"
Returns: 29173788
"12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890"
Returns: 316752414
"36753562912709360626187920237592289736129319478450361063206155476569374525474430786884314920689266495048717272261061594909177115977673656394812939088509638561159848103044447631759621785741859753883189643338604888977643030925405946922477548128936802105110850646258628472406299081311034039196933805664004626756987282996027613215991491075870480429610422205529028380409196254499360502943517431469422641288928886838333804768906879033373265265879604104870862479392830178915492574994593570819978253490201962"
Returns: 41485333
"1234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679123456791234567912345679"
Returns: 561370040
"1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789"
Returns: 693261620
"90205946716241682622408680768199870943253492965382986218147174113301960948422921416915129358324724921006162204022158402370578076851670585789758106677683287779945487112733658553728058188332300859538960636681164660257453927015427331311839026967663830816984094361940512188564433020487972690266305867200514441510261403746229527814732849811673853339545591183719299333492981551264989325838873707243986820324634295097512826309428917062380114011777056691021226174128379442971866697882936732012811598937288406"
Returns: 708957197
"1100"
Returns: 1010
"99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999"
Returns: 936716249
"13068209271501718214926494458660051218286031905490881475416690946340334573046760821234273095029616510360690895010412349313461779507511413098779132671105433371447245599313757779741474502025148820903558962332095756566247699102094483282136772896373323910203246197587351902547513821961851070517610098726771785816022244994885975429580579167820585419469929055646862341073213281318504982736373598636680202826083718445223203707410852016625212886428580848678817695276615450278466388714395042646544571372147568"
Returns: 561085142
"10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
Returns: 917250316
"90476890687903"
Returns: 887359507