PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Let x _ 0, x _ 1, …, x _ {d-1} be the seed values we are trying to discover. It is easy to see by induction that every value x _ i is a linear combination of these seeds. Furthermore, we can use the usual fast matrix multiplication trick to discover the coefficients in this linear combination (I’ll explain this below if you haven’t seen it). So, for each of the x _ i given in the input we have a linear equation with unknowns being the seed values. Once we determine all of these equations, it is a simple matter of solving this linear system with Gaussian elimination to determine if there are none, one, or many solutions for the seed values.
The matrix multiplication trick I’m alluding to is the following. For i >= 0, let z _ i denote the column vector (x _ {i+d-1}, x _ {i+d-2}, …, x _ {i+1}, x _ i)^T. The main idea is that there is a matrix A such that A z _ i = z _ {i+1} for every i >= 0. The first row of A consists of the a _ {d-1}, …, a _ 0 values given in the input and of the remaining rows, the j’th such row has all zeros except for a single 1 in column j-1 (try this on a few simple recurrences like the Fibonacci series). Then multiplying z _ i by A “shifts” the entries down and the top entry becomes x _ {i+d} by the recurrence. By induction on k >= 0, we have that A^k z _ 0 = z _ k where z _ 0 is the column vector of the seed values we are trying to discover. The neat thing is that we can compute A^k in O(log k) matrix multiplications by using fast exponentiation. Just remember to keep all intermediate results reduced modulo 2. The coefficients of the linear combination of the seeds that yield x _ i are then found on the bottom row of the matrix A^i.
This easily generalizes to the case when we are trying to discover the seeds when the recurrence is taken modulo p for some arbitrary prime p. However, it would involve implementing modular inversion and I thought there was enough to do for this problem in short contest already 
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.