Statistics

Problem Statement for "TheLongPalindrome"

Problem Statement

John and Brus are studying string theory at the university. Their task is to create a list of all the palindromes that contain between 1 and n lowercase letters ('a'-'z'), inclusive. A palindrome is a string that reads the same forward and backward. Additionally, each palindrome in their list must contain no more than k distinct letters. Return the number of palindromes in the list modulo 1234567891.

Definition

Class:
TheLongPalindrome
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int n, int k)
(be sure your method is public)

Constraints

  • n will be between 1 and 1,000,000,000, inclusive.
  • k will be between 1 and 26, inclusive.

Examples

  1. 1

    1

    Returns: 26

    All palindromes in the list are single character strings.

  2. 2

    10

    Returns: 52

    Now we have single and double character palindromes.

  3. 3

    2

    Returns: 728

    A slightly longer list.

  4. 44

    7

    Returns: 240249781

  5. 1000000000

    26

    Returns: 502499513

  6. 999999999

    25

    Returns: 555594822

  7. 23

    23

    Returns: 1209505107

  8. 40

    19

    Returns: 923760996

  9. 39

    19

    Returns: 1161532321

  10. 1000000000

    1

    Returns: 74074289

  11. 757148

    26

    Returns: 808142191

  12. 301413357

    26

    Returns: 903541512

  13. 659598369

    26

    Returns: 801376963

  14. 391749388

    26

    Returns: 1084608896

  15. 35766291

    26

    Returns: 998485394

  16. 473038165

    26

    Returns: 754312177

  17. 3615545

    26

    Returns: 1134947060

  18. 392289611

    26

    Returns: 854429520

  19. 170427799

    26

    Returns: 1020182844

  20. 675016434

    26

    Returns: 298581589

  21. 100757147

    19

    Returns: 647481233

  22. 401413356

    23

    Returns: 1150834273

  23. 759598368

    14

    Returns: 706606893

  24. 491749387

    18

    Returns: 15745476

  25. 135766290

    9

    Returns: 384108829

  26. 573038164

    21

    Returns: 333945499

  27. 103615544

    23

    Returns: 480834182

  28. 1000000000

    20

    Returns: 198470272

  29. 999999999

    17

    Returns: 517605484

  30. 999999999

    16

    Returns: 652883421

  31. 1000000000

    20

    Returns: 198470272

  32. 147

    7

    Returns: 1126070080

  33. 999999999

    23

    Returns: 1049716493

  34. 999999999

    11

    Returns: 318667120

  35. 999999999

    26

    Returns: 522071800

  36. 1000000000

    23

    Returns: 1232051448

  37. 1000000000

    25

    Returns: 460019892

  38. 1000000000

    15

    Returns: 389687257

  39. 1000000000

    10

    Returns: 482302736

  40. 999999973

    25

    Returns: 1222160695

  41. 1000000000

    19

    Returns: 868920764

  42. 574857047

    23

    Returns: 946932112

  43. 999999997

    23

    Returns: 138511467

  44. 51

    12

    Returns: 776103748

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: