State pattern implementation hardship

I use state pattern in my application because my state-entities has API the behaviour of which changes due to current state.

In my case that state-dependent API consists only from one method - changeState. This method change state and also execute some state-dependent logic.

But there is the circumstance that made me to ask this question: State dependent logic depends not only on current state, but also it depends on newState (see code below). So I have to use instanceof.

Question: what is the true way to get rid of instanceof?

public interface IStateEntity {
  void changeState(IState newState);
}

public interface IState {
  void doStateDependentLogic(IState newState);
}

public class StateEntityImpl {

  private IState state;

  @Override
  public void changeState(IState newState) {
    state.doStateDependentLogic(newState);
    state = newState;  
  }
}

public class StateImplA { //each state implementation is a singleton

  @Override
  public void doStateDependentLogic(IState newState) {
      // HARDSHIP #1: state dependent logic depends not only on current state, but also it depends on newState. So I have to use `instanceof`
     if (newState instanceof StateImplA) {
       //do one logic
     } else if (newState instanceof StateImplB) {
       //do another logic
     }
  }
}

EDIT (why not enum):

If enum replace a getClass().getSimpleName(): because it's functional programming paradigm. When I make my architecture in such way that it relies on className, that the first sign that something goes wrong.It seems for me that change instanceof to enum doersn't mean to change architecture, but only to change one bad for worse.

If make each IState implementation as enum: each IState implementation is Hibernate entity.

The accepted way in Java of creating a singleton is with an enum. This provides thread safe initialisation as well as JVM guaranteed singleton status. There are many ways for creating a second instance of a class that is not an enum.

The additional benefit of using an enum is that you are allowed to case switch on the enum in your logic:

public enum State {

    STATE_A {
        @Override
        public void doStateDependentLogic(final State newState) {
            switch (newState) {
                case STATE_B:
                    //do stuff
                //case SOME_OTHER_STATE
            }
        }
    },
    STATE_B {
        @Override
        public void doStateDependentLogic(final State newState) {
        }
    };

    public abstract void doStateDependentLogic(State newState);
}

I don't know where you got the idea that an enum is a functional programming paradigm. This is not the case. enum in Java is designed to do exactly what you want.