I'm trying to find an efficient algorithm to calculate the amount of permutations for this problem. I've only slightly simplified the problem to be easier to read. But the original problem, is Problem K from here: https://prog4fun.csse.canterbury.ac.nz/pluginfile.php/26/question/questiontext/11874/1/30809/problemset.pdf
In this RPG, you have a team of 4 players, and you can fight $N$ different bosses. Each boss $i$ has a payout $b_i$ (an integer), which represents the amount of gold you receive for defeating that boss.
Your task is to fight a minimum of $L$ rounds and a maximum of $U$ rounds. You can choose to fight the same boss multiple times, and the order in which you fight the bosses matters (i.e., permutations are considered).
The goal is to determine the number of different valid permutations of boss fights such that the total amount of gold obtained is divisible by 4 (so that each teammate can receive an equal share).
Brute-forcing is too slow, as the lower bound and upper bound for amount of boss fights can be $10^9$. So I assume this has something to do with dynamic programming.
How can I approach this problem? Any guidance or methods to count these permutations would be greatly appreciated.
What is the number of valid permutations of boss fights under these conditions?
Constraints:
- $N$ is the number of bosses.
- $L$ is the minimum number of rounds.
- $U$ is the maximum number of rounds.
- $b_i$ is the payout for boss $i$, where $b_i \in \mathbb{Z}$.
- The sum of gold from any valid sequence of boss fights must be divisible by 4.
Any help with how to structure the solution or the relevant combinatorial methods would be appreciated!
I've only come up with this equation so far: (where $a_i$ is how many times you defeated boss $i$)
$$a_1 \cdot b_1 + a_2 \cdot b_2 + \dots + a_N \cdot b_N \equiv 0 \pmod{4}$$
And I've thought about using stars and bars on $ L \leq a_1 + a_2 + \dots + a_N \leq U $
But I'm not sure where to go from there.
