RainbowNim | Topcoder Archive

Problem Statement

Alice and Bob are playing a game with some piles of stones. The i-th pile contains pile[i] stones with color color[i].

In a single turn, a player has two options:

Take a positive number of stones from a single pile.
Choose a color, and take at least one stone and a total of at most m stones from piles of that color.

The first player unable to make a move loses the game.

You are given the the description of the piles of the stones and the number m. Return the number of subsets of piles such that Alice will win if she starts the game on just that subset of piles. Return this modulo 998244353.

Definition

Class:: RainbowNim
Method:: countSubsets
Parameters:: int[], int[], int
Returns:: int
Method signature:: int countSubsets(int[] pile, int[] color, int m)
(be sure your method is public)

Constraints

n will be between 1 and 250, inclusive.
pile, color will contain exactly n elements.
Each element of pile will be between 1 and 250, inclusive.
Each element of color will be between 1 and 250, inclusive.
m will be between 1 and 250, inclusive.

Examples

```
{1, 1}
```
```
{1, 1}
```
```
2
```
```
Returns: 3
```
In this case, Alice can win with any non-empty subset of the piles. If there is only one pile, Alice can win by taking all the stones in that pile. If both piles are present, she can take 1 stone from each pile.
```
{1, 1}
```
```
{1, 250}
```
```
2
```
```
Returns: 2
```
In this case, Alice can't win if both piles are initially present.
```
{2, 2}
```
```
{1, 1}
```
```
3
```
```
Returns: 2
```
```
{250}
```
```
{1}
```
```
2
```
```
Returns: 1
```
```
{17,11,5,8,17}
```
```
{1,1,2,2,3}
```
```
2
```
```
Returns: 30
```

{3,1,4,1,5,9,2,6,5,3,5,8,9,7,9}

{3,2,3,8,4,6,2,6,4,3,3,8,3,2,7}

Returns: 30880

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

Returns: 176322511

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.