TopCoder Statistics - Problem Statement

Problem Statement

You have a set S which contains N distinct objects numbered from 0 to N - 1. You are also given 3 integers P, Q, and K.

We are going to execute the following steps:

Choose a subset A of S uniformly at random. (Each of the 2^|S| possible subsets is chosen with the same probability.)
Let R = |A|.
Choose an integer Y uniformly at random from the set {0, 1, ..., K}.
Compute the weirdness of your choices: the value R^Y * (R+P)^K-Y / (R+Q).

Find the expected value of weirdness: a fraction p/q. Return that fraction modulo 1,000,000,007.

Definition

Class:: TooMuchExpectation
Method:: findExpectedValue
Parameters:: int, long, int, int
Returns:: int
Method signature:: int findExpectedValue(int N, long P, int Q, int K)
(be sure your method is public)

Notes

Use 00 = 1.
It is guaranteed that P modulo 1,000,000,007 is not equal to 0.
If the correct answer is the reduced fraction p/q, the correct return value is (p*q-1) modulo 1,000,000,007, where q-1 is the inverse element to q.
For inputs that meet the given constraints the correct return value always exists.

Constraints

N will be between 1 and 900,000,000, inclusive.
P will be between 1 and 10,000,000,000,000,000, inclusive.
Q will be between 1 and 100,000, inclusive.
K will be between 1 and 500, inclusive.
P modulo 1,000,000,007 is not equal to 0.

Examples

721

400

828

329

Returns: 745150960
808

499

530

384

Returns: 100413881
831

325

865

54

Returns: 360470513
578

383

926

377

Returns: 608011535
598

636

963

255

Returns: 21662201
913

414

836

51

Returns: 842162873
791

919

579

74

Returns: 78820406
574

601

525

275

Returns: 504652058
571

199

683

24

Returns: 188183820
875

921

570

251

Returns: 928685714
476

52

715

302

Returns: 619642843
240

544

548

39

Returns: 48481462
281

600

972

209

Returns: 517702045
727

869

43

365

Returns: 790532481
740

796

832

197

Returns: 70636424
137

779

481

293

Returns: 653702142
262

896

255

133

Returns: 259097188
886

226

751

300

Returns: 54411798
288

638

690

456

Returns: 870301274
159

355

405

72

Returns: 886846246
659

4645817790544334

42002

169

Returns: 217549548
415

9943325593058255

96510

97

Returns: 322328375
680

3082982852062306

46857

263

Returns: 356457310
620

7269729526914656

20505

180

Returns: 778236598
113

8851519094020995

19479

324

Returns: 388554509
65

1034476463774957

31376

327

Returns: 5402020
613

3976511528473505

47317

57

Returns: 874405511
799

9596782366703881

4699

87

Returns: 340467816
614

841940899667823

84540

247

Returns: 759141635
694

7186008835922563

21493

287

Returns: 282036145
293

2544549653616603

678

34

Returns: 609536020
384

9379590169907054

30005

410

Returns: 858871436
588

2967425119859737

76043

177

Returns: 586591803
357

5283831265520666

67733

57

Returns: 107467499
474

1970302708701592

772

92

Returns: 370810170
118

9562137501020952

61165

24

Returns: 276521111
289

2287490886183945

94794

415

Returns: 263490471
574

9229294389407034

50936

56

Returns: 282927228
923

1147702409502046

6647

440

Returns: 104526154
483

2253202558138767

34765

463

Returns: 853176931
487

8380917413674440

51171

333

Returns: 981710768
96

1428989475691882

71814

169

Returns: 200919960
927

9316815620672440

12647

493

Returns: 945129677
22

2949518722339931

39260

251

Returns: 137620228
277

2437750647784414

84029

422

Returns: 74995028
565

522360380776498

39623

347

Returns: 968943991
168

4800546602955052

47325

441

Returns: 52296411
583

3235583422028034

2050

245

Returns: 528634890
922

3736324857396434

14976

66

Returns: 54416667
100

3428930159082780

36388

51

Returns: 232186363
713004389

9999999999678650

99991

477

Returns: 239441797
320295326

9999999999797435

99900

432

Returns: 396222374
754444856

9999999999616637

99949

435

Returns: 736418481
118329214

9999999999538829

99979

433

Returns: 826245546
676075518

9999999999020511

99922

491

Returns: 52434919
263240971

9999999999184335

99955

414

Returns: 496981841
322234430

9999999999924581

99969

408

Returns: 318976760
459987697

9999999999422773

99955

459

Returns: 920039441
11877826

9999999999739267

99962

461

Returns: 8232395
141972247

9999999999555753

99964

450

Returns: 527409497
590844564

9999999999151803

99970

480

Returns: 181258668
609383590

9999999999111726

99901

469

Returns: 565784475
671964923

9999999999838167

99923

409

Returns: 773579025
649381896

9999999999580470

99964

430

Returns: 29161253
898536322

9999999999172051

99999

495

Returns: 945613171
771228389

9999999999931833

99948

494

Returns: 367485771
521779952

9999999999388215

99999

486

Returns: 108921446
129405991

9999999999481753

99962

454

Returns: 530241088
365295440

9999999999418042

99978

413

Returns: 600928362
27569143

9999999999061055

99922

402

Returns: 244103154
378243306

9999999999059352

99965

421

Returns: 397099872
354323132

9999999999514752

99913

421

Returns: 251866782
198719558

9999999999704282

99980

480

Returns: 701059410
634563362

9999999999677686

99971

412

Returns: 685826601
746754351

9999999999102459

99915

468

Returns: 97641501
140322064

9999999999179853

99934

459

