### PROBLEM LINK:

Author: Ankit Srivastava and Uttam Kanodia

Tester: Roman Rubanenko

Editorialist: Amit Pandey

### DIFFICULTY:

Easy-Medium.

### PREREQUISITES:

Game theory and Combinatorics.

### PROBLEM:

A game is played with the rule that a non-zero number of the stones must be removed from the first non-empty pile. Find the number of permutations of the piles, in which the first player has a winning strategy.

### QUICK EXPLANATION:

Find a way to check if a given permutation is the winning permutation, followed by finding the number of permutations which satisfy the given condition.

### EXPLANATION:

The problem can be solved using various claims.

**Claim 1: If each pile contains exactly 1 stone. Now, if number of piles is even, then second player will win. Otherwise, first player will win.**

**Reason:** The reason being that each player will have exactly one way of making a move, i.e. emptying the current pile.

**Claim 2: If the first pile contains more than one stone, then first player will always win.**

**Reason:** Suppose that piles are numbered as 1,2,3...N. Number of stones in piles are given as A_1,A_2,....A_N with the condition A_1 \ge 2.

**Case 1:** Suppose in piles A_2,A_3,...A_N, first player has winning strategy, then first player will remove A_1-1 number of stones from the first pile and second player will be enforced to remove remaining 1 stone. First player will have winning strategy on remaining piles.

**Case 2:** Suppose in piles A_2,A_3,...A_N, first player doesn’t have winning strategy, then first player will empty first pile in single move. So, when game will arrive as pile 2, second player will not have the winning strategy, hence first player will have winning strategy.

**Claim 3:** Now we can claim very easily that first player will win if permutation is in such a way that A_1 = 1, A_2 = 1,... A_x = 1, A_{x+1} != 1, and x is an even number, because when the game will arrive at pile number (x+1), first player will be making first move and he will win according the points given above.

**How to count number of permutations such that number of 1’s in the beginning is even? **

Suppose count of 1's in the array A is M. Each distinct number of array A(except 1) is in array B, i.e., B_1, B_2,...B_K, and count of B_i in array A is cnt[B_i].

Now count the number of permutations in which number of 1’s in the beginning is **at least** x. To do that, keep x 1's in the beginning and permute rest of the numbers.

Number of permutations in which number of 1's in the beginning is exactly 2r.

So, number of permutations in which numbers of 1’s in the beginning is even:

K is a constant which can be calculated in O(N) time, and we can calculate it in the beginning. So, Number of permutations can also be calculated in O(N) time.

### Solution:

Setter’s solution can be found here

Tester’s solution can be found here