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