Statistics

Problem Statement for "DistinctFaces"

Problem Statement

You have a collection of dice: for each valid index i you have exactly count[i] dice with size[i] faces.

A die with x faces has them labelled with integers from 1 to x, inclusive. When such a die is rolled, one of those integers is selected uniformly at random. All dice rolls are mutually independent.


If you roll your entire collection, what is the expected number of distinct values you'll see?


The answer can always be expressed as a reduced fraction A/B, where both numbers are coprime with M = 10^9 + 7. Let B^(-1) denote the inverse of B when computing modulo M. Calculate and return (A * B^(-1)) mod M.

Definition

Class:
DistinctFaces
Method:
expectation
Parameters:
int[], int[]
Returns:
int
Method signature:
int expectation(int[] count, int[] size)
(be sure your method is public)

Constraints

  • count will have between 1 and 50 elements, inclusive.
  • size will have the same number of elements as count.
  • Each element of count will be between 1 and 10^6, inclusive.
  • Each element of size will be between 1 and 10^6, inclusive.
  • The elements of size will be distinct.

Examples

  1. {1}

    {47}

    Returns: 1

    This is easy: you roll the only die you have and you are guaranteed to see exactly one value.

  2. {2}

    {6}

    Returns: 833333341

    Two six-sided dice. With probability 1/6 you roll doubles and then you'll see only one distinct value. With probability 5/6 you'll see two distinct values. The expected number of distinct values you'll see is therefore (1/6 * 1 + 5/6 * 2) = 11/6 = 1.833333. Computing modulo M = 10^9 + 7, the modular inverse of 6 is 166,666,668. Thus, we should return (11 * 166,666,668) mod M = 833,333,341.

  3. {1, 1}

    {1, 100}

    Returns: 430000005

    Again we have two dice but now they are distinct: one has only one face (and thus always rolls a 1), the other has 100 faces. Rolling two 1s is pretty unlikely and thus the expected number of distinct values is almost equal to 2. The exact value is 199/100. The answer is computed as (199 * 100^(-1)) mod M = (199 * 570,000,004) mod M = 430,000,005.

  4. {48}

    {6}

    Returns: 368315208

  5. {1000}

    {2}

    Returns: 272979609

    One thousand fair coins.

  6. {2, 1, 1}

    {6, 10, 20}

    Returns: 497500007

    A set of common Dungeons&Dragons dice: two d6s, a d10 and a d20. We can iterate over all 6*6*10*20 equally likely outcomes to calculate the exact expected number of distinct values. The result is 25326 / 7200 = 1407 / 400 = 3.5175. Our return value is (1407 * 400^(-1)) mod M = 497,500,007.

  7. {996960, 917105, 995425, 969469, 974721, 978965, 952132, 962138, 999022, 943390, 922776, 913964, 910516, 924947, 997147, 969674, 956498, 961575, 903758, 916568, 961171, 955744, 913514, 963249, 992407, 911832, 950198, 953038, 967806, 973202, 934669, 981966, 917062, 936772, 902366, 968420, 941189, 952419, 989554, 924236, 981280, 970266, 926393, 985226, 999634, 960224, 951127, 965004, 972320, 991732}

    {221714, 207043, 38719, 134462, 511511, 226410, 858303, 764154, 804255, 778685, 450972, 66712, 550217, 366320, 75091, 714643, 726178, 296155, 609209, 516325, 902797, 56179, 985418, 126533, 816573, 192977, 657789, 886750, 656728, 418814, 679146, 441709, 406740, 952304, 576088, 473920, 680554, 425203, 551441, 711200, 36342, 856000, 828386, 847883, 68392, 30630, 929932, 763001, 734852, 369859}

    Returns: 339050723

  8. {221714, 207043, 38719, 134462, 511511, 226410, 858303, 764154, 804255, 778685, 450972, 66712, 550217, 366320, 75091, 714643, 726178, 296155, 609209, 516325, 902797, 56179, 985418, 126533, 816573, 192977, 657789, 886750, 656728, 418814, 679146, 441709, 406740, 952304, 576088, 473920, 680554, 425203, 551441, 711200, 36342, 856000, 828386, 847883, 68392, 30630, 929932, 763001, 734852, 369859}

    {221714, 207043, 38719, 134462, 511511, 226410, 858303, 764154, 804255, 778685, 450972, 66712, 550217, 366320, 75091, 714643, 726178, 296155, 609209, 516325, 902797, 56179, 985418, 126533, 816573, 192977, 657789, 886750, 656728, 418814, 679146, 441709, 406740, 952304, 576088, 473920, 680554, 425203, 551441, 711200, 36342, 856000, 828386, 847883, 68392, 30630, 929932, 763001, 734852, 369859}

    Returns: 530942060

  9. {221714, 207043, 38719, 134462, 511511, 226410, 858303, 764154, 804255, 778685, 450972, 66712, 550217, 366320, 75091, 714643, 726178, 296155, 609209, 516325, 902797, 56179, 985418, 126533, 816573, 192977, 657789, 886750, 656728, 418814, 679146, 441709, 406740, 952304, 576088, 473920, 680554, 425203, 551441, 711200, 36342, 856000, 828386, 847883, 68392, 30630, 929932, 763001, 734852, 369859}

    {996960, 917105, 995425, 969469, 974721, 978965, 952132, 962138, 999022, 943390, 922776, 913964, 910516, 924947, 997147, 969674, 956498, 961575, 903758, 916568, 961171, 955744, 913514, 963249, 992407, 911832, 950198, 953038, 967806, 973202, 934669, 981966, 917062, 936772, 902366, 968420, 941189, 952419, 989554, 924236, 981280, 970266, 926393, 985226, 999634, 960224, 951127, 965004, 972320, 991732}

    Returns: 848884454

  10. {380464, 606447, 402212, 532998, 566366, 852478, 265117, 101816}

    {502, 112601, 188, 24315, 3, 133466, 1899, 3448}

    Returns: 153816278

  11. {1, 108, 11206, 62, 80, 10, 442527, 116963, 12, 16398, 9292, 2132, 277, 21, 129890, 127, 124989, 267380, 5, 26, 770180, 3, 8, 6, 3, 166, 202679, 608911, 519702, 1130, 14}

    {115497, 42059, 544630, 558561, 707637, 272886, 780329, 507455, 765682, 590074, 414689, 914727, 250592, 582239, 817538, 810628, 370199, 921856, 990520, 966796, 300227, 274297, 436900, 838457, 634027, 849307, 810483, 592848, 374283, 327373, 848417}

    Returns: 16163341

  12. {1365, 17124, 313621, 25453}

    {1013, 31253, 296847, 1}

    Returns: 975814724

  13. {921906, 546165, 743505}

    {506130, 402343, 568594}

    Returns: 793909678

  14. {616, 638, 59, 2042, 12034, 100021, 1071, 922034, 712507, 2, 714564, 606006}

    {726, 225475, 26198, 971114, 9, 363, 2279, 1136, 30816, 2253, 6290, 6821}

    Returns: 96135939

  15. {759419, 93163, 99310, 628, 147442, 693, 48582, 7979, 1, 770967, 13, 5, 317660, 174, 5}

    {61554, 7, 1837, 14, 6778, 1, 22148, 941509, 14941, 622565, 9, 11413, 158403, 62594, 707611}

    Returns: 533723614

  16. {805970, 94477, 672582, 329416, 106866, 37525}

    {617728, 904153, 412914, 127712, 132069, 365233}

    Returns: 917544937

  17. {668836, 460453, 457222, 709040, 433182, 763125}

    {960513, 695620, 990988, 806085, 984107, 750150}

    Returns: 469535673

  18. {923964, 68635, 496149, 279767, 67483, 170144, 214672, 238479, 974010, 442603, 495601, 831855, 207045, 311127, 6228, 119734, 633879, 591833, 854132, 12440, 263304}

    {432, 91, 260459, 17515, 327172, 1407, 9158, 22, 81201, 13, 15045, 818, 2, 10007, 15, 63896, 3566, 3, 1314, 586, 178}

    Returns: 40425698

  19. {561}

    {21556}

    Returns: 793179007

  20. {852632, 766501, 616321, 134498, 73930, 951812, 18384, 143629, 128598, 543689, 817745, 133466, 641879, 895756, 976579, 991043, 306306, 597635, 631963, 923197, 438638, 573956, 781653, 511777, 642218, 895342, 609165, 912899, 24600, 175537, 819875, 843991, 626829, 568292, 606353, 863724}

    {666705, 326306, 763912, 463208, 754435, 348772, 414639, 930247, 94134, 290724, 707911, 200246, 39647, 630653, 265510, 961336, 534999, 486579, 318812, 616712, 426528, 975552, 800140, 755323, 936446, 929736, 51651, 94301, 986755, 485922, 402073, 639850, 68438, 54559, 749013, 364762}

    Returns: 974632079

  21. {847869, 826342, 979683, 914566, 511029, 513421, 767607, 427860, 360168, 393154}

    {681993, 507856, 513857, 646693, 483000, 952301, 941078, 939381, 298991, 846111}

    Returns: 510389090

  22. {367, 127, 37843, 4286, 14, 737, 11301, 5, 154475, 240984, 834, 2534, 6, 23326, 9, 220374, 516031, 143, 1655, 286, 6, 23601, 129150, 838, 12268, 868849, 372102, 355188, 94, 2}

    {763, 3, 150640, 1326, 5504, 3441, 86, 279942, 455, 46, 387, 224841, 10, 27555, 27, 54184, 565995, 12, 1, 304, 22, 115, 16071, 4926, 2703, 215061, 14, 766000, 1861, 43927}

    Returns: 781412874

  23. {47, 419, 127, 101546, 24752, 1262, 193, 136, 23, 19161, 1466, 1216, 336, 440, 21, 5, 2, 631948, 554, 1403, 7, 306}

    {1965, 2991, 124, 96477, 622794, 438683, 1787, 925424, 88318, 118, 26026, 7898, 174, 31268, 1, 42, 549, 468, 1602, 676, 6, 4}

    Returns: 469045367

  24. {261745, 247128, 3707, 269513, 568360, 857661, 26617, 840560, 353436, 415888, 901798, 557241, 317592, 747605, 207635, 265916, 70959, 711628, 53086, 254705, 183102, 640040, 369712}

    {67, 303, 43, 946435, 979, 25859, 1, 104, 576911, 943391, 851949, 3, 11047, 753, 565, 505, 550, 121, 5562, 210439, 194110, 488, 747}

    Returns: 12197647

  25. {476556, 897948, 543587, 773628, 743570, 275425, 98778, 367689, 800422, 269023, 9918, 661952, 579997, 292675, 559408, 280619, 487518, 550020, 643105, 489667, 922464, 157872, 381150, 141500, 703658, 900004, 218022, 20665, 102997, 56777, 403089, 517886, 216040, 688789, 707367, 554515, 704523, 603894, 165491, 663007, 734616, 385582}

    {896, 3, 334358, 8489, 183669, 221, 23980, 173, 127, 12, 84639, 374, 9272, 2, 26057, 6573, 57048, 262, 9776, 757520, 5632, 502, 118, 91, 208557, 333, 53362, 1, 77, 5892, 255, 190, 58977, 61, 6, 61671, 1337, 1762, 45440, 757563, 236491, 33537}

    Returns: 279833808

  26. {17327, 347888, 271360, 502904, 291761, 103348, 955238, 794487, 774602, 691242, 122688, 376231, 506778, 9489, 291981, 599204, 482469, 918754, 964526, 467673, 194652, 129259, 981652, 271290, 386575, 488475, 56524, 515902, 725889, 34364, 446547}

    {777616, 912207, 178055, 407209, 478252, 348679, 447650, 537479, 671082, 230698, 245669, 604021, 340428, 142320, 727142, 737001, 913795, 812377, 812399, 180155, 620763, 1964, 502740, 207736, 921126, 534556, 521269, 843456, 59806, 722148, 736576}

    Returns: 572060165

  27. {155355, 294123}

    {530794, 772011}

    Returns: 786627689

  28. {545541, 819630, 831220, 658129, 171475, 199769, 649287, 25285, 558380, 787570, 828751, 488286, 241158, 827032, 272221, 437858, 503505, 5618, 791032, 687141}

    {917604, 24, 14855, 138724, 53, 58, 5, 67, 3042, 428664, 56, 9, 163, 1, 3139, 10, 73833, 10924, 3, 257301}

    Returns: 177902658

  29. {683670, 996814, 6848, 96}

    {651515, 218856, 358517, 272316}

    Returns: 580354406

  30. {69335, 21238, 223297, 4828, 4, 241086, 85735, 60, 5, 3616, 127, 7, 71, 1, 182092, 4199, 28, 2997, 11, 113, 492, 7544, 35029, 41, 109, 892164, 17, 21, 35, 1, 66}

    {1585, 930190, 447, 2, 3, 15, 364, 553, 37, 63366, 4, 70571, 3543, 173, 189, 301, 6748, 29, 71, 378, 48990, 9, 714620, 58, 50, 61683, 641000, 5720, 12532, 1, 19}

    Returns: 239190562

  31. {470457, 509620, 483994, 834127, 520122, 621691, 177405, 932449, 794700, 38122, 437269, 621639, 920340, 532291, 855306, 572323, 487208, 338196, 388587, 454234, 178744, 545132, 680272, 954311, 580801, 560542, 240425, 520578, 431276, 813718, 783257, 48682, 368532, 909247, 319101, 654604, 258100, 843967, 492106, 256495, 842384, 213955}

    {8980, 26285, 869705, 759531, 939809, 447117, 317385, 292727, 640458, 175984, 690603, 610274, 805259, 613514, 320842, 13784, 893711, 134726, 556162, 132851, 106081, 920724, 949394, 580362, 967767, 846572, 808033, 192839, 481089, 851695, 435557, 911181, 938127, 515978, 437311, 688893, 336794, 388184, 213725, 386035, 190373, 541481}

    Returns: 970151515

  32. {3}

    {742794}

    Returns: 609464783

  33. {453, 44, 7454, 3, 39087, 104921, 3054, 4, 2, 417, 9654}

    {31, 6, 3, 4324, 801, 683999, 401671, 164462, 13, 12466, 3143}

    Returns: 169413764

  34. {70, 6, 126115, 29707, 252, 97, 703114, 689, 346158, 543, 2, 74, 188830, 132289, 85597, 247, 9645, 72390, 700320, 863, 921, 38579}

    {52578, 808247, 225925, 506280, 816684, 962064, 192626, 212336, 949701, 73009, 462181, 902988, 809614, 378976, 70279, 565631, 105844, 843667, 65699, 36963, 863753, 516204}

    Returns: 651350845

  35. {13667}

    {126364}

    Returns: 139568093

  36. {693480, 21201, 219221, 81910, 883835, 446786, 431182, 724581, 909940, 208432, 231932, 607893, 862923, 144126, 496419, 587973, 471185, 816637, 81206, 167365, 934017, 827269, 325105, 82508}

    {302115, 952081, 880155, 945388, 890663, 508914, 385360, 948314, 896127, 196191, 224782, 218354, 219808, 330895, 629708, 171159, 766561, 222648, 944331, 972315, 197162, 755177, 292540, 899674}

    Returns: 786365406

  37. {1, 1002, 1, 100337, 44958, 91, 1197, 8, 30960, 1, 62878, 79, 472491, 1893, 2699, 936, 392196, 977, 1813, 106466, 13588, 16485}

    {3494, 5643, 10, 18, 13, 31, 951623, 3566, 29814, 848947, 3925, 295, 141525, 59, 230, 2, 100861, 95696, 5, 981801, 206, 641654}

    Returns: 31009254

  38. {118231, 381421, 656627, 410624, 486110, 836017, 193581, 291353, 817689, 299839, 35403, 618482, 608930}

    {33844, 805242, 210141, 258888, 833170, 416588, 3647, 770782, 286232, 552796, 566172, 146092, 671682}

    Returns: 407248714

  39. {561426, 646801, 742338, 120477, 750162, 879693, 433089, 657292, 678295, 416033, 270029, 387270, 400388, 381474, 54657, 983454, 360178, 847912, 811328}

    {709030, 85809, 1073, 218, 7155, 916, 5, 57, 3097, 127, 43, 6254, 492995, 265115, 2, 3776, 256483, 14068, 57942}

    Returns: 399398293

  40. {449693, 556988, 596130, 234248, 237144, 308405, 316085, 979729, 124045, 159318, 508926, 709126, 73690, 206320, 540970, 943829, 967541, 957263, 418796, 506090, 554700, 443869, 705222, 221510, 923598, 271075, 264573}

    {16162, 266139, 3007, 238, 1974, 100, 483, 1553, 459, 278, 433, 153, 230671, 55144, 1, 1786, 8716, 55, 2841, 2057, 4909, 15, 227, 3, 585, 112, 6761}

    Returns: 509159010

  41. {1171}

    {848733}

    Returns: 511781070

  42. {427942, 253759, 11, 18638, 179, 409481, 63, 23455, 26680, 346, 28453, 142, 66701, 699, 44919, 51819, 85720, 4083, 5, 9923, 209, 3, 8, 574057, 27418, 130810, 2583, 11, 17, 5, 322, 23, 13, 1835, 14812, 5751, 230, 12488, 335520, 11060, 172}

    {212809, 64150, 480508, 19373, 29017, 883715, 220368, 457387, 687370, 828924, 453164, 786746, 309156, 130569, 333642, 296343, 934768, 682218, 108862, 282462, 403781, 303752, 434146, 198874, 438524, 563554, 134765, 464740, 463689, 486087, 864128, 735827, 926208, 587141, 979505, 4269, 937065, 766814, 178188, 811867, 523611}

    Returns: 707105488

  43. {795095, 451494, 666906, 270615, 850514, 71034, 994348, 599527, 488652, 377175, 912451, 857101, 185866, 787819, 929210, 380484, 56199, 380895, 679617, 899946, 532677, 225430, 60036, 22218, 7129, 244580, 530604, 319570, 608478, 719692, 285836, 707142, 773971, 795304, 109645, 715002, 875568, 820907, 21958, 904012, 212543, 554881, 478982, 807887, 682323, 247111}

    {16031, 780, 78770, 27, 4932, 556493, 886205, 434370, 913, 104, 14, 57566, 886127, 522, 448, 9, 2, 128, 53, 3683, 1, 184717, 6, 644346, 57, 174162, 16, 10589, 12, 303, 154406, 108482, 128195, 202596, 1453, 5, 108797, 2678, 2696, 91257, 1891, 23098, 4, 216069, 32212, 165466}

    Returns: 944428627

  44. {1, 759, 157}

    {984001, 863121, 758710}

    Returns: 168872183

  45. {3, 4, 464095, 254685, 49484, 7776, 2348, 6312, 15, 31, 27, 3, 65003, 40, 35105, 228, 822310, 278, 18076, 308, 172934, 1958, 23097, 17679, 15235, 1, 215, 1346, 120883, 418799, 1736, 71385, 65154}

    {1909, 966364, 171777, 785251, 280309, 79188, 308475, 209788, 376023, 339753, 189284, 287760, 638774, 413334, 512044, 543171, 268825, 589524, 454412, 64360, 533072, 438302, 688481, 440621, 26345, 888256, 370335, 906546, 579721, 907399, 945387, 89992, 111962}

    Returns: 926642431

  46. {293370, 262800, 62308, 266155, 129370, 875874, 110645, 551448, 751850, 674095, 817225, 286730, 461369, 183666, 589141, 191364, 169816, 486149, 86077, 795130, 540394, 50679, 533879, 374295, 991194, 900365, 720406, 404143, 53495, 120420, 577081, 393258, 317816, 592010, 855633, 850784, 508786, 714988, 335022, 665149, 859676, 83884, 268287, 384915}

    {1811, 46, 38, 39, 13444, 1413, 111069, 307, 16149, 94, 4, 285, 1252, 16156, 636, 25008, 24473, 554, 2074, 49843, 104, 10, 36, 271, 1138, 515, 9, 7, 160, 2, 24, 16768, 349492, 18, 56, 206, 28, 61, 1, 37, 50, 215146, 3294, 402245}

    Returns: 748246395

  47. {832676}

    {706117}

    Returns: 79636166

  48. {613, 942, 40758}

    {26082, 437, 1}

    Returns: 469129824

  49. {608058, 347589, 492227, 276498, 914167, 16072, 817377, 382249, 520803, 571482, 686313, 570256, 258733, 730075, 290194, 804893, 118167, 604174, 505059, 530715, 771679, 645114, 178660, 130018, 489077, 52937, 227307, 611081, 546104, 344749, 534013, 689173, 730231, 44115, 347665, 720821, 399748, 498946, 87102, 800355, 458735, 287305, 590764, 76288, 359218}

    {217, 31, 634, 99402, 45, 2, 2483, 531685, 44, 1, 93, 124, 7, 29, 42, 22, 2903, 13, 589, 100, 3, 112665, 21633, 14, 81439, 94902, 48, 23123, 10, 101715, 4292, 17796, 15, 566, 27, 323, 235771, 164842, 84, 869050, 348304, 288666, 1890, 62, 11971}

    Returns: 450648549

  50. {5, 4, 3234, 960, 172679, 231476, 28184, 16812, 3136, 256986, 6, 49918, 59440, 289472, 27767, 4207, 16206, 6, 1407, 913, 9, 27, 1712, 64, 2, 628482, 268406, 4, 7, 91, 382, 24834, 89, 94590, 5704, 634187, 477, 5555}

    {682239, 428770, 552005, 998880, 67099, 587231, 43508, 152300, 767876, 447642, 463172, 496794, 370991, 65202, 437288, 790476, 407389, 857463, 779112, 190864, 449713, 206735, 275558, 240997, 566064, 657770, 381217, 835110, 621487, 818666, 621236, 82080, 204255, 24045, 662073, 666050, 405830, 960605}

    Returns: 393717665

  51. {183847, 367144, 84678, 323030, 521057, 602900, 1349, 103729, 676156, 703345, 534237, 851066}

    {588972, 406958, 782854, 122226, 535384, 249102, 648020, 878922, 498369, 118292, 552313, 60502}

    Returns: 878926177

  52. {628832, 587836, 208156, 102587, 786743, 880350, 141830, 463549, 982041, 784798, 318030, 734921, 257288, 394079, 115208, 599148, 21408, 199359, 594863, 352039, 212833, 15107, 362516, 150184, 297348, 778477, 797255, 496958, 747896, 789174, 49881, 622688, 836057, 232035, 643311, 221882, 593722, 659994, 456546, 822514, 181691, 217240, 337158, 490971, 21291, 526597, 192275, 632963, 419890, 964760}

    {350229, 106350, 6099, 4, 99830, 811, 96, 106387, 229, 97274, 163, 754, 199566, 29, 3225, 8340, 44913, 663116, 39, 19, 30278, 71, 311, 3183, 1, 31418, 52215, 789942, 602844, 1307, 22, 167, 501, 435841, 2498, 1023, 3250, 30246, 1857, 966342, 931588, 5766, 324305, 7056, 125718, 98, 6, 15524, 1502, 147}

    Returns: 646764574

  53. {4885, 127, 226927, 609792, 11124, 14, 53, 6682, 7206, 30, 11, 55681, 6, 1704, 24710, 145, 37, 1, 3, 56, 82254, 457802}

    {761872, 701747, 796163, 199758, 264586, 929905, 255702, 780081, 423180, 259106, 152223, 335208, 489062, 411717, 968634, 784500, 82391, 393631, 326015, 417043, 260039, 141524}

    Returns: 151259311

  54. {44892, 65389, 407417, 142844, 3393, 10903, 2774, 473999, 487, 21, 62, 13187, 43, 984926, 1530, 513, 1514, 32, 7543, 132, 82}

    {4, 1, 554735, 88850, 1587, 847, 2, 1227, 38, 119673, 149466, 3436, 193, 62, 3419, 324, 12538, 8512, 24413, 1285, 9223}

    Returns: 53619990

  55. {38932, 889820, 327473, 702316, 859542, 694440, 212589, 129423, 916695, 610669, 620747, 503538, 495001, 782433, 539320, 191735, 851162, 380093, 206725, 379178, 773715, 270872, 167124, 72547, 828242, 23181, 270205, 437372, 469965, 70185, 46936, 993797}

    {950579, 446599, 127757, 867259, 300397, 435248, 39439, 346461, 999319, 235349, 714145, 149195, 160650, 877035, 843089, 398205, 136406, 272655, 434429, 545578, 557217, 708027, 73842, 749426, 75508, 341473, 997934, 619128, 886022, 599166, 547565, 995298}

    Returns: 757858517

  56. {910700, 119518, 105645, 754081, 254314, 245995, 407365, 234758, 112598, 607551, 975697, 629478, 221571, 863642, 567144, 167305, 576422, 24948, 40639, 423600, 931061, 621756, 216160, 24952, 748147, 880365, 234813, 548425, 886382, 246196, 308995, 68023, 902627, 979051}

    {34, 1772, 839685, 152834, 2, 902, 1142, 174834, 809512, 9180, 77744, 12, 85440, 20, 14, 104, 48, 873881, 659947, 404, 3553, 47, 28, 54105, 1146, 12794, 1, 847250, 402976, 537, 51, 123, 226100, 2531}

    Returns: 557428938

  57. {94672}

    {960648}

    Returns: 712840460

  58. {6, 35150, 18942, 29, 123, 830, 68772}

    {202877, 372478, 181456, 280586, 414043, 177188, 418390}

    Returns: 529185008

  59. {160050, 475025, 740643, 672041, 681651, 527161, 620043, 932548, 289664, 161003, 60946, 804228, 634512, 812089, 944193, 262804}

    {67280, 558031, 98830, 31398, 112216, 480, 98109, 590650, 432119, 2, 2866, 1341, 231, 381082, 824, 281}

    Returns: 547623824

  60. {438317, 470494, 96547, 471784, 207569, 714017, 145923, 297709, 700740, 635399, 678239, 642310, 488071, 442489, 583965, 589807, 325925, 349624, 657584, 925715, 357887, 45288, 952282, 856949, 916738, 771667, 100611, 842793, 190585, 18495, 134401, 929933, 934684, 903396, 983744, 990551, 554939, 789350, 346891, 286578, 906787, 383060, 218579, 317705, 69287, 5165}

    {1265, 420984, 156727, 4466, 87, 118, 796410, 7571, 41, 10668, 37, 3, 13, 32468, 11, 217891, 424444, 24, 381294, 148007, 147, 199175, 1002, 23239, 253193, 227, 183834, 3945, 1737, 58156, 188, 5, 294, 32, 93, 474, 25, 38706, 2, 10423, 29326, 1, 842972, 202, 7, 98}

    Returns: 32731665

  61. {2873, 207244, 9, 11791, 1065, 14786, 236, 1, 3, 148, 55, 2810, 6948, 872, 14, 294, 541, 5, 3, 1, 26297, 7422, 11, 40, 8}

    {9, 39762, 1002, 127, 32035, 267936, 6, 4, 300, 2984, 80033, 903, 10652, 1, 67, 61, 3513, 13513, 48601, 37, 813720, 5557, 517668, 50544, 117735}

    Returns: 699567454

  62. {357143}

    {404701}

    Returns: 449831723

  63. {703119, 653291, 485736, 175394, 273790, 543820, 762407, 17435, 114193, 852377, 936806, 494497, 646664, 765368, 714699, 830522, 93054, 62049, 770578, 963902, 684512, 105433, 767284, 474287, 889614, 690838}

    {404055, 127117, 901955, 714223, 272424, 333040, 966789, 770274, 243332, 128509, 467264, 702858, 56495, 217660, 484374, 522076, 986415, 942369, 680066, 271705, 534085, 39692, 213263, 501661, 365750, 65118}

    Returns: 503726240

  64. {23, 1, 14, 5, 111, 120831, 3619, 7, 1403, 14361, 66, 12, 10856, 3, 4304, 1626, 2036, 297, 1459, 2078, 4, 23843, 2642, 225, 28482, 906, 47496, 6, 720435, 351, 3747, 4, 778, 1, 39316, 197, 4, 1, 3447}

    {856456, 85718, 7263, 288, 7424, 394, 99, 5139, 68, 35, 4574, 25, 256, 65, 2, 555, 12916, 104, 20191, 171, 5, 653, 256046, 912553, 78, 117555, 278537, 544984, 1, 9012, 12039, 695, 3, 6, 36, 1008, 28, 10, 7912}

    Returns: 176584899

  65. {919191, 272552}

    {10747, 7433}

    Returns: 808661160

  66. {382528}

    {782799}

    Returns: 82118760

  67. {64, 311, 2515, 135174, 810, 4, 7, 158160, 127, 20038, 23236, 8491, 576046, 603984, 52, 27, 2898, 1489, 6684, 9227, 68623, 124936, 13, 2, 687704, 261879, 7127, 3, 1995, 459085, 884939, 235, 1, 218, 33918, 998499, 59, 1982, 571348, 82428}

    {26, 27, 243900, 7, 40, 5, 146976, 221, 14690, 118, 446, 91751, 245368, 325, 398, 18, 3921, 10894, 32260, 16, 510, 1730, 105, 8, 70, 688626, 367672, 1, 43, 11214, 105035, 119, 3, 14, 7893, 12, 315084, 4, 46035, 2128}

    Returns: 301840876

  68. {526227, 35668, 1, 1613, 170641, 3, 247, 102, 15, 21, 20255, 24548, 891964, 29, 5, 7223, 40, 26, 13488, 1, 1515, 5816, 709, 494, 154224, 1728, 49933, 18, 5, 71246, 213, 27, 503805, 490754, 74175, 110403, 121563, 14, 1, 74, 601585, 473853}

    {230788, 25, 21581, 77, 75, 167, 251934, 29, 3190, 4108, 678, 324, 106, 10, 22190, 318, 134885, 25421, 36, 7286, 4, 136, 690, 29878, 4592, 523765, 127, 1543, 5, 918, 23, 2, 6348, 2372, 730, 1, 508189, 282312, 258, 616550, 130, 19806}

    Returns: 689573849

  69. {622388, 427573, 449107, 876666, 233853, 801138, 898209, 675881, 422955, 691023, 818072, 326944, 240653, 685190, 963560, 406356, 697550, 520268, 322335, 648951, 283066, 966890, 474225, 272259, 71289, 312745, 784789, 650647, 251279, 711034, 896619, 31564, 954773, 585602, 901431, 541896, 477772, 676027}

    {1, 3, 574, 4, 796, 653, 15, 14, 404, 49, 88, 47, 14381, 144, 65430, 99396, 84, 275, 50587, 10, 8783, 127061, 70, 38, 3328, 7594, 3556, 154514, 145489, 7525, 25, 738780, 2, 242052, 9, 23, 62, 56431}

    Returns: 80842863

  70. {1000000, 999999, 999998, 999997, 999996, 999995, 999994, 999993, 999992, 999991, 999990, 999989, 999988, 999987, 999986, 999985, 999984, 999983, 999982, 999981, 999980, 999979, 999978, 999977, 999976, 999975, 999974, 999973, 999972, 999971, 999970, 999969, 999968, 999967, 999966, 999965, 999964, 999963, 999962, 999961, 999960, 999959, 999958, 999957, 999956, 999955, 999954, 999953, 999952, 999951 }

    {999951, 999952, 999953, 999954, 999955, 999956, 999957, 999958, 999959, 999960, 999961, 999962, 999963, 999964, 999965, 999966, 999967, 999968, 999969, 999970, 999971, 999972, 999973, 999974, 999975, 999976, 999977, 999978, 999979, 999980, 999981, 999982, 999983, 999984, 999985, 999986, 999987, 999988, 999989, 999990, 999991, 999992, 999993, 999994, 999995, 999996, 999997, 999998, 999999, 1000000 }

    Returns: 940374042

  71. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    {999951, 999952, 999953, 999954, 999955, 999956, 999957, 999958, 999959, 999960, 999961, 999962, 999963, 999964, 999965, 999966, 999967, 999968, 999969, 999970, 999971, 999972, 999973, 999974, 999975, 999976, 999977, 999978, 999979, 999980, 999981, 999982, 999983, 999984, 999985, 999986, 999987, 999988, 999989, 999990, 999991, 999992, 999993, 999994, 999995, 999996, 999997, 999998, 999999, 1000000 }

    Returns: 49436268

  72. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    {1000000, 999999, 999998, 999997, 999996, 999995, 999994, 999993, 999992, 999991, 999990, 999989, 999988, 999987, 999986, 999985, 999984, 999983, 999982, 999981, 999980, 999979, 999978, 999977, 999976, 999975, 999974, 999973, 999972, 999971, 999970, 999969, 999968, 999967, 999966, 999965, 999964, 999963, 999962, 999961, 999960, 999959, 999958, 999957, 999956, 999955, 999954, 999953, 999952, 999951 }

    Returns: 49436268

  73. {1, 1000 }

    {11312, 12 }

    Returns: 737000422

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: