Судя по ограничениям, надо что-то квадратичное написать а не 3D.
Во-первых, заметим, что если все числа a[i] заменить на k+1-a[i], то последовательность останется правильной. Но первое число поменяет свой тип, если оно было локальным максимумом, но станет минимумом и наоборот. В итоге, нам можно считать только последовательности где a[0] < a[1] > a[2] < a[3] ... и в конце умножить на 2. Это немного упрощает решение. ведь от позиции числа уже фиксируется, какие там должны быть знаки.
Идея в том, мы будем считать такие зубчатые последовательности длины n и заканчивающихся на число a.
Почему нам важно последнее число? Потому что именно оно определяет, что мы дальше можем приписать и что может идти перед ним.
Обозначим это как DP[n, a]. Для вычисления надо перебрать все возможные значения предыдущего числа, они должны быть < или > a в зависимости от четности n.
DP[n,a] = DP[n-1,1]+..DP[n-1,a-1], если n - четно
DP[n,a] = DP[n-1,a+1]+..DP[n-1,k], если n - нечетно
Но тут неудобно, что у нас разные суммы для четных и нечетных n. Помним, что можно все знаки обратить просто заменив все числа на k+1-a[i]. Тогда можно всегда считать что DP[n,a] - это такие последовательности, где последнее число всегда минимум. А значит, предыдущее j > a - должно быть максимуом, что то же самое что k+1-j было минимумом.
DP[n,a] = sum_j=a+1..k DP[n-1,k+1-j] = DP[n-1,k-a] + ... + DP[n-1,1]
Можно было бы считать что последнее число -максимум и формула была бы примерно такая же, только сумма верхней части массива, а не нижней как тут.
Вроде бы N^2 состояний, но каждое считается за O(n), пока много.
Можно заменить, что нам каждый раз нужны лишь частичные суммы предудщей строки. А если a==k, то ответ 0 (логично, потому что ну не может число k быть строго меньше соседей).
Можно подсчитать частичные суммы строки, а можно заметить, что при сдвиге a на единицу у нас в частичных суммах получится лишь одно новое слагаемое. В итоге получаем:
База:
DP[1,k] = 1
DP[n,k] = 0
Переход:
DP[n,a] = DP[n,a+1] + DP[n-1,k-a]
Ответ:
(DP[n,1] + ... + DP[n,k]) * 2
Ответ - надо взять все последовательности длины n, заканчивающиеся на что у годно и умножить на 2.
База - для a=k ответ всегда 0, кроме первой строки, где всегда 1 последовательность кончающаяся на фиксированное число (ведь длина - 1. Это само число и есть вся последовательность).
При чем тут достаточно хранить только 2 последние строки. А может заметить, что каждый раз мы считаем частичные суммы начиная с 0 и записываем их в следующую строку задом-наперед. Ну так можно сделать это на месте: подсчитать частичные суммы, а потом развернуть массив.
Вот и все решение. Арифметику по модулю добавьте сами.
int CountSequences(int n, int k) {
vector<int> dp(k, 1);
for (int i =0; i < n-1; ++i) {
int sum = 0;
for (int j = 0; j < k; ++j) {
int prev = sum;
sum += dp[j];
dp[j] = prev;
}
reverse(dp.begin(), dp.end());
}
int ans = 0;
for (int x : dp) ans += x;
ans *= 2;
return ans;
}
Вообще, тут кажется можно комбинаторикой и какую-то формулу за O(n) вывести.
Простой