Chlience

【题解】LOJ 2210 「HNOI2014」江南乐
Problem给定 $n$ 堆石子和每堆石子的数量 $s_i$,每次可以将某个数量不小于 $F$ 的石子堆尽量平均...
扫描右侧二维码阅读全文
12
2019/02

【题解】LOJ 2210 「HNOI2014」江南乐

Problem

给定 $n$ 堆石子和每堆石子的数量 $s_i$,每次可以将某个数量不小于 $F$ 的石子堆尽量平均的分为 $m$ 堆,其中 $m$ 可以是任意正整数

无法操作者败

多组询问

Thought

显然最终的局面肯定是每一堆都小于 $F$ 的
考虑将每个状态分解为多个子状态,也就是说对每一堆石子进行分析

设 $f[i]$ 为一堆 $i$ 个石子的 $SG$ 值,显然有

$$ f[i]=0 (i<F)\\ f[i]=mex_{j=2}^{i}\{f[\frac{i}{j}]\oplus f[\frac{i}{j}]\oplus \cdots\oplus f[\frac{i}{j}+1]\oplus f[\frac{i}{j}+1]\oplus\cdots\} $$

由于 $x\oplus x=0$,那么只需要算出 $f[\frac{i}{j}]$ 的个数和 $f[\frac{i}{j}+1]$ 的个数即可

显然的, $f[\frac{i}{j}]$ 共有 $j-(i\bmod j)$ 个, $f[\frac{i}{j}+1]$ 共有 $i \bmod j$ 个
并且,当 $\left \lfloor \frac{i}{j} \right \rfloor$ 不变时, $i\bmod j=i-j*\left \lfloor \frac{i}{j} \right \rfloor$ 仅和 $j​$ 的奇偶相关

那么,可以用分块枚举每个 $\left \lfloor \frac{i}{j} \right \rfloor$ 的不同取值,对于每个取值相同的一段 $j​$ ,根据奇偶关系计算贡献

当 $i​$ 为奇数时, $\left \lfloor \frac{i}{j} \right \rfloor​$ 为奇数时, $j​$ 为奇数时: $f[\frac{i}{j}]​$
当 $i​$ 为奇数时, $\left \lfloor \frac{i}{j} \right \rfloor​$ 为奇数时, $j​$ 为偶数时: $f[\frac{i}{j}]\oplus f[\frac{i}{j}+1]​$
当 $i​$ 为奇数时, $\left \lfloor \frac{i}{j} \right \rfloor​$ 为偶数时, $j​$ 为奇数时: $f[\frac{i}{j}+1]​$
当 $i​$ 为奇数时, $\left \lfloor \frac{i}{j} \right \rfloor​$ 为偶数时, $j​$ 为偶数时: $f[\frac{i}{j}]\oplus f[\frac{i}{j}+1]​$
当 $i​$ 为偶数时, $\left \lfloor \frac{i}{j} \right \rfloor​$ 为奇数时, $j​$ 为奇数时:$f[\frac{i}{j}+1]​$
当 $i​$ 为偶数时, $\left \lfloor \frac{i}{j} \right \rfloor​$ 为奇数时, $j​$ 为偶数时: $0​$
当 $i​$ 为偶数时, $\left \lfloor \frac{i}{j} \right \rfloor​$ 为偶数时, $j​$ 为奇数时: $f[\frac{i}{j}]​$
当 $i​$ 为偶数时, $\left \lfloor \frac{i}{j} \right \rfloor​$ 为偶数时, $j​$ 为偶数时: $0​$

但是其实不用这么复杂,考虑 $i,\left \lfloor \frac{i}{j} \right \rfloor​$ 不变时,可能的贡献只有两种,分别在 $j​$ 为奇数和偶数的时候取到

那么对于 $\left \lfloor \frac{i}{j} \right \rfloor$ 相同的一段,假设最小的 $j=min_j$ ,只需要求出 $min_j,min_j+1$ 两个取值即可

小优化:先计算取值,再计算 $mex$ 有惊喜

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
int sg[N], s[N], F;
void find(int x) {
    if(sg[x] >= 0) return;
    sg[x] = 0;
    if(x >= F) {
        for(int i = 2; i <= x; i = x / (x / i) + 1)
            for(int j = i ; j <= min(i + 1, x); ++ j) {
                if((x % j) & 1)
                    find(x / j + 1);
                if((j - (x % j)) & 1)
                    find(x / j);
            }
        for(int i = 2; i <= x; i = x / (x / i) + 1)
            for(int j = i ; j <= min(i + 1, x); ++ j) {
                int ans = 0;
                if((x % j) & 1)
                    ans ^= sg[x / j + 1];
                if((j - (x % j)) & 1)
                    ans ^= sg[x / j];
                s[ans] = x;
            }
        while(s[sg[x]] == x) ++ sg[x];
    }
}
int main() {
    memset(sg, - 1, sizeof(sg));
    int t = read(); F = read();
    while(t --) {
        int ans = 0, n = read();
        for(int i = 1; i <= n; ++ i) {
            int pos = read();
            find(pos);
            ans ^= sg[pos];
        }
        printf(ans ? "1 " : "0 ");
    }
    return 0;
}
Last modification:February 12th, 2019 at 07:31 pm

Leave a Comment