题意简述
给定长度为 (n) 的序列 (a[]) , (a_i=1,2,3)
定义 (x_{i,j}) 为：
求 (x_{n,1}) 的值。
(n leq 10^6)
想法
首先，显然 (x_{i,j}=0,1,2)。(x_{i,j}) 的值只与差有关，所以可以把 (a[]) 中的所有值都减1，这样 (a_i=0,1,2)，多整齐。
然后好像不知道该怎么办了。于是考虑一种弱化情况，即 (a[]) 只有两种取值。
不失一般性地设 (a[i]) 的两个取值为 (0) 和 (t) ，则所有 (x_{i,j}) 的取值也只有 (0)、(t)
再次可以不失一般性地设这两个取值为 (0) 和 (1) 。
这时问题转化为，给定一个由 (0) 和 (1) 构成的数组 (a[]) ，求 (x_{n,1})
我们注意到，0与1的差为1，1与1 或 0与0的差为0。这恰是异或操作。
于是有 (x_{i,j}=x_{i-1,j} oplus x_{i-1,j-1})，(oplus) 表示异或
最终的 (x_{n,i}) 是由若干个 (a[i]) 异或得到的。
具体异或多少次呢？
为方便表示，规定符号 (XOR(m,i)=moplus moplus ...oplus m) ，表示 (i) 个 (m) 连着异或。
自己动手画一画可以发现规律（图中的^表示异或）。
每个 (x_{i,j}) 都对下面一行的左右两个数有贡献，由底向上递归发现就是个杨辉三角。
于是搞出对2取模的组合数随便算算就能知道 (x_{n,1}) 的奇偶性了。
注意组合数模2时需要记录阶乘中2的次数。
知道奇偶性后，就可判断出1了。
然后考虑怎么判断0和2。
此处有一个小性质：
如果原序列（(a[i]-1)）中有1，那么最终答案只能是0。
简单证明一下：如果原序列全是1，那么最终答案一定是0；如果不全是1，则一定有1与2相邻或1与0相邻的位置，这些相邻位置的差为1，也就是下一行一定有1。
以此递推下去，在出现某一行全是1之前，所有行中都是有1的。直到出现了全是1的行，之后的行中才不会有1，且之后的行中全是0。
那有没有可能最终答案为1呢？由于前面判断过答案为偶数了，所以只能是0。
判断完这种情况后，剩余情况即使原序列中只有 (0) 与 (2) 。可用上文判断 (0) 和 (1) 的方法判断最终答案。
妙题啊妙题！
总结
思想
考虑奇偶性。
二进制。
要有分类讨论的勇气！！
实现
组合数对小质数取模：记录次数。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000005;
int n;
char s[N];
int t[N];
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=n;i++) s[i]--;
int sum=0,c=0;
t[0]=t[1]=0;
for(int i=2;i<=n;i++)
if(i&1) t[i]=0;
else t[i]=t[i/2]+1;
for(int i=1;i<=n;i++){
if(i>1) c+=t[n-i+1]-t[i-1];
if(s[i]=='1' && c==0) sum^=1;
}
if(sum==1) { printf("1
"); return 0; }
for(int i=1;i<=n;i++)
if(s[i]=='1') { printf("0
"); return 0; }
sum=0; c=0;
for(int i=1;i<=n;i++){
if(i>1) c+=t[n-i+1]-t[i-1];
if(s[i]=='2' && c==0) sum^=1;
}
if(sum==1) printf("2
");
else printf("0
");
return 0;
}