SuperNim High#2877
Nim is a game for two players who take turns picking objects from several piles. On each turn, a player selects a non-empty pile and removes any non-zero number of objects from it. The player who cannot make a move on their turn (i.e., their opponent took the last object on the previous move) loses.
This game has been completely analyzed mathematically. Losing positions are those where, no matter what moves the player to move makes, the opponent can always respond to ensure the player's defeat (i.e., the opponent has a winning strategy). Winning positions are those where, regardless of the opponent's future moves, the player to move can always play so as to ensure their victory (i.e., the player has a winning strategy). It is known that the outcome of a position is determined by the nim-sum: p_1 \operatorname{xor} p_2 \operatorname{xor} \ldots \operatorname{xor} p_N, where p_i is the number of objects in the -th pile, and denotes the bitwise exclusive "or" operation (binary addition without carrying). If this sum is nonzero, the position is winning; if it is zero, the position is losing.
In this problem, we are dealing with a large number of piles. Your task is, given the sizes of the piles, to determine the number of winning first moves for the first player from the initial position (that is, moves after which the first player still has a winning strategy).
The first line of input contains the integer , the number of groups of piles. Each of the next lines describes a group with three integers , , . If we arrange all piles in the group in ascending order of sizes, is the size of the smallest pile, is the size of the largest pile, is the number of piles in the group, and the difference between the sizes of two adjacent piles is constant.
1 \leq M \leq 20000, 0 \leq a \leq b \leq 10^{18}, b-a is divisible by N-1.
Output a single integer — the number of first moves that allow a winning strategy.
Primer 1