Statistics

Problem Statement for "IncreasingNumber"

Problem Statement

A positive integer is called Increasing Number if its digits are in non-descending order from left to right in decimal notation. For example, 1234, 111, 58 and 8899 are Increasing Numbers, while 314, 7654 and 2009 are not.

You are given a long digits and an int divisor. Calculate the number of Increasing Numbers that satisfy both of the following conditions and return this number modulo 1,000,000,007.
  • The number contains exactly digits digits in the decimal notation with no leading zeroes.
  • The number is divisible by divisor.

Definition

Class:
IncreasingNumber
Method:
countNumbers
Parameters:
long, int
Returns:
int
Method signature:
int countNumbers(long digits, int divisor)
(be sure your method is public)

Constraints

  • digits will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
  • divisor will be between 1 and 500, inclusive.

Examples

  1. 2

    12

    Returns: 4

    12, 24, 36, and 48 satisfy the conditions.

  2. 3

    111

    Returns: 9

    All 3-digits numbers divisible by 111 are Increasing Numbers.

  3. 452

    10

    Returns: 0

    There is no Increasing Number divisible by 10.

  4. 6

    58

    Returns: 38

  5. 26542766498659

    25

    Returns: 766312864

  6. 1000000000000000000

    500

    Returns: 0

  7. 1191391530

    289

    Returns: 475286846

  8. 749886849151962303

    66

    Returns: 0

  9. 749886849151962303

    1

    Returns: 661603623

  10. 19331162461509069

    389

    Returns: 56752330

  11. 416200735956824683

    231

    Returns: 0

  12. 643124731204676461

    106

    Returns: 262850288

  13. 865199921304978104

    172

    Returns: 249358233

  14. 54126391707803701

    39

    Returns: 779801725

  15. 671063097370769915

    329

    Returns: 246638202

  16. 550939609201547580

    381

    Returns: 57818109

  17. 55039596160320169

    288

    Returns: 995668005

  18. 163128123172298853

    335

    Returns: 787579912

  19. 501387399378258699

    405

    Returns: 978228651

  20. 82190732272563427

    227

    Returns: 923474687

  21. 896839841037856137

    56

    Returns: 569787111

  22. 303177480212212551

    270

    Returns: 0

  23. 840851407954101812

    39

    Returns: 186899778

  24. 390878882493758140

    493

    Returns: 861537174

  25. 456171233135326954

    54

    Returns: 55048903

  26. 128392756807576563

    278

    Returns: 332310466

  27. 90879438685727167

    46

    Returns: 242788905

  28. 95423511116150452

    485

    Returns: 448679752

  29. 259646944544549089

    133

    Returns: 797289029

  30. 547970027625158847

    484

    Returns: 0

  31. 716125354002379421

    99

    Returns: 0

  32. 601399664891764513

    496

    Returns: 552901552

  33. 587509511140690310

    46

    Returns: 38084373

  34. 221056621576503616

    230

    Returns: 0

  35. 462631284211754200

    392

    Returns: 974846149

  36. 602795751183208049

    273

    Returns: 593473140

  37. 575055690344512924

    470

    Returns: 0

  38. 1000000000000000000

    499

    Returns: 76413956

  39. 209380238032

    1

    Returns: 102111522

  40. 12

    1

    Returns: 125970

  41. 1

    3

    Returns: 3

  42. 1

    11

    Returns: 0

  43. 23532

    1

    Returns: 977032859

  44. 1000000000000000000

    1

    Returns: 652411468

  45. 1000000000000000000

    256

    Returns: 479459

    maximal pre-cycle length

  46. 1000000000000000000

    486

    Returns: 469981615

  47. 1

    16

    Returns: 0

  48. 2

    48

    Returns: 1

  49. 1

    20

    Returns: 0

  50. 89280254937855977

    13

    Returns: 644977870

  51. 5

    19

    Returns: 67

  52. 2

    32

    Returns: 0

  53. 1

    8

    Returns: 1

  54. 2

    45

    Returns: 1

  55. 2

    29

    Returns: 2

  56. 5

    123

    Returns: 10

  57. 2

    101

    Returns: 0

  58. 4

    101

    Returns: 9

  59. 999999999999999999

    397

    Returns: 822411603

  60. 99999999999999999

    479

    Returns: 264676719

  61. 856923147569242342

    327

    Returns: 157281183

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: