Statistics

Problem Statement for "DerangementsStrikeBack"

Problem Statement

You are given two ints: n and m.

Let D[i] be the number of permutations of the set {1,2,...,n+i} such that the first i values are not fixed points of the permutation. Formally, we are interested in permutations p such that for each j between 1 and i, inclusive, we have p(j) != j.

Next, let B[i] = (D[i] / n!) modulo (10^9 + 7). Note that it can be shown that D[i] divided by n! is always an integer.

Compute and return the bitwise xor of the values B[i] for i between 1 and m, inclusive.

Definition

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

Notes

  • Author's solution explicitly computes each of the values B[i]. Bitwise xor is only used to reduce the size of the output.

Constraints

  • n will be between 0 and 1,000,000,000, inclusive.
  • m will be between 1 and 100,000, inclusive.

Examples

  1. 0

    3

    Returns: 3

    As we have n=0, we are counting derangements, i.e., permutations with no fixed points. We can easily see that D[1]=0, D[2]=1, and D[3]=2. As 0! = 1, we also have B[1]=0, B[2]=1, and B[3]=2. Thus, the correct return value is (0 xor 1 xor 2) = 3.

  2. 1

    3

    Returns: 9

  3. 3

    3

    Returns: 73

  4. 4

    1

    Returns: 4

  5. 70

    39

    Returns: 319676671

  6. 0

    12345

    Returns: 683702962

  7. 0

    100000

    Returns: 1036996263

  8. 1000000000

    1

    Returns: 1000000000

  9. 1000000000

    100000

    Returns: 542069369

  10. 370242812

    88757

    Returns: 420979659

  11. 507562699

    4885

    Returns: 73206930

  12. 939849878

    88309

    Returns: 731267126

  13. 77169765

    4437

    Returns: 127255300

  14. 919522361

    55157

    Returns: 472697994

  15. 50

    19

    Returns: 327679888

  16. 15

    47

    Returns: 823622925

  17. 31

    21

    Returns: 349396594

  18. 46

    45

    Returns: 569066966

  19. 5821

    55390

    Returns: 618778242

  20. 55229

    81

    Returns: 348379946

  21. 500984

    75

    Returns: 759902809

  22. 13

    100

    Returns: 890931655

  23. 4

    34

    Returns: 607287887

  24. 9513

    23

    Returns: 391052831

  25. 8356001

    43

    Returns: 287781834

  26. 1

    618

    Returns: 249120489

  27. 86607

    64

    Returns: 670835158

  28. 801491399

    6960

    Returns: 952083914

  29. 333636

    8

    Returns: 715536442

  30. 3654

    1170

    Returns: 1040155257

  31. 884614

    6829

    Returns: 954332261

  32. 1

    117

    Returns: 513531619

  33. 12031991

    23221

    Returns: 927646603

  34. 50963

    3

    Returns: 853105813

  35. 26792

    963

    Returns: 860533662

  36. 254088346

    9048

    Returns: 134791655

  37. 38

    28

    Returns: 810689834

  38. 44611284

    954

    Returns: 199354260

  39. 58585

    45

    Returns: 978498919

  40. 531068323

    15

    Returns: 409378080

  41. 5132503

    23363

    Returns: 512253022

  42. 54

    61

    Returns: 949331111

  43. 7975133

    56048

    Returns: 648887522

  44. 8330567

    6506

    Returns: 829618358

  45. 806401

    59077

    Returns: 789895885

  46. 16518307

    275

    Returns: 714902137

  47. 850

    26740

    Returns: 592610554

  48. 735

    5

    Returns: 553915785

  49. 997051

    8

    Returns: 318116342

  50. 117

    6

    Returns: 753534616

  51. 118

    28

    Returns: 303125841

  52. 925658423

    917

    Returns: 170184929

  53. 734

    1

    Returns: 734

  54. 7

    67

    Returns: 662733229

  55. 3683

    2681

    Returns: 441849391

  56. 5637237

    8

    Returns: 333022216

  57. 64455463

    5439

    Returns: 1046244009

  58. 970189304

    95

    Returns: 984052749

  59. 7662

    34114

    Returns: 340199527

  60. 750354

    64064

    Returns: 408203866

  61. 938034

    6964

    Returns: 1015366012

  62. 468125115

    2

    Returns: 376601084

  63. 260

    8906

    Returns: 725632693

  64. 0

    422

    Returns: 462313885

  65. 643

    10

    Returns: 562043046

  66. 255936040

    1

    Returns: 255936040

  67. 291837066

    968

    Returns: 90948002

  68. 73708

    174

    Returns: 1043100958

  69. 337971344

    10

    Returns: 449306760

  70. 2904653

    89

    Returns: 1029492575

  71. 26140195

    5199

    Returns: 874672356

  72. 82559

    6218

    Returns: 833797401

  73. 16332905

    888

    Returns: 112847748

  74. 36695

    357

    Returns: 951859002

  75. 922

    440

    Returns: 31154663

  76. 126122924

    1354

    Returns: 678015142

  77. 3

    307

    Returns: 486451410

  78. 293196087

    851

    Returns: 253877783

  79. 67

    100

    Returns: 111488981

  80. 5386

    77017

    Returns: 389256855

  81. 502025

    99

    Returns: 169027416

  82. 86413280

    33629

    Returns: 594814767

  83. 9

    8

    Returns: 639682824

  84. 227254

    1968

    Returns: 353895834

  85. 6569806

    3

    Returns: 325907047

  86. 9306

    657

    Returns: 127406496

  87. 10

    83

    Returns: 136970137

  88. 66

    6243

    Returns: 754496557

  89. 650337

    97811

    Returns: 579399286

  90. 5030926

    2948

    Returns: 333341744

  91. 951

    6325

    Returns: 899796375

  92. 4

    67

    Returns: 54082159

  93. 93604

    2538

    Returns: 1010094588

  94. 25

    99831

    Returns: 377347236

  95. 403739776

    4630

    Returns: 636778756

  96. 46

    9

    Returns: 367112555

  97. 4713

    7

    Returns: 327362714

  98. 1291

    57214

    Returns: 116956159

  99. 9174

    3070

    Returns: 301518109

  100. 497466804

    433

    Returns: 823675836

  101. 1

    9198

    Returns: 518540720

  102. 90

    853

    Returns: 611155561

  103. 0

    7

    Returns: 1553

  104. 956528

    7

    Returns: 560587842

  105. 10335

    60

    Returns: 838758844

  106. 6157973

    110

    Returns: 517831857

  107. 17

    2

    Returns: 290

  108. 8551010

    7

    Returns: 165415308

  109. 5492

    9399

    Returns: 657208193

  110. 5471

    400

    Returns: 48502250

  111. 622497343

    50539

    Returns: 163197443

  112. 3

    1043

    Returns: 51294610

  113. 66

    41

    Returns: 309230698

  114. 64597

    4556

    Returns: 621476850

  115. 924148341

    80

    Returns: 332157824

  116. 2

    774

    Returns: 611521173

  117. 2

    1

    Returns: 2

  118. 5

    3

    Returns: 249

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: