Wataru

У вас при вычислении cache числа не берутся по модулю. А значит очень быстро переполняют long long и случается фигня. Ведь цикл может начаться на очень больших числах. Вам надо всегда при вычислении брать по модулю m.

И, очевидная оптимизация - так как у вас fib() вызывается от увеличивающихся по порядку индексов, вы вместо функции делайте сразу же seq.push_back((seq[i-2]+seq[i-1]) % m);

Вариант 1 - полный рекурсивный перебор. Есть одна рекурсивная функция, которой передается следующее число, текущая сумма и текущий список взятых чисел. Функция или берет следующее число или пропускает его и вызывается рекурсивно для следующего числа. Если сумма слишком большая - просто возвращается сразу. Если сумма равна n - выводит текущие числа и возвращается.

Можно хранить список взятых чисел в глобальном массвие/списке. Но надо аккуратно его откатывать. Перед рекурсивным вызовом, если добавили новое число, то после вызова его из массива/списка удалите. Так будет потребление памяти O(n) вместо O(n^2).

Что-то типа такого:

void Generate(int n, int next, int sum, vector<int> taken) {
  if (next > n || sum > n) return;
  if (sum == n) {
   Output(taken);
  }
  Generate(n, next+1, sum, taken);
  taken.push_back(next);
  Generate(n, next+1, sum+next, taken);
}

...

Generate(n, 1, 0, {});

Но это решение будет не самым быстрым - ибо оно будет заходить в длинные "тупики".

Вариант 2 - оптимизированный перебор, который не перебирает ничего лишнего. Сначала, как в задаче о рюкзаке, при решении динамическим программированием, найдем все варианты набрать каждую сумму.

Заведите двумерный массив n x (n+1). d[i][j] будет хранить, можно ли собрать сумму j используя числа от 1 до i.

База - d[0][0] = true (нет чисел - ноль набрать можно), d[i][0] = false (нет чисел. Не ноль набрать нельзя).

пересчет: d[i][j] = d[i-1][j-i] or d[i-1][j] (или берем текущее число или нет)
Естественно, первый вариант рассматривается только если i<=j. Можно подсчитать этот массив или рекурсивной функцией с запоминанием или просто тупо двумя вложенными циклами.

Потом модифицируем нашу рекурсивную функцию из первого варианта. Теперь она будет как бы идти с конца и параметры будут - сколько первых чисел мы можем использовать, какую сумму должны набрать и какие бОльшие числа уже взяли. В функции опять 2 варианта - или берем текущее число или нет. Но при этом смотрим в массиве d[][], а можем ли мы вообще набрать нужную сумму данными нам числами. Если нет - сразу возвращаемся. Когда пришли к оставшейся сумме в 0, выводим набранные числа.

Оба решения имеют временную сложность O(2^n), но второе будет в несколько раз быстрее, потому что не перебирает никаких тупиков. Возможно, если еще подумать можно избваиться от динамического программирования и вообще вывести формулу, когда из чисел от 1 до i можно собрать заданное число k (может там формула типа i*(i+1)/2 <= k).

Если у вас задача стоит не вывести все наборы (их много! Порядка 2^n), а подсчитать их количество, то тут не надо рекурсивного перебора, а можно подифицировать динамическое программирование, которое будет вместо true/false считать сколько способов собрать из i чисел сумму j. будет формула вида d[i][j] = d[i-1][j] + d[i-1][j-i]. Тогда все решение будет за O(n^2) по времени и можно сделать его O(n) по памяти, если немного подумать (и хранить только две или одну строку матрицы d).

Давайте составим рекурентное соотношение. Пусть F(n) - сколько работает ваша функция при входе в n элементов.

В функции:
- Выделяется новый массив: n операций
- Вызывается функция для укороченного массива: F(n-1) операций
- Цикл по всем перестановкам n-1 элемента: (n-1)! повторений
- Вложенный цикл по позициям: n*(n-1)! = n! повторений
- вложенное в циклы построение новой перестановки: n*n! операций

Итого F(n) = n + F(n-1) +n*n!

Можно раскрыть рекурсивно и получим:
F(n) = 1 + 2 + 3 + ... + n + n*n! + (n-1)*(n-1)! + (n-2)*(n-2)! + ... +1
Аккуратно посмотрев на это можно понять, что все члены, начиная от (n-1)*(n-1)!, cумарно меньше n*n!, а первые n членов вообще мизерные и их можно отбросить.
В итоге, F(n) = O(n*n!).

Обратите внимание, тут мало просто взять самый большой член. Их же n штук и если бы они были примерно одинакового порядка, то возник бы еще один множитель n в ответе. Но тут остальные члены как минимум в n раз меньше самого крупного.

Сложность по памяти такая же - ведь вы там в итоге храните все перестановки, их n! и каждая занимает n. Но это оценка ассимптотики - O(n*n!). На самом деле будет чуть больше n*n! элементов, потому что хранится список ответ и список для меньших перестановок, плюс стек и промежуточные массивы при конкатенации.

Это хорошая ассимптотика - для построения всех перестановок меньше нельзя.
Однако, если вам не надо все перестановки хранить в памяти (да и для кэша, кстати) будет заметно быстрее генерировать следующую перестановку из текущей на месте, как описано тут. Хоть и с такой же ассимптотикой, этот алгоритм будет работать в несколько раз быстрее.

Немного пальцем в небо, но попробуйте заменить "/" на "//". Вам же надо в целых числах считать. Возможно, питон пытается блинные числа приводить к даблу и потом назад к длинными и теряет точность.

Вместо ceil(a/b) используйте (a+b-1)//b
Вместо floor(a/b) или, когда делится без остатка используйте a//b

В логике решения ошибки я не вижу.

Это классическая задача о рюкзаке.

Можно составить такое ДП: F(c, k) - максимальное количество страниц, которые можно набрать из первых k книг общей стоимостью ровно c.

База: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
Пересчет:

F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))

Это ДП приведено в википедии, например. Ответ - максимум по всем c F(c,k).

Есть одна хитрость при реализации - можно обойтись только одной строкой этой матрицы, если вам не нужно восстанавливать весь набор книг в ответе, а только его лучшее значение (только надо поменять параметры местами - строка размером с максимальную цену). Это сократит потребление памяти в K раз, если у вас K книг. На скорость работы решения это не влияет.

Сначала реализуйте все дп на матрице снизу вверх, двумя циклами.
Теперь, если вы будете гнать внутренний цикл с конца к началу, то вам не понадобится смотреть на уже переписанные на текущей итерации внешнего цикла значения, и можно забить на второй параметр ДП и просто переписывать строку на месте.

Есть решение, но оно на плохих тестах, если не повезет, не влезет в лимит.
Чтобы вам повезло, можно "перемешать" входные данные случайным образом. Заведите случайную перестановку. Далее внизу я про нее как бы забуду, но когда я говорю спросить про элементы i и j вы должны справшивать про p[i] и p[j]. Как только вы найдете, что 0 в p[k] - про эту случайную перестановку можно забыть и далее использовать элемент p[k] для востановления перестановки.

Спросите про элементы 0 и 1. Запомните a[0] | a[1].

Вот у вас есть 2 элемента каких-то, вы знаете их позиции и a[i]|a[j]. Мы будет добавлять к ним элементы 2..n-1 по одному, все время выбрасывая один или несколько, в которых нуля точно нет.

Вот есть у вас элеметы x, y и вы знаете a=x|y. возьмем новый элемент z и спросим b=y|z.

Мог ли 0 быть в x? тогда бы a = x|y=0|y = y. Т.е. предыдущее значение a должно вкладываться в новое b как множество единиц. Аналогичный критерий для возможности z быть нулем - b вкладывается в a.

Eсть 4 взаимоисключающих варианта, как множества бит a и b соотносятся:
1) a целиком вкладывается в b, или a|b == b, a != b, например 5 вкладывается в 7.
2) b целиком вкладывается в a, или a|b == a, a != b
3) a == b
4) ничего из выше перечисленного, например, 3 и 6.

Мы уже становили, что x может быть 0 только в случаях 1) и 3). z может быть нулем только в случаях 2) и 3).

В каких случаях может быть нулем y? только в 1), 2) и 4)

Теперь алгоритм, если выпал случай 1), то мы выбрасываем z. При этом значение текущего OR уменьшилось как множество.

Если выпал случай 2), то мы выбрасываем x. При этом значение текущего OR уменьшилось как множество.

Если выпал вариант 3), то мы выбрасываем y и нам придется спросить x|z, ведь нам надо знать OR оставшихся элеметов. Это плохо тем, что мы спросили 2 раза, рассморев один новый элемент. В неудачном случае мы бы задали 2n вопросов только ища 0 и у нас не осталось бы квоты на восстановление самой перестановки.

Но тут есть 2 подварианта. 3а) Если значение x|z стало меньше, как множество, то ок. 3б) Но оно еще могло бы остаться таким же, т.е. x|y=y|z=x|z. Но в этом случае, по аналогичным рассуждениям нуля не может быть нигде среди этих трех элементов! А значит мы можем выкинуть и их все, избавившись от двух элементов за два вопроса.

Если выпал вариант 4), то мы выбрасываем x или z.

