Solution 1: Set operations

In fact, the problem can be tackled quite efficiently using set operations.

def subst(f,x,c):
   i=x.index()
   c=Polynomial(c)#if c was int is now converted mod 2, so comparison to int(0) makes sense
   s=f.set()
   if c==0:
       #terms with x evaluate to zero
       return Polynomial(s.subset0(i))
   else:
       #c==1
       return Polynomial(s.subset1(i))+Polynomial(s.subset0(i))