计算平分石子问题的成功模式

mathe

http://poj.org/problem?id=1014中的问题，大概意思是给定一些价值分别为1,2,3,4,5,6的石子，判断能否将它们平分成两份。
我们可以先做一些记号$E_k = {n| n = 0 (mod 2), n>=k}, O_k = {n | n=1(mod 2), n>=k}, A_k = {n | n>=k, n \in Z}$
然后先考虑一些规模更小的问题，
i)比如所有石子价值都是1的情况，显然，只有石子数目为偶数时可以平分，于是我们可以用
$E_0$
表示可以成功平分的模式。

ii) 而对于石子价值分别为1，2的情况。显然价值为1的石子数目必须是偶数才有可能平分。而价值为1的石子数目至少两个时总能够平分（先尽量平分价值为2的石子，然后利用余下价值为1的石子来调整）。
而价值为1的石子数目为0时，价值为2的石子数目为偶数时才可以平分，所以我们可以用两个模式
$E_2A_0$
$0E_0$
两表示，第一个表示价值为1的石子数目不小于2而且是偶数，价值为2的石子数目是任意数，第二个模式表示价值为1的石子数目为0，价值为2的石子数目为偶数。

iii)而对于石子价值分别有1，2，3的情况，同样，价值为1或3的石子数目之和必须是偶数才可能平分。此时，如果价值为1的石子数目不小于2，容易分析出必然可以平分。
由此得出两个模式$E_2A_0E_0, O_3A_0O_1$。
另外如果价值为1的石子数目为1，那么价值为3的石子数目为奇数，如果这时存在价值为2的石子，必然可以平分，得出模式$1A_1O_1$
   而如果价值为1的石子数目为1，那么价值为3的石子数目为奇数，而不存在价值为2的石子，那么必然不可以平分。
如果价值为1的石子不存在，那么价值为3的石子数目为偶数，如果价值为3的石子数目不小于2，价值为2的石子数目不小于3而且为奇数，那么也可以，得出模式$0O_3E_2$
                                                如果价值为2和3的石子数目都是偶数，必然能成功，得出模式$0E_0E_0$
得出所有模式为
$E_2A_0E_0$
$O_3A_0O_1$
$1A_1O_1$
$0O_3E_2$
$0E_0E_0$

现在问题是对于这样一般性的问题，给定k中石子价值$v_1,v_2,...,v_k$（其中k不是很大，每个$v_i$也不是太大，比如都不超过10）
如何利用计算机计算出所有成功模式

mathe

对于k个数值的问题，可以用一个k维向量$(x_1,x_2,...,x_k)$表示，其中每个分量都是非负整数。
我们可以用这些向量作为顶点构造一个图，其中对于每个点$(x_1,x_2,...,x_k)$,分别向点$(x_1+2,x_2,...,x_k),(x_1,x_2+2,...,x_k),(x_1,x_2,...,x_k+2)$做有向边。
也就是每个点会引出k条边（每条边两个顶点有k-1个分量相等，一个分量差2），而每个点最多有k条边进入。
这样可以构成一个有$2^k$个连通分支的有向无环图。
而我们容易看出，如果某个点的结果是“成功”的，那么它的所有后继节点也必然是“成功”的。所以只要能够找到那些所有父节点都"不成功“（或没有父节点）的”成功“节点就可以了

mathe

上面图中有$2^k$个连通分支。如果每个结果“成功”的点染成红色，“不成功”的店染成白色。显然有些连通分支全红，比如所有坐标都是偶数的连通分支。而有些连通分支全白，比如一个奇数价值分量坐标为奇数，其余分量坐标都是偶数的连通分支。
由于如果所有价值都是偶数，我们总可以将所有价值都除以2，得到至少存在奇数价值的等价问题。所以我们不妨假设总有部分价值是奇数。而这时，我们是可以证明，如果价值是奇数的分量坐标之和是偶数的点所在连通分支必然有红色点；反之，价值是奇数的坐标分量之和是奇数点所在连通分支必然全是黑色点（也就是总价值是奇数情况）

另外，如果一个红色点所有前驱点都是白色点，那么我们称这个红色点是一个关键点。那么本题中任务就是要求所有关键点。

对于一个本题中的图（或一个连通分支），如果我们固定某些坐标分量的取值，可以得到这个图一个子图，称为其一个投影。实际上，这些投影相当于一个降维后图。
比如我们取图中第一个分量取常数10的图,即点集${(10,x_2,x_3,...,x_k)}$生成的子图，就是一个k-1维投影。
于是我们容易看出，如果一个点在一个图中是关键点，那么在所有包含它的投影中也是关键点。

mathe

现在假设我们已经得到一个关键点$(a_1,a_2,...,a_k)$
于是我们知道对于它所在连通分支上任意其它的关键点$(b_1,b_2,...,b_k)$,那么条件$b_1<a_1,b_2<a_2,...,b_k<a_k$中至少有一个成立
所以我们知道所有其它关键点必然在落在投影$x_1=0,x_1=1,...,x_1=a_1-1,x_2=0,x_2=1,...,x_2=a_2-1,...,x_k=0,x_k=1,...,x_k=a_k-1$中的某一个上（可以同时存在多个上），而且它们也必然也是所对应的投影的关键点。
于是得出任意一个关键点后，余下的关键点必然都是有限个k-1维投影的关键点。同样对于这些k-1为投影，如果存在关键点，任意找出它们一个关键点，又可以继续降维得到更多更低维度的投影。由此我们可以知道关键点数目必然是有限的。

mathe

所以现在一般情况下就是给定一个连通投影，如何判断其是否包含关键点，如果存在那么如何找到一个关键点。
不妨设这个投影为$x_1=a_1,x_2=a_2,...,x_h=a_h$,而$d=gcd(v_{h+1},v_{h+2},...,v_k)$.
我们首先需要计算集合${t_1*v_1+t_2*v_2+...+t_h*v_h+s_{h+1}*v_{h+1}+...+s_k*v_k| -a_i<=v_i<=a_i, 2|v_i-a_i}$是否包含$2d$的倍数,其中$s_i$在坐标$x_i$为偶数时时0，在坐标$x_i$是奇数为1.
如果不包含$2d$的倍数，那么投影上不存在关键点，不然投影中必然存在关键点。（可以用动态规划模$d$计算做上面判断）
而构造关键点的关键是先找到一个红点，然后判断其前驱结点，如果都不是红点就找到了关键点，不然用前驱替换当前点，继续判断其前驱。
而为了找到一个红点，利用上面集合中$d$的倍数对应的一个划分得出前$h$部分坐标石子价值差为$d$的倍数然后让后面部分用中国剩余定理构造解答

mathe

利用上面方法手工计算四种石子中部分连通分支得到部分关键点0000,2100,0122,0320,0201,4001,2021