是SDOI2016R2D1T1的加强版? 感觉比sdoi那个题有意思许多。

适当打表有利身心健康?

适当猜结论有利身心健康?

传送门

题目大意

每次选择一个白子\(x\), 选择一个整数\(k \leqslant \lfloor n/x \rfloor\), 翻转\(x, 2x, ... , kx\).

不能操作者输。

解题报告

首先初始棋盘上的每个白子是独立的, \(f[x]\) 表示\(x\)位置的白子的\(sg\)值。

很容易发现

\[f[x] = \text{mex} \left \lbrace f[x] \text{^} f[2x] \text{^} ... \text{^} f[kx] \right \rbrace , k \in [1,\lfloor \frac{n}{x} \rfloor]\].

如果直接用这个式子转移, 复杂度是\(O(\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor)\) .

可以发现, 一个位置的\(sg\)值可以由\(\lfloor \frac{n}{x} \rfloor\) 确定, 因为转移是完全一样的。

所示有用的状态就是\(O(\sqrt{n})\)的。

时间复杂度是\(O(n)\) ?

可以过了。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
int c[2][100000],k,w,n,B;
inline void nxt(int &i, int n) { i=(i==n?i+1:n/(n/(i+1)));}
inline void inital() {
static bool vs[100000]; static int tot,a[100000];
for (int i=1;i<=n;nxt(i,n)) {
int no=0; tot=0;
for (int j=2;j<=i;nxt(j,i)) {
int x=i/j,t=x>=B?c[1][n/x]:c[0][x];
a[++tot]=no^t, vs[a[tot]]=1;
if ((i/x-i/(x+1))&1) no^=t;
}
no=1; while (vs[no]) ++no;
if (i>=B) c[1][n/i]=no; else c[0][i]=no;
while (tot) vs[a[tot--]]=0;
}
}
int main() {
scanf("%d",&n); B=sqrt(n);
inital(); scanf("%d",&k); int x;
while (k--) { scanf("%d",&w); int as=0;
while (w--) scanf("%d",&x), x=n/x,as^=(x>=B)? c[1][n/x]:c[0][x];
puts((as?"Yes":"No"));
}
return 0;
}

留言