Таким образом задав от n до 2n (в самом неудачном случае) мы получаем в конце 2 элемента в одном из которых точно 0, а второй - a.

Чтобы восстановить кто из двух оставшихся элементов кто: по ходу отсеивания, задавая любой вопрос запоминайте для какой пары чисел вы видели нулевой бит в каждом разряде. (Т.е. спросили про i|j получили ответ 5. Тут второй бит 0, значит запомнили, что i|j дает 0 в бите 2. И поддерживайте массив для всех разрядов).
Если вам хоть сколько-нибудь повезет. вы наберете достаточно таких примеров.

Теперь пройдитесь по всем примерам, что вы ранее видели и выберите тот, который имел 0 в разряде, где у a стоит 1. пусть это были элементы i и j. Теперь спросите x|i. Если и там этот разряд 0, то x=0, иначе у=0.

Тут почти нарисовался строго убывающий инвариант - размер множетсва бит в OR для текущих кандидатов, но пункт 3б) его ломает, ведь мы получаем 2 новых элемента и множество может стать любым. Но случайный порядок вопросов должен сделать этот вариант маловаероятным. У вас запас примерно 150 впоросов на максимальном тесте. Возможно тут можно придумать какую-то строгую схему, где какой-то инвариант строго убывает на лишних вопросах и может убывать не более 100 раз.

У вас проблема в решении в том, что вы сравниваете 2 обхода. Это неверно для, как вам уже приводили в пример, этих двух деревьев:

1
 \
  2
   \
    3

    3
   /
  2
 /
1

Тут оба обхода вернут 1,2,3.

Можно в вашем решении добавлять всякие разделители при переходе влево-вправо-вверх. Вставить всякие yeild -1 и другие значения перед походом влево, выводом собственно элемента и походом вправо.

Но есть лучшее решение, через DFS или BFS: вы делайте обход одновременно на двух деревьях. Т.е. у вас параметр функции dfs или в очереди в bfs лежат сразу 2 вершины - по одной из каждого дерева. Вы проверяете, что у них значения одинаковые и что у них у обеих одновременно есть или нет левого и правого ребенка. Потом вызываетесь/кладете в очередь одновременно левых детей и одновременно правых детей. Если в процессе обхода вершины оказались разными, или где-то есть ребенок, а где-то нет - то деревья не равны.

Очень логично реализовывается в виде DFS (ниже псевдокод):

Equals(t1, t2):
   // обработать случай null одного или обоих деревьев.
   return t1.v == t2.v && Equals(t1.left, t2.left) && Equals(t1.right, t2.right)

Все предельно логично - 2 дерева равны, если у них равны корни, левые поддеревья и правые поддеревья.

Кстати, ваше решение, если его исправить, тоже будет за O(n).

Я, правда, не понимаю, почему нельзя просто объединить все массивы в один (будет просто список уникальных элементов). Возможно вам нужно максимальное количество массивов.

У этой задачи есть два варианта решения - через обход графа или через систему непересекающихся множеств. Но они оба по сути одно и тоже, просто разные реализации.

Суть в том, чтобы построить граф, где все различные элементы всех массивов будут вершинами. Ребра есть между двумя вершинами, если соответствующие им элементы присутствуют в одном и том же входном массиве.

Ответ на вашу задачу - компоненты связности этого графа. Вариант через граф следующий - для каждого массива перебирайте двумя циклами все пары элементов и добавляйте ребро в граф. Используйте какой-нибудь ассоциативный массив списков для сохранения списка смежности. Или используйте ассоциативный массив для назначения каждому уникальному элементу уникального порядкового номера. Потом список смежности или матрицу инцидентности можно хранить просто по номерам, в виде массива списков или двумерного массива. Потом обходом в глубину или в ширину найдите все компоненты связности.

Чуть проще и быстрее будет работать решение через систему непересекающихся множеств (DSU). Сначала пройдитесь по всем массивам и, как и в первом решении, перенумеруйте все уникальные элементы. Заведите DSU, где каждый элемент - сам себе множество.

Потом пройдитесь по всем элементам каждого входного массива и объединяйте его множество с множеством предыдущего элемента в том же массиве. Попутно, можете считать количество объединений, которые выполнились (множества были различными до выполнения операции union_sets). Так вы можете подсчитать, сколько массивов будет в ответе. В итоге все элементы для каждого массива в ответе будут в одном и том же множестве. Теперь, чтобы вывести ответ заведите массив списков с известным количеством элементов. Используйте ассоциативный массив, чтобы назначить каждому множеству один из списков в ответе. Пройдитесь по всем элементам и дописывайте их в соответствующий список.