题解 p2148 [sdoi2009]e&d

using namespace std;
int SG[1010][1010], n;
inline int (vector <int> v) {
    sort(v.begin(), v.end());
    int cnt = unique(v.begin(), v.end()) - v.begin();
    for(int i = 0; i < cnt; i++) if(v[i] != i) return i;
    return cnt;
}
int main() {
    scanf("%d", &n);
    SG[1][1] = 0;
    for(int sum = 3; sum <= n * 2; sum++) {
        for(int i = max(1, sum - n); i <= sum && i <= n; i++) {
            int j = sum - i;
            vector <int> v;
            for(int k = 1; k < i; k++) v.push_back(SG[k][i - k]);
            for(int k = 1; k < j; k++) v.push_back(SG[k][j - k]);
            SG[i][j] = mex(v);
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) printf("%d%c", SG[i][j], " n"[j == n]);
    return 0;
}

using namespace std;
inline int work(unsigned int x) {
    x = ~x;
    x = x & (-x);
    int ans = 0;
    while(x >>= 1) ans++;
    return ans;
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, ans = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i += 2) {
            int a, b;
            scanf("%d%d", &a, &b);
            ans ^= work((a - 1) | (b - 1));
        }
        if(ans) puts("YES");
        else puts("NO");
    }
}