信息学集训队作业zoj

1、ZOJ2700Andrew Stankevichs Contest #9Quadratic Equation解题报告题目大意对于关于t的0/1系数多项式a(t)、b(t)和c(t)，求方程a(t)x2(t)+b(t)x(t)+c(t)=0的一个解x(t)。0/1系数多项式是每项系数都为0或1的多项式，在加减乘时所有系数在mod 2下进行运算。a(t)、b(t)、c(t)的次数都不超过127。算法分析首先可以注意到其次多项式a(t)x2(t)、b(t)x(t)和c(t)必然有两个次数相等而大于另一个的次数，否则这三个多项式的和不可能是0。分别讨论三种情形可以得到x(t)次数的最大值。这样可以从可

2、能的最高次依次向下确定x(t)的每个系数。每次可以确定形如ax=b的方程，因而有时系数01均可，有时则无解，必须回溯。x(t)确定后需要再验证是否为方程的解。效率和优化由于过程中不能立即确定系数的情形出现不多，程序运行效果非常好。朴素的递归式dfs写法即可AC。此外，整个方程可以化为一个线性方程组，在不考虑重复和无意义方程(即0=0)时方程个数多于未知数个数。运用有关线性方程组的知识可能可以得到更多结论。总结和体会作这道题时有相当长时间的对回溯的畏惧。对于这种充满了0的方程组，一定的回溯或许是无法避免的。原题Quadratic EquationTime limit: 10 Seconds Me

3、mory limit: 32768K Special JudgeTotal Submit: 33 Accepted Submit: 11 Children in school learn how to solve quadratic equations - that is, equations of form ax2+bx+c=0, where a , b and c are some given real numbers, and x is the real number to find. In this problem you have to solve quadratic equatio

4、n for polynomials with coefficients from Z/2Z . Recall, that there are two numbers in Z/2Z : 0 and 1 , and all operations in this field are performed modulo 2 . Given polynomials a(t) , b(t) and c(t) , find such polynomial x(t) that a(t)x2(t)+b(t)x(t)+c(t)=0, where equality should be considered as p

5、olynomial equality. Remember, that two polynomials are equal if and only if their coefficients at corresponding powers of t are equal. InputThere are mutilple cases in the input file. Each case contains a(t) , b(t) and c(t) , specified as their power followed by their coefficients, starting from the

6、 leading one (the coefficient at the greatest power of t ). Zero polynomial has the degree of -1 for the purpose of this problem. Degrees of all polynomials do not exceed 127 . There is an empty line after each case. OutputIf there is at least one solution to the equation, output any one in the same

7、 format, that is used in input. Leading coefficient of the answer polynomial must not be zero. The degree of the polynomial must not exceed 512. In the other case print “no solution” on the first line of the output file. There should be an empty line after each case. Sample Input0 12 1 1 03 1 0 0 0 0 11 1 10 1-1-1-1Sample Output1 1 0no solution-1In the first example the equation has the form x(t)2+(t2+t)x(t)+t3=0, and x(t) = t is clearly a solution. In the second example the equation is x(t