Statistics

Problem Statement

Definition

Class:

YetAnotherORProblem2

Method:

countSequences

Parameters:

int, int

Returns:

int

Method signature:

int countSequences(int N, int R)

(be sure your method is public)

Notes

• If a and b are single bits then a | b is defined as max(a, b). For two integers, A and B, in order to calculate A | B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2 (if the lengths of their representations are different, the shorter one is prepended with the necessary number of leading zeroes). Then A | B = C = (cn...c1)2, where ci = ai | bi. For example, 10 | 3 = (1010)2 | (0011)2 = (1011)2 = 11.

Constraints

• N will be between 2 and 10, inclusive.
• R will be between 1 and 15000, inclusive.

Examples

1. 2

   2

   Returns: 7

   The possible sequences are: {0,0}, {0,1}, {0,2}, {1,0}, {1,2}, {2,0}, {2,1}.

2. 2

   3

   Returns: 9

   Now we can also have {0,3} and {3,0}.

3. 3

   3

   Returns: 16

4. 7

   1023

   Returns: 73741815

5. 2

   1

   Returns: 3

6. 2

   1024

   Returns: 61097

7. 2

   15000

   Returns: 4628299

8. 2

   8192

   Returns: 1610707

9. 2

   8191

   Returns: 1594323

10. 2

    12414

    Returns: 3859991

11. 3

    1

    Returns: 4

12. 3

    7

    Returns: 64

13. 3

    81

    Returns: 11980

14. 3

    597

    Returns: 670708

15. 3

    4235

    Returns: 30295792

16. 3

    11111

    Returns: 208187968

17. 3

    14336

    Returns: 256383985

18. 10

    14336

    Returns: 713476067

19. 10

    14335

    Returns: 713485067

20. 10

    8192

    Returns: 710933233

21. 10

    15000

    Returns: 604862946

22. 10

    14889

    Returns: 122153261

23. 10

    14999

    Returns: 504862946

24. 4

    2

    Returns: 21

25. 4

    412

    Returns: 1840049

26. 4

    777

    Returns: 8797045

27. 4

    1000

    Returns: 9762149

28. 4

    10000

    Returns: 331991665

29. 5

    5

    Returns: 186

30. 5

    2048

    Returns: 606937681

31. 5

    2166

    Returns: 236906422

32. 5

    4842

    Returns: 524164130

33. 5

    11555

    Returns: 153919913

34. 6

    1

    Returns: 7

35. 6

    124

    Returns: 823465

36. 6

    8000

    Returns: 881512537

37. 6

    8001

    Returns: 881792473

38. 6

    8190

    Returns: 889009537

39. 6

    8134

    Returns: 888746881

40. 6

    14123

    Returns: 300553945

41. 7

    9

    Returns: 3256

42. 7

    898

    Returns: 66473638

43. 7

    1900

    Returns: 575048607

44. 7

    2011

    Returns: 589702008

45. 7

    3093

    Returns: 991581192

46. 7

    8900

    Returns: 987061820

47. 7

    9999

    Returns: 721994547

48. 7

    15000

    Returns: 536763508

49. 8

    7

    Returns: 729

50. 8

    8

    Returns: 4825

51. 8

    13

    Returns: 6489

52. 8

    422

    Returns: 382371713

53. 8

    4774

    Returns: 38236942

54. 8

    9041

    Returns: 696657728

55. 8

    14336

    Returns: 463250579

56. 8

    14136

    Returns: 164677824

57. 8

    14333

    Returns: 743773888

58. 8

    14408

    Returns: 362174879

59. 8

    14493

    Returns: 949082868

60. 8

    15000

    Returns: 621910852

61. 9

    6

    Returns: 991

62. 9

    99

    Returns: 9756100

63. 9

    999

    Returns: 999828919

64. 9

    9999

    Returns: 928944134

65. 9

    8092

    Returns: 982796158

66. 9

    14599

    Returns: 145822809

67. 9

    14995

    Returns: 401807800

68. 9

    15000

    Returns: 497998621

69. 10

    13533

    Returns: 948229035

70. 10

    13900

    Returns: 694816363

71. 10

    14208

    Returns: 764767976

72. 10

    12954

    Returns: 660459545

73. 9

    12954

    Returns: 575289095

74. 10

    13478

    Returns: 39129197

75. 9

    14444

    Returns: 888515420

76. 2

    10

    Returns: 59

77. 10

    12345

    Returns: 846521329

78. 9

    14297

    Returns: 990869599