# [洛谷 2148][SDOI 2009] E&D【SG定理】

• 2018-03-01
• 0
• 0

```2
4
1 2 3 1
6
1 1 1 1 1 1```

```YES
NO```

## Solution:

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int upr = 20;

int SG[52][52], S[2502], tops;

inline int mex(int *S, int tops){
int *tmp = new int[2502];
for(register int i = 1; i <= tops; i++) tmp[i] = S[i];
sort(tmp + 1, tmp + tops + 1);
if(tmp[1]) return 0;
else{
for(register int i = 1; i < tops; i++) if(tmp[i + 1] > tmp[i] + 1) return tmp[i] + 1;
return tmp[tops] + 1;
}
}

inline void calc_SG(){
for(register int sum = 2; sum <= (upr << 1); sum++){
int mn = min(upr, sum - 1);
for(register int i = 1; i <= mn; i++){
tops = 0; int j = sum - i;
for(register int k = 1; k < i; k++) S[++tops] = SG[k][i - k];
for(register int k = 1; k < j; k++) S[++tops] = SG[k][j - k];
SG[i][j] = (i == 1 && j == 1) ? 0 : mex(S, tops);
}
}
}

inline void display_SG(){
printf("  SG  y ");
for(register int j = 1; j <= upr; j++) printf("%4d", j);
puts(""), printf("   x  ##"); for(register int j = 1; j <= upr; j++) printf("####");
puts(""), printf("      ##"); for(register int j = 1; j <= upr; j++) printf("####");
puts("");
for(register int i = 1; i <= upr; i++){
printf("%4d  ##", i);
for(register int j = 1; j <= upr; j++) printf("%4d", SG[i][j]);
puts("");
}
}

int main(){
calc_SG(), display_SG();
return 0;
}
```

```  SG  y    1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
x  ##################################################################################
##################################################################################
1  ##   0   1   0   2   0   1   0   3   0   1   0   2   0   1   0   4   0   1   0   2
2  ##   1   1   2   2   1   1   3   3   1   1   2   2   1   1   4   4   1   1   2   2
3  ##   0   2   0   2   0   3   0   3   0   2   0   2   0   4   0   4   0   2   0   2
4  ##   2   2   2   2   3   3   3   3   2   2   2   2   4   4   4   4   2   2   2   2
5  ##   0   1   0   3   0   1   0   3   0   1   0   4   0   1   0   4   0   1   0   3
6  ##   1   1   3   3   1   1   3   3   1   1   4   4   1   1   4   4   1   1   3   3
7  ##   0   3   0   3   0   3   0   3   0   4   0   4   0   4   0   4   0   3   0   3
8  ##   3   3   3   3   3   3   3   3   4   4   4   4   4   4   4   4   3   3   3   3
9  ##   0   1   0   2   0   1   0   4   0   1   0   2   0   1   0   4   0   1   0   2
10  ##   1   1   2   2   1   1   4   4   1   1   2   2   1   1   4   4   1   1   2   2
11  ##   0   2   0   2   0   4   0   4   0   2   0   2   0   4   0   4   0   2   0   2
12  ##   2   2   2   2   4   4   4   4   2   2   2   2   4   4   4   4   2   2   2   2
13  ##   0   1   0   4   0   1   0   4   0   1   0   4   0   1   0   4   0   1   0   5
14  ##   1   1   4   4   1   1   4   4   1   1   4   4   1   1   4   4   1   1   5   5
15  ##   0   4   0   4   0   4   0   4   0   4   0   4   0   4   0   4   0   5   0   5
16  ##   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   5   5   5   5
17  ##   0   1   0   2   0   1   0   3   0   1   0   2   0   1   0   5   0   1   0   2
18  ##   1   1   2   2   1   1   3   3   1   1   2   2   1   1   5   5   1   1   2   2
19  ##   0   2   0   2   0   3   0   3   0   2   0   2   0   5   0   5   0   2   0   2
20  ##   2   2   2   2   3   3   3   3   2   2   2   2   5   5   5   5   2   2   2   2
```

## Code: O(TNlogS), 其中S=max{Si} [1996K, 40MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int T, N, x, y;

inline int SG(int x, int y){
int res = 0;
while(true){
if(x & 1 && y & 1) return res;
else if(x & 1) x++;
else if(y & 1) y++;
else x >>= 1, y >>= 1, res++;
}
}

int main(){
getint(T);
while(T--){
getint(N); int nimsum = 0;
for(register int i = 1; i <= N; i += 2){
getint(x), getint(y);
nimsum ^= SG(x, y);
}
puts(nimsum ? "YES" : "NO");
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai