mydcwfy 提供的题目。
很显然对于 $n>1$ 的情况答案一定不为 $2$，特判即可。其他情况我们先做一次操作。
接着我们手动模拟，大胆猜测：若序列中有 $1$，则答案一定不为 $2$。似乎也比较显然，因为只要 $1$ 与 $2$ 在操作过程中相遇，那么 $2$ 就会被消掉，而 $1$ 并不会。对于只有 $2$ 的情况，我们可以把整个序列 $\div 2$ 就和 $0-1$ 序列的情况一样了，最后答案 $\times 2$ 即可。
实际上我们只需要判断答案奇偶，操作也变成了模 $2$ 意义下的。比较重要的是：$f_{k,x}=f_{k-1,x}-f_{k-1,x-1}=f_{k-1,x}+f_{k-1,x-1} \mod 2$。这很像组合数，我们进一步可以得到：$f_{n,1}=\sum_{i=1}^{n} a_i \cdot \binom{n-1}{i-1} \mod 2$。使用 Lucas 定理或者 [n&m==m] 判断奇偶都可以。
Code
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
| #include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=1e6+10;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int a[N];
int C(int n,int m){return (n&m)==m;}
int main()
{
read(n);
for(int i=1;i<=n;i++)
scanf("%1d",&a[i]);
if(n==1)
{
printf("%lld\n",a[1]);
return 0;
}
int flag=0;
n--;
for(int i=1;i<=n;i++)
a[i]=abs(a[i]-a[i+1]),flag|=(a[i]==1);
if(!flag)
for(int i=1;i<=n;i++)
a[i]>>=1;
flag^=1;
int ans=0;
for(int i=1;i<=n;i++)
ans^=C(n-1,i-1)*(a[i]&1);
printf("%d\n",ans<<flag);
return 0;
}
|