TopCoder Statistics - Problem Statement

Problem Statement

This problem has an unusual time limit: 3 seconds

You are given three ints: n, m, k.

We are in an k-dimensional space that has an orthogonal coordinate system. We are interested in k-dimensional hyperboxes that have sides parallel to the axes of the coordinate system. Formally, each such hyperbox can be described by 2k coordinates: x_{1,1}, x_{1,2}, x_{2,1}, x_{2,2}, ..., x_{k,1}, x_{k,2}. This sequence of coordinates denotes the hyperbox that contains points with the following property: for each i, the i-th coordinate of the point is between x_{i,1} and x_{i,2}, inclusive.

Each hyperbox must have a positive hypervolume. That is, for each i, x_{i,1} must be strictly smaller than x_{i,2}. Additionally, in this problem we will restrict our attention to hyperboxes with the following property: each of the 2k coordinates of the hyperbox is an integer between 1 and n, inclusive.

Two hyperboxes intersect if they share at least one point, so touching at a corner still counts as intersecting. Two hyperboxes are disjoint if they do not intersect.

We want to select m mutually disjoint hyperboxes with the above properties, and we want to label them from 1 to m. Count and return the number of ways to do so, modulo 998244353.

(Note that the hyperboxes are labeled. Two ways of selecting them are different even if just the labels differ.)

Definition

Class:: Hyperboxes
Method:: findCount
Parameters:: int, int, int
Returns:: int
Method signature:: int findCount(int n, int m, int k)
(be sure your method is public)

Constraints

n will be between 2 and 10^9.
m will be between 1 and 6.
k will be between 1 and 10^9.

Examples

5

1

1

Returns: 10

We want to choose a single 1-dimensional hyperbox, i.e., a line segment. The coordinates of its endpoints must be integers between 1 and 5, inclusive. The number of ways to select the hyperbox is (5 choose 2) = 10.
5

2

1

Returns: 10

Now we want to choose two disjoint 1-dimensional hypercubes. In other words, we want two disjoint line segments in the given range of coordinates. There are 10 ways of doing so. Remember that the hyperboxes are labeled. The choice where hyperbox 1 has coordinates (1,2) and hyperbox 2 has coordinates (3,5) differs from the choice where hyperbox 1 has coordinates (3,5) and hyperbox 2 has coordinates (1,2).
5

1

2

Returns: 100

Here we want a single 2-dimensional hyperbox - in other words, a rectangle.
4

2

2

Returns: 140
710

3

710

Returns: 980029536

Don't forget about the mod.
2

1

1

Returns: 1
10

6

1

Returns: 0
4

5

987

Returns: 457998142
1000000000

6

1000000000

Returns: 907279660
296

1

194990929

Returns: 443362819
754234475

1

374186162

Returns: 442055725
321330833

1

947034694

Returns: 987256154
24313670

1

292051389

Returns: 127521238
890331224

1

456892725

Returns: 426776015
190955579

1

7663458

Returns: 505951038
461728571

1

127850932

Returns: 125174373
8260502

1

765318491

Returns: 801432598
183658290

1

988367072

Returns: 150391676
292696232

1

903645520

Returns: 879139823
204967995

1

878489639

Returns: 645455587
889344347

1

641354184

Returns: 89334322
221849414

1

233968412

Returns: 52091357
784383970

1

169684209

Returns: 224694118
537758116

1

60555347

Returns: 922808607
403821382

1

361722636

Returns: 814399489
972039205

1

438064673

Returns: 794868888
908981888

1

811565365

Returns: 244754557
707560940

1

609582106

Returns: 237150155
288538192

1

49676826

Returns: 911725445
641290376

2

3647

Returns: 591782253
254857208

2

128016

Returns: 410101665
994128266

2

327635068

Returns: 417734994
379205009

2

296854827

Returns: 96213967
847453062

2

512850347

Returns: 915480192
545857698

2

671841705

Returns: 733020403
903707009

2

842232847

Returns: 964861926
1058792

2

349695636

Returns: 617216312
116989500

2

701687103

Returns: 613469722
702689093

2

87815041

Returns: 556114336
907006663

2

883934467

Returns: 348474209
264062244

2

160417679

Returns: 147766766
455857748

2

891073286

