P9387 [THUPC 2023 决赛] 巧克力

, , ,

[THUPC 2023 决赛] 巧克力

Description

https://www.luogu.com.cn/problem/P9387

Solution

首先推一下必胜情况的充要条件。

本图是有向无环图，公平的两人游戏，考虑用 sg 函数。

令当前操作的巧克力长度为 $x$，实际上 $SG(x)=x$。

  • 如果 $x\not = 1$ ，显然可以先分为 $(0,x-1,1),…,(0,1,x-1)$，这样取 $\text{mex}$ 之后 sg 值已经为 $x$，所以有 $SG(x)\ge x$。
  • 如果分为 $(a,b,c),a+b+c=x,b>0$ 。原问题拆成两个独立的的子博弈 $a$ 和 $c$，又有 $a\bigoplus c\le a+c$，所以这里不会对 $SG$ 值有影响。

首先要全局的 $SG$ 异或和不为 $0$，保证先手不可能必败。令全局初始的异或和为 $N$。

再用令要把 $x$ 拆分为 $(a,b,c),a+b+c=x,b>0$，若操作完以后先手必败（这时候是后手先手）应该有：
$$
a\bigoplus c\bigoplus x\bigoplus N=0
$$
即现在的 $SG$ 的异或和为 $0$。

移个项为：
$$
a\bigoplus c\bigoplus(a+b+c)=N
$$
我们要求的是 $a+b+c\le n$ 或者 $a+b+c=m$ 的方案数，令 $\le n$ 的方案数为 $F(n)$，那么答案为 $F(n)+F(m)-F(m-1)$。

考虑数位 dp。一种的做法选择是从低位到高位 dp。记录当前在第 $i$ 位，低位到第 $i$ 进了 $j$ 位， $b$ 是否等于 $0$，$a+b+c$ 的后 $i$ 位是否大于 $N$ 的后 $i$ 位的方案数。

另一种大概是从高到低位 dp。记录当前在第 $i$ 位，向低位借了 $j$ ，$b$ 是否为 $0$，是否大于 $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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#define int long long
int f[65][4][2][2];
int stat[65],p[65];
int cnt;
void add(int &x,int y) {x=(x+y)%mod;}
int get(int n) {
	if (n==0) return 0;
	memset(f,0,sizeof(f));	
	memset(p,0,sizeof(p));
	int tot=0;
	while (n) p[++tot]=n%2,n/=2;
	f[0][0][1][0]=1;
	int i,j,k,l,a,b,c;
	for (i=0;i<=60;i++) {
		for (j=0;j<=3;j++) {
			for (k=0;k<=1;k++) {
				for (l=0;l<=1;l++) {
					for (a=0;a<=1;a++)
						for (b=0;b<=1;b++)
							for (c=0;c<=1;c++) {
								int s=((a+b+c+j))%2;
								if ((s^a^c)==stat[i+1]) {
									int pus=0;
									if (s>p[i+1]||(l&&s==p[i+1])) pus=1;
									add(f[i+1][(j+a+b+c)/2][k&(b==0)][pus],f[i][j][k][l]);
								}
							}
				}
			}
		}
	}
	return f[60][0][0][0];
}
void solve(void) {
	int i,n,m,s=0;
	read(n);read(m);
	memset(stat,0,sizeof(stat));
	s=m;
	if (n%4>=1) s^=n;
	if (n%4>=2) s^=(n-1);
	if (n%4>=3) s^=(n-2);
	if (s==0) return puts("0"),void();
	cnt=0;
	while (s) stat[++cnt]=s%2,s/=2;
	int tmp1,tmp2;
	printf("%lld\n",(get(n)+get(m)-get(m-1)+mod)%mod);
}
signed main(void){
	int T;
	read(T);while (T--) solve();
	return 0;
}

没卡常之前不太能过。卡常就跟另外一篇题解一样循环展开之类的，效果很明显。