uh just read the problem yourself, explaining it here would take way too long
so it would be absolute cancer to try and actually calculate if each tuple
can get to a level where all cows have the same hunger level
not only that, calculating all the possible
tuples themselves...
hm
what if we thought of the problem in reverse?
so like we started at a level where all the cows
were equal, and then we added pairs of 1's to cows until we got a random n-tuple that also
satisfied the input's upper bounds?
actually that might work!
but here's the thing: we have to handle cases where the number of cows is
even differently from the cases where the number of cows is odd
why?
because if the # of cows is even, all levels can be gotten from if all the hunger levels were 0
however, if the # of cows is odd, no level can be achieved from each other
actually yk what just have an example
if there we 3 cows, we couldn't get, say, `2 2 2` from `0 0 0` or `1 1 1`
however, if there were 4 cows, we could get `2 2 2 2` from `0 0 0 0`
so if the # of cows is even, we only have to calculate for if we start from 0, but if it's odd, we have to calculate from 0 all the way to the min upper bound
now to get to actually solving it for a random level & upper bound
first let's just subtract the level from all upper bounds so we can just treat it as if we're starting from 0
next, let's define `num_ways[c][l]` as the number of ways to bring crap up from 0
given that:
after some pain with the first couple values of `c` because of edge cases, we can get this recursion:
``` num_ways[c][0] = sum of all of num_ways[c - 1] num_ways[c][l] = sum of everything EXCEPT THE LAST l ELEMENTS of num_ways[c - 1] ```but constantly calculating the sum of the previous things would take too long, so let's just use a prefix sum as well to make things faster
and yeah, we basically solved the thing!
code here:
```cpp #include <iostream> #include <vector> #include <algorithm> using std::cout; using std::endl; using std::vector; using std::pair; constexpr int MOD = 1e9 + 7; // given the upper bounds, how many ways can we start from all 0's? int num_ways(const vector<int>& levels) { // just handle the first two pesky cases vector<vector<int>> num_ways{vector<int>(levels[0] + 1, 1)}; if (levels.size() >= 2) { int min = std::min(levels[0], levels[1]); num_ways.push_back({1}); for (int i = 1; i <= levels[1]; i++) { num_ways[1].push_back(i <= min); } } vector<int> prefs{0}; for (int i : num_ways.back()) { prefs.push_back(prefs.back() + i); // no need for modding here } for (int c = 2; c < levels.size(); c++) { num_ways.push_back(vector<int>(levels[c] + 1)); for (int l = 0; l <= levels[c - 1]; l++) { num_ways[c][0] = (num_ways[c][0] + num_ways[c - 1][l]) % MOD; } for (int l = 1; l <= levels[c]; l++) { if (l <= levels[c - 1]) { num_ways[c][l] = prefs[levels[c - 1] - l + 1]; } } prefs = {0}; // calculate prefix sums for the next iteration for (int l = 0; l <= levels[c]; l++) { prefs.push_back((prefs.back() + num_ways[c][l]) % MOD); } } // sum everything up @ the end & return it int total = 0; for (int i : num_ways.back()) { total = (total + i) % MOD; } return total; } /** * 2022 jan gold * 3 * 9 11 7 should output 241 * 4 * 6 8 5 9 should output 137 */ int main() { int cow_num; std::cin >> cow_num; vector<int> levels(cow_num); int min_hunger = INT32_MAX; for (int& c : levels) { std::cin >> c; min_hunger = std::min(min_hunger, c); } int total = num_ways(levels); // special odd cases if (cow_num % 2 == 1) { // go through all possible starting levels for (int i = 1; i <= min_hunger; i++) { for (int& c : levels) { c--; } total = (total + num_ways(levels)) % MOD; } } cout << total << endl; } ```