Returns: 824752206
878802860

9999999999459511

99995

401

Returns: 104878734
72585391

9999999999614860

99997

485

Returns: 567099370
411074824

9999999999183863

99997

413

Returns: 891670118
484079209

9999999999475739

99925

444

Returns: 608920199
899990316

9999999999614925

99937

403

Returns: 758449408
899999260

9999999999973474

99910

426

Returns: 877299753
899995247

9999999999636407

99947

445

Returns: 552133561
899990280

9999999999147393

99932

460

Returns: 341764750
899994727

9999999999571762

99915

417

Returns: 670592382
899999558

9999999999901292

99910

477

Returns: 900311679
899997317

9999999999221803

99963

479

Returns: 722704930
899990409

9999999999084120

99965

414

Returns: 678298423
899998379

9999999999626663

99919

481

Returns: 577147741
899990575

9999999999411633

99967

404

Returns: 106414821
899991903

9999999999137235

99914

478

Returns: 519398399
899998679

9999999999382959

99948

438

Returns: 488233918
899999335

9999999999969030

99947

450

Returns: 318166523
899999923

9999999999992432

99902

450

Returns: 767632093
899993514

9999999999820676

99926

445

Returns: 189610532
899997639

9999999999118444

99936

496

Returns: 613825983
899992371

9999999999912100

99912

500

Returns: 235533315
899991386

9999999999405278

99959

421

Returns: 412422406
899998695

9999999999331377

99975

474

Returns: 731719427
899992649

9999999999176202

99991

466

Returns: 36978018
899999924

9999999999999996

99970

479

Returns: 449913732
899999912

9999999999999990

99967

472

Returns: 110073281
899999967

9999999999999990

99970

454

Returns: 253034485
899999944

9999999999999960

99985

495

Returns: 699167161
899999917

9999999999999965

99964

479

Returns: 620769178
900000000

9999999999999986

99962

470

Returns: 250754662
899999983

9999999999999954

99982

490

Returns: 262853104
899999903

9999999999999966

99972

496

Returns: 518144813
899999976

9999999999999979

99997

459

Returns: 146502471
899999964

9999999999999988

99992

457

Returns: 144224167
899999973

9999999999999958

99984

463

Returns: 144909032
899999967

9999999999999950

99977

482

Returns: 597697679
899999977

9999999999999951

99974

494

Returns: 51158456
899999933

9999999999999984

99965

493

Returns: 901518407
899999907

9999999999999975

99979

480

Returns: 778592180
899999984

9999999999999956

99970

494

Returns: 466977345
899999958

9999999999999966

99996

463

Returns: 864785420
899999922

9999999999999965

99980

466

Returns: 327307896
899999921

9999999999999976

99998

490

Returns: 797866952
899999902

9999999999999963

99989

498

Returns: 342995401
899999910

9999999999999952

99952

457

Returns: 706798996
899999914

9999999999999991

99952

491

Returns: 431893084
899999980

9999999999999957

99995

494

Returns: 329399313
899999923

9999999999999965

99995

462

Returns: 183200374
899999979

9999999999999967

99951

489

Returns: 629083087
899999920

9999999999999985

99959

480

Returns: 965007078
899999986

9999999999999972

99988

494

Returns: 811481604
899999904

9999999999999975

99977

484

Returns: 982758001
899999923

9999999999999995

99997

493

Returns: 687981076
899999944

9999999999999971

99978

456

Returns: 137174501
899999969

9999999999999993

99950

491

Returns: 421759346
899999941

9999999999999992

99973

468

Returns: 160214029
899999940

9999999999999991

99971

471

Returns: 112212790
899999937

9999999999999986

99960

460

Returns: 672795611
899999940

9999999999999960

99960

497

Returns: 319686917
899999961

9999999999999960

99973

453

Returns: 145190846
899999961

10000000000000000

99983

472

Returns: 577198181
899999952

9999999999999969

99992

499

Returns: 763003842
900000000

9999999999999988

99996

466

Returns: 125082247
899999923

9999999999999989

99966

492

Returns: 370988324
899999920

9999999999999996

99971

457

Returns: 462655349
899999937

9999999999999981

99950

471

Returns: 688213693
899999963

9999999999999993

99954

485

Returns: 30683936
899999990

9999999999999957

99966

468

Returns: 797035855
899999957

9999999999999986

99963

455

Returns: 141642525
899999971

9999999999999993

99960

498

Returns: 437507069
899999963

9999999999999993

99987

458

Returns: 73714867
899999934

9999999999999981

99951

496

Returns: 37095192
899999965

9999999999999979

99968

465

Returns: 387674007
899999909

9999999999999965

99972

485

Returns: 323882012
1

1

1

1

Returns: 625000005

The given set is S = {0}. We have four equally likely cases: We choose the subset {} and Y=0: weirdness is 00 * 11 / 1 = 1. We choose the subset {} and Y=1: weirdness is 01 * 10 / 1 = 0. We choose the subset {0} and Y=0: weirdness is 10 * 21 / 2 = 1. We choose the subset {0} and Y=1: weirdness is 11 * 20 / 2 = 1/2. Thus, the expected weirdness is (1 + 0 + 1 + 1/2) / 4 = 5/8. The correct return value is (5 * 8-1) modulo 1000000007 = (5 * 125000001) modulo 1000000007 = 625000005.
1

1

1

2

Returns: 750000006

Here the exact answer is 3/4.
100

100

100

100

Returns: 224580006
900000000

10000000000000000

10000

500

Returns: 459797508

Statistics

Problem Statement for "TooMuchExpectation"

Problem Statement

Definition

Notes

Constraints

Examples