信息学集训队作业侯启明

1、IOI2003中国国家集训队难题讨论活动0058 研究报告清华附中 侯启明【题目大意】【解决情况】证明了一般模线性方程组012解的存在性判定是NP-Hard的。文中算法的复杂度上限是O(3n)，下限是O(n3)，但实际运行效果非常好。【算法梗概】高斯消元法+搜索【讨论收获与感谢】和张家琳和陶默雷两位同学关于高斯消元和搜索的讨论。【正文】（由于黑体有表示向量的含义，所以本文中用红色标出重点）不妨设A*B=one，设Ai=ai，Bi= xi+1。得方程组：a0 x1+an-1x2+.+a1xnb1(mod Q)a1x1+a0 x2+.+a2xnb2(mod Q).an-1x1+an-2x2+.+a

2、0 xnbn(mod Q)现在，问题转化成了判定这个方程组是否有012解（就是xi0，1，2）的解。如果将条件稍稍减弱一点，觉得到了上面所说的一般模线性方程组012解的存在性判定问题：判定是否存在xi0，1，2使得：a11x1+a12x2+.+a1nxnb1(mod Q)a21x1+a22x2+.+a2nxnb2(mod Q).an1x1+an2x2+.+annxnbn(mod Q)我也曾经从这方面入手想过，但一直没有想出什么结果，最后发现：这个问题是NP-Hard的。证明：对任意的01背包问题“判定是否存在yi0，1使得wiyi=M”： 令Q=2p（p为充分大的质数），a11=1，a1i=5

3、wi-1（i2,n+1），b1=10M，bi=0（i2,n+1），aij=pij，（i2,n+1，j1,n+1）。下证原问题有解是模线性方程组：a11x1+a12x2+.+a1,n+1xn+1b1(mod Q)a21x1+a22x2+.+a2,n+1xn+1b2(mod Q).an+1,1x1+an+1,2x2+.+an+1,n+1xn+1bn+1(mod Q) 有012解的充要条件。n 充分性：n i =1 存在yi0，1使得wiyi=M i =1n 令x1=0，xi=2yi-1（i2,n+1）n i =1a1,i+1*xib1 i =1pxibi(mod Q) （i2,n+1） xi为原方

4、程一组012解，充分性得证 必要性： 原方程组有012解，5|b1-a12x2+.+a1,n+1xn+1=x1pxi0(mod Q) （i2,n+1） x1=0，xi0,2 （i2,n+1）n 令yi=xi+1/2n i =1 wiyi=M，yi0，1，原问题有解，必要性得证 i =1 证毕因此，通过和张家琳和陶默雷两位同学的讨论，我决定写一个高斯消元+搜索的程序。在写这个程序的过程中，我发现简单搜索的效率很不理想，想到题目中的方程组有很强的性质，于是我做了一些分析：为了分析简便，把本题所涉及到的方程组写成这种形式：在模Q加法的意义下定义群NQ=0,1,.,Q-1。定义NQ上的乘法运算为模Q乘

5、法。以下如不特别说明，所有的字母均表示群NQ的元素，加法和乘法均表示群NQ中的运算。 A1Xb1(mod Q)A2Xb2(mod Q).AnXbn(mod Q)n i =1其中A1=(a0,an-1,an-2,.,a1)，A2=(a1,a0,an-1,.,a1)，An=(an-1,an-2,.,a0)；b1=1；b2,b3,bn=0。定义(p1,p2,.,pn)(q1,q2,.,qn)= piqi（因为向量空间NQn不一定是一个线性空间，即使它是，这个运算也不完全符合内积的性质，所以不能成为内积）。n i =1可以得到一些结论：结论1：如果方程组有解，且iAi=0，那么i=0。nn证明：原方程

6、组有解nn i =1 i =1n i(AiX)= ibi i =1 i =1n i =1 (iAi)X=1 i =1 1=0n 令0=n，i=i-1。n i =1 iAi=0 i =1 n=1=0 同理，对任意的i，i=0结论2：如果方程组有解，且iAi=(b1,b2,.,bn)，k|Q，k|bi，那么k|i。证明：设Q=pk。原方程组有解，piAi=0pi=0k|i但是该结论目前只能用来判定无解，不能用来将k约去（因为方程kax=kb(mod kc)与ax=b(mod c)等价，但与ax=b(mod kc)并不等价，所以约去k会改变该方程模的值而使得后面的高斯消元无法进行下去）。加入这两条结

7、论后的程序可以直接判定相当多的无解情况，但是在很多数据面前却败下了阵来，比如我的自拟数据的第6个点。经过分析发现，这类数据在高斯消元的过程中会产生大量的增根（而且这些增根基本都是0或2），因而使得搜索量呈指数膨胀；但是如果调整一下消元的顺序，这类方程经常变得简单到能用手算解出来。因此，我加入了“启发式消元”：如果能不产生增根地消掉xi，就不产生增根地消掉xi。加入这个优化后，对绝大多数随机数据都能很快出解（对n=20，q=4或6检测了10000个随机数据，n=4时耗时24s，n=6时耗时28.5s）。而且该程序在1000多个随机小数据上通过了盲目搜索的验证，正确性应该可以保证。在对官方数据进行测试时发现：按照文中猜想写的程序得到的结果和林希德同学所描述的一样：第一个点有解，其它的点都是无解，与标准输出有很大差异。改用解方程+搜索，结果依旧。最后用完全的盲目搜索验证了标准输出为有解的最小的两个点，发现标准输出的确有误，因此，只好靠自制数据来测试程序了。【进一步研究的方向】启发式消元的效率分析，自制数据的互相验证。【参考文献】代数与几何自制数据说明：1巨大的“平凡”数据。24从10000个Q相同的随机数据中挑出来的“佼佼者”（有解的）。5消元顺序对搜索效率影响