How to apply Q-learning when rewards is only available at the last state?
Having only a non-zero reward at the very end is not uncommon. When rewards are sparse, it becomes a bit harder to learn compared to having lots of different rewards along the way, but for your problem, the goal state is always reached, so that should not be a problem. (The real problem with sparse rewards is that, if an agent can do a lot of exploration without every finding the goal, it essentially receives no feedback and will behave randomly, until it happens to stumble upon the very rare reward state.)
What concerns me more about your problem is that the final reward depends not just on the last state visited, but also on the chain of actions taken so far. That means that, to make this a proper MDP, you need to keep the chain of action in the state. So, your state would be something of the type $(s_k, [a_1, a_2, \ldots, a_{k-1}])$.
This kind of combinatorial problem is not what RL is really great at. RL is really good when the state and action together give a lot of information about the next state. Here it seems that, in your formulation, the next state is independent of the previous action.
Instead of seeing this as a RL problem, you might want to express this as sequences of actions with an associated reward, and look at it as a combinatorial optimization problem.