We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
We can solve this problem by finding the recurrence relation. Let A(n,m) be the number of ways in the string with length n for which exactly m characters come after theit neighbour to the left. We can call them ascents. We can construct such string either by placing a new character to string with length n - 1 and m - 1 ascents or placing a new character to the string n-1 with m ascents. In the first case we have string with m segments were characters are decreasing from left to right and we can put a new character in all n positions except for position 0 and and m-1 positions between ascending characters that is n-m positions. In the seconds case we have string with m+1 decreasing segment and we can put character at the begining of each segment
that is we have m+1 choices. So A(n,m) = (n-m)*A(n-1,m-1) + (m+1)*A(n-1,m). A(n,0) = 1 for all n and A(n,n) = 0 for all n.
The rest is trivial as we can use memoization to solve all test cases.
For N = 700 and m = 0, 1, .. 699 I get following sum:
First digits: 24852827549363778103818000360884855688859274799663035....
last digits:
08433505760735219696180850962689869949710826332645746831356075750752869976605336293599548108511464727114964064660520016562607136532939010163985742438455249882955899640271685505419053449214593163977703007368323931572476417580582804451662627264391735394040958486127161392677991
We can solve this problem by finding the recurrence relation. Let A(n,m) be the number of ways in the string with length n for which exactly m characters come after theit neighbour to the left. We can call them ascents. We can construct such string either by placing a new character to string with length n - 1 and m - 1 ascents or placing a new character to the string n-1 with m ascents. In the first case we have string with m segments were characters are decreasing from left to right and we can put a new character in all n positions except for position 0 and and m-1 positions between ascending characters that is n-m positions. In the seconds case we have string with m+1 decreasing segment and we can put character at the begining of each segment that is we have m+1 choices. So A(n,m) = (n-m)*A(n-1,m-1) + (m+1)*A(n-1,m). A(n,0) = 1 for all n and A(n,n) = 0 for all n. The rest is trivial as we can use memoization to solve all test cases.
For N = 700 and m = 0, 1, .. 699 I get following sum:
First digits: 24852827549363778103818000360884855688859274799663035....
last digits: 08433505760735219696180850962689869949710826332645746831356075750752869976605336293599548108511464727114964064660520016562607136532939010163985742438455249882955899640271685505419053449214593163977703007368323931572476417580582804451662627264391735394040958486127161392677991
Wow, those are some big numbers! My very wimpy C++ BigNumber class times out for test cases with alphabets of size around 500.
For example, answer for
370 1
113
is the number (more than 750 digits)
1129486192863670815372730620783152644645169 1442473318546501048909340350384155216314327 4388928275082280890440415255439241910001546 2010749396855372214202134439383005223993275 8536596323384816629416049833306137266457487 4322049800510021109373025249471015248831329 7130400883899674846529159641866613001987231 7911193788754442584927477720429127563216884 6008787920431360644080198580955955254473662 7756954418383722891987501053820677434636345 5978890805684775481410610470681630942556410 6409125700551210297628302316146986808029677 2380837979049654271185843505158957683435991 5743631040336861132082488759019517356369043 6639985261394938004139680810790315701841724 9032123262350144516972365274229892284882967 6141813989374499877422091577973968474227765
01855821264609860903760
what does lexographic mean
Doesn't the output value reach way beyond 2^64 ? It doesn't say I need to output modulo 1000000007 so I'm confused.