Technically yes, but I think that the bit "no solutions" necessarily means a negation. It rather means that they believe there´s zero solution, not one solution. That is, they positively believe that.
If it is to negate the sentence, one would have to "negate the belief", hence the use of "don´t/do not" close to the verb believe.
In passing, I must say that DO NOT suggests a more formal sentence, whereas with DON´T it would be a less formal one (i.e. A more colloquial way).