早前看过，那里给出了一个gifted solution，我复写如下：
int i,j,k,A[9],K[][9]={
{1,1,1,1,1,2,1,2,0},
{2,1,2,1,2,1,3,0,3},
{1,1,1,2,1,1,0,2,1},
{2,1,3,1,2,0,2,1,3},
{2,1,2,1,3,1,2,1,2},
{3,1,2,0,2,1,3,1,2},
{1,2,0,1,1,2,1,1,1},
{3,0,3,1,2,1,2,1,2},
{0,2,1,2,1,1,1,1,1}};
int main(){
	for(i=0;i<9;i++){
		scanf("%d",&k);
		for(j=0;j<9;j++)A[j]+=K[i][j]*k;
	}
	for(i=0;i<9;i++)for(k=A[i]%4;k--;)printf("%d ",i+1);
}

不要问为什么，bro只是copy,这里是向大家提供一种思路。

我看了一下留言，有的说枚举搜索，有的说高斯消元，都很不错。
还有个哥们说了句矩阵，我这里推导一下：

从figure中能得到如下方阵
[1,1,0,1,1,0,0,0,0 ,
 1,1,1,0,0,0,0,0,0 ,
 0,1,1,0,1,1,0,0,0 ,
 1,0,0,1,0,0,1,0,0 ,
 0,1,0,1,1,1,0,1,0 ,
 0,0,1,0,0,1,0,0,1 ,
 0,0,0,1,1,0,1,1,0 ,
 0,0,0,0,0,0,1,1,1 ,
 0,0,0,0,1,1,0,1,1 ]=C

令最终状态[0 0 0 0 0 0 0 0 0]=O

设输入[3 3 0 2 2 2 2 1 2]=b

所求的即是 (a*C+b)mod 4=O 方程中的a。 (*is Matrix multiply)

而样例中的输出则为 [0 0 0 1 1 0 0 1 1]， 带入方程中是满足的(with matlab)。

方程作如下变形
a*C mod 4 + b mod 4 =O
a*C mod 4 = -(b mod 4)  
a*C mod 4 = (-b) mod 4  
a*C mod 4 = (4-b) mod 4   (cz:0<=b<4)

设[4...4]=f, a'为a*C=f的解, 设(4-b) mod 4=v, a为a*C=v的解

显然，a为原方程一个特解，原方程的通解为 a+k*a', k为任意实数, 其中a=v*I, a'=f*I
I为C的逆阵，这里用软件求出来为：
[ -1/5,  3/5, -1/5,  3/5, -1/5, -2/5, -1/5, -2/5,  4/5]
[  2/5, -1/5,  2/5, -1/5,  2/5, -1/5, -3/5,  4/5, -3/5]
[ -1/5,  3/5, -1/5, -2/5, -1/5,  3/5,  4/5, -2/5, -1/5]
[  2/5, -1/5, -3/5, -1/5,  2/5,  4/5,  2/5, -1/5, -3/5]
[  2/5, -1/5,  2/5, -1/5, -3/5, -1/5,  2/5, -1/5,  2/5]
[ -3/5, -1/5,  2/5,  4/5,  2/5, -1/5, -3/5, -1/5,  2/5]
[ -1/5, -2/5,  4/5,  3/5, -1/5, -2/5, -1/5,  3/5, -1/5]
[ -3/5,  4/5, -3/5, -1/5,  2/5, -1/5,  2/5, -1/5,  2/5]
[  4/5, -2/5, -1/5, -2/5, -1/5,  3/5, -1/5,  3/5, -1/5]

a'求出来为:[ 4/5, 8/5, 4/5, 8/5, 4/5, 8/5, 4/5, 8/5, 4/5]


综上，先求出特解a，我试过，有时候并不是整数，再用通过 a+k*a'寻找一组整数解。

• Re:USACO，chapter 1 (833) tzkq 2010-06-19 17:41:32