Returns: 879347973
734187721

2

55455380

Returns: 818381283
92022802

2

284934589

Returns: 126184498
410575068

2

17404360

Returns: 382002033
989548277

2

38

Returns: 507628277
267081704

2

456

Returns: 914490160
352810132

2

351010849

Returns: 76881908
41853765

2

719839838

Returns: 176620212
918367153

3

890322185

Returns: 348301356
772834935

3

458664281

Returns: 26757260
985299257

3

509166884

Returns: 790545516
514211187

3

511439188

Returns: 950666817
284059548

3

113701249

Returns: 651419526
800167065

3

659910599

Returns: 973984294
811250318

3

383315002

Returns: 734104360
474087075

3

238116540

Returns: 146672820
293867255

3

416613592

Returns: 232796604
771843644

3

188226618

Returns: 810564408
201437908

3

700342122

Returns: 974654335
37070780

3

444434911

Returns: 235637301
198114183

3

844335967

Returns: 489960516
154330134

3

731057576

Returns: 313779996
619160519

3

678902748

Returns: 732184354
712834810

3

373681487

Returns: 993699589
967413268

3

433111247

Returns: 854329460
58903113

3

703655651

Returns: 10805184
555168447

3

803282818

Returns: 937064293
759572596

3

86412361

Returns: 526426428
265588879

4

780551363

Returns: 743722461
175921

4

523050696

Returns: 191102851
975103933

4

134677973

Returns: 32233167
129959976

4

28

Returns: 396944561
464408117

4

448376965

Returns: 768013056
449092318

4

916505583

Returns: 228265127
650547385

4

114834

Returns: 448609866
593255350

4

700197202

Returns: 642216456
696215213

4

224836995

Returns: 661857339
753600921

4

604300326

Returns: 634470754
994763003

4

646166677

Returns: 352176224
264068749

4

581052789

Returns: 154269654
190562175

4

52164

Returns: 226565326
877906236

4

946688607

Returns: 270462103
274238246

4

955384027

Returns: 914304982
226499155

4

208869723

Returns: 923051124
390930086

4

450327618

Returns: 455638346
876587907

4

394870154

Returns: 18245979
317110115

4

51822525

Returns: 6149236
182128339

4

194202581

Returns: 274416941
597634215

5

302672723

Returns: 410148274
119692872

5

835823359

Returns: 238580709
89572757

5

523973439

Returns: 319536357
508528232

5

695246213

Returns: 229785086
133007203

5

550382004

Returns: 103321305
444025863

5

170841201

Returns: 212714074
761359445

5

721863390

Returns: 528379892
760854563

5

381289990

Returns: 517171403
274953624

5

553510407

Returns: 739387994
536593191

5

717614612

Returns: 361493233
131393351

5

95859550

Returns: 783477573
71694802

5

233391296

Returns: 804012527
454969995

5

557693129

Returns: 775420640
84253339

5

275707124

Returns: 501867139
534700173

5

291639381

Returns: 919091844
2785

5

666819

Returns: 129804903
466723873

5

739951595

Returns: 493424192
22708382

5

945264071

Returns: 520359656
601677039

5

403668755

Returns: 971646930
692044333

5

552161659

Returns: 871271538
1353851

6

332929473

Returns: 577559255
28706003

6

38800717

Returns: 621029416
490810861

6

39531956

Returns: 595647027
749955679

6

513791236

Returns: 805730795
515107233

6

104902762

Returns: 708226135
868953577

6

675912510

Returns: 815808459
465940336

6

97457645

Returns: 496720230
888161867

6

30781031

Returns: 900377049
646840578

6

722907570

Returns: 135788862
1697763

6

900751625

Returns: 715378430
939155062

6

4835

Returns: 911887548
914595145

6

494866563

Returns: 681392648
3646003

6

776329096

Returns: 20019217
823138974

6

5117

Returns: 220991756
350425620

6

736514

Returns: 41140708
258299819

6

526446337

Returns: 925728399
591196772

6

488296024

Returns: 828399096
866547600

6

245975475

Returns: 702590629
505058337

6

177463162

Returns: 834241685
797685823

6

651414865

Returns: 323617441

Statistics

Problem Statement for "Hyperboxes"

Problem Statement

Definition

Constraints

Examples