一道结论小博弈
感觉挺难想，但是 luogu 上是绿
题意
题目链接
现在有 堆石子和两个人
Alice、Bob，第 堆石子有 个。
Alice 与 Bob
轮流取石子，第一个人第一次可以任选一堆，取任意（显然不能取成负数）石子。后面每一次取石子的个数必须是前一次的正整数倍（仍然为人选一堆），谁不能取谁输。
问 Alice
开局有多少种方案使得自己胜利，选取不同的堆，或石子数量不同，都算不同的方案。
题解
啊，结论题
这题看起来就不好 SG 函数，所以优先考虑什么情况有解。
首先发现，若在第 个堆里拿了
个石子，那么相当于先令所有 ，然后令
这样我们就可以忽略，每一次拿取数量必须是前一次倍数的限制。
为方便表示，我们设
表示，恰有 个石子的堆的数量。
不·容易发现，若对于每一个数字 ，都有 ，那么后手必胜。若先手在一个有 个石子的堆里拿走 个，那么后手一定能再找到一个恰有 个石子的堆，然后拿走 个石子。这样后手永远可以继续操作。
对于剩下的情况，一定为先手必胜。先手可以找到一个最大的 ，使得 ，然后先手拿空任何一个有 个石子的堆，就可以转成上面的情况。
知道了如何判断局面，那么考虑 Alice 如何进行操作。
发现题目实际上在问，Alice
开局有多少种拿法，使得局面变为先手必败。
首先考虑枚举 ，表示 Alice
第一次拿几个石子，这样我们就知道了 。
现在我们的目标是：选取一个数 ，令 ，使得对于所有 ，有 ，方案数为
。
所以我们进行分类讨论：
初始不存在 使得 ，那么显然无解。因为这样会导致 。
初始恰存在一个 使得
若 ，显然满足；
若 ，则会导致 ，不满足。
初始恰存在两个数
满足
若 ，显然满足；
若 ，则不满足。
若至少存在三个 使得 ，显然无解。
如果存在 ，那么将答案加上初始的
即可。
时间复杂度 。
代码
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int pre[2000001];
int a[100001];
ll ans;
int n;
inline int get(int len,int id)
{
return pre[id*len+len-1]-pre[id*len-1];
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read(),pre[a[i]]++;
for(int i=1;i<=2000000;i++) pre[i]+=pre[i-1];
for(int i=1;i<=1000000;i++)
{
int wh1=0,wh2=0;bool flag=0;
for(int j=1;i*j<=1000000;j++) if(get(i,j)&1)
{
if(!wh1) wh1=j;
else if(!wh2) wh2=j;
else flag=1;
}
if(!flag)
{
if(wh2&&wh2==wh1+1) ans+=get(i,wh2);
if(!wh2&&wh1==1) ans+=get(i,wh1);
}
}
printf("%lld\n",ans);
return 0;
}
|
感谢观看！