How to understand SG function and its properties

This article focuses on "how to understand SG functions and properties", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to understand SG functions and properties".

{

Properties of Sprague-Grundy function

All endpoints have an SG value of 0 (because its successor set is empty)

A vertex whose SG is 0, and all its subsequent points satisfy that SG is not 0

For a vertex whose SG is not 0, there must be a successor satisfying that SG is 0

Meet the nature of combinatorial games

All SG 0 points correspond to P points, and SG > 0 vertices correspond to N points.

}

Hdu1847 Good Luck in CET-4 Everybody!

Meaning of the title:

A total of n cards, both sides take turns to draw cards, the number of cards each person can only be the power of 2. ), after the card is drawn, the result also comes out: the winner is the one who finishes the card. Give n and ask whether the first hand wins or the second hand wins?

PS: of course, this question can be directly introduced to n% 3 percent 0 must be defeated, otherwise it will be won. / / Bash Game

Here is another approach

SG value: the SG value of a point is the smallest integer that is not equal to the SG of its successor point and is greater than or equal to zero. / / same as mex () function

To put it simply, it is the distance from the current state to the nearest point of failure.

SG (x) = mex (S)

S is the set of SG function values of the successor state of x

Mex (S) denotes the smallest non-negative integer not in S

Let's enumerate the SG values with the number of cards 0-10:

Num: 0 1 2 3 4 5 6 7 8 9 10

SG value: 0 1 20 0 1 2 0 1 2 0 1

# include#include#includeusing namespace std;const int maxn = 1000 + 10 int arr [11], sg [maxn]; void pre () {/ / calculate all the cards that may be taken at once for less than 1000! Arr [0] = 1; for (int iTunes 1; I