Сложная задача на перестановки

@Суренчик · Регистрация: 12.02.2017

Студворк — интернет-сервис помощи студентам

Перестановкой размера n называется массив ⟨a1, a2, . . . , an⟩ различных чисел от 1 до n.
Каждое число в перестановке встречается ровно один раз.
Сеня называет красотой перестановки ⟨a1, a2, . . . , an⟩ число
(a1a2 + a2a3 + . . . + an−1an). Он хочет посчитать количество перестановок, красота
которых делится на k.
Даны числа n и k, найдите количество перестановок размера n, красота которых делится
на k.
Например, для n = 3 существует 6 перестановок. Рассмотрим все эти перестановки и
их красоту.
Перестановка Красота
⟨1, 2, 3⟩ 1 · 2 + 2 · 3 = 8
⟨1, 3, 2⟩ 1 · 3 + 3 · 2 = 9
⟨2, 1, 3⟩ 2 · 1 + 1 · 3 = 5
⟨2, 3, 1⟩ 2 · 3 + 3 · 1 = 9
⟨3, 1, 2⟩ 3 · 1 + 1 · 2 = 5
⟨3, 2, 1⟩ 3 · 2 + 2 · 1 = 8

Добавлено через 4 минуты
Перестановка Красота
⟨1, 2, 3⟩ 1 · 2 + 2 · 3 = 8
⟨1, 3, 2⟩ 1 · 3 + 3 · 2 = 9
⟨2, 1, 3⟩ 2 · 1 + 1 · 3 = 5
⟨2, 3, 1⟩ 2 · 3 + 3 · 1 = 9
⟨3, 1, 2⟩ 3 · 1 + 1 · 2 = 5
⟨3, 2, 1⟩ 3 · 2 + 2 · 1 = 8

@Sun Serega · 23.10.2018, 21:10

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function ПолучитьПерестановки(c: integer; prev: array of integer; i: integer): sequence of array of integer;
begin
  if i=0 then
    prev := new integer[c] else
  if i=c then
  begin
    yield prev;
    exit;
  end;
  for var n := 1 to c do
    if not prev.Contains(n) then
    begin
      var temp := Copy(prev);
      temp[i] := n;
      yield sequence ПолучитьПерестановки(c, temp, i+1);
    end;
end;
 
function ПолучитьПерестановки(c: integer) :=
ПолучитьПерестановки(c,nil,0);
 
begin
  var (c,k) := ReadlnInteger2;
  ПолучитьПерестановки(c)
  .Where(a-> ( a.Pairwise.Sum(t->t[0]*t[1]) mod k )=0 )
  .Count
  .Print;
end.

@Суренчик · 23.10.2018, 21:31 **[ТС]**

Серега, она не работает

@Sun Serega · 23.10.2018, 21:42

Как именно не работает? Скрин + текст ошибки.

@Суренчик · 23.10.2018, 21:49 **[ТС]**

Вот так

@Sun Serega · 23.10.2018, 21:53

А, это была #486, уже давно исправлено. Обновитесь.

@Суренчик · 23.10.2018, 22:15 **[ТС]**

не можешь ли ты объяснить,что и для чего в этой программе? просто я щё учусь,хочу понять способ решения

@Sun Serega · 23.10.2018, 22:23

Ок, какие части непонятны?

@Суренчик · 23.10.2018, 22:28 **[ТС]**

Ну, вообще, как бы, я не проходил ещё таких функций, так что было бы неплохо, если бы ты объяснил всё. Спасибо большое!!!

@Sun Serega · 23.10.2018, 22:37

Каких таких? yield - есть презентация на PascalABC.Net

Что ещё?

@eaa · 24.10.2018, 18:00

А задача точна на "brute force" ?
Какие ограничения на массив a?

@Sun Serega · 24.10.2018, 18:19

Единственное ограничение - при вычислении суммы может возникнуть переполнение. Но для этого надо такое большое n - что программа никогда не досчитает (очень много перестановок будет).

@Суренчик · 24.10.2018, 21:22 **[ТС]**

Серёжа, ты можешь перевести на простой АВС с АВСnet?

Добавлено через 11 минут
Хотя нет, не надо. Спасибо большое!!!!

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28

	Сложная задача на перестановки 23.10.2018, 20:57. Показов 11230. Ответов 12 Метки олимпиадная задача pascal (Все метки) Перестановкой размера n называется массив ⟨a1, a2, . . . , an⟩ различных чисел от 1 до n. Каждое число в перестановке встречается ровно один раз. Сеня называет красотой перестановки ⟨a1, a2, . . . , an⟩ число (a1a2 + a2a3 + . . . + an−1an). Он хочет посчитать количество перестановок, красота которых делится на k. Даны числа n и k, найдите количество перестановок размера n, красота которых делится на k. Например, для n = 3 существует 6 перестановок. Рассмотрим все эти перестановки и их красоту. Перестановка Красота ⟨1, 2, 3⟩ 1 · 2 + 2 · 3 = 8 ⟨1, 3, 2⟩ 1 · 3 + 3 · 2 = 9 ⟨2, 1, 3⟩ 2 · 1 + 1 · 3 = 5 ⟨2, 3, 1⟩ 2 · 3 + 3 · 1 = 9 ⟨3, 1, 2⟩ 3 · 1 + 1 · 2 = 5 ⟨3, 2, 1⟩ 3 · 2 + 2 · 1 = 8 Добавлено через 4 минуты Перестановка Красота ⟨1, 2, 3⟩ 1 · 2 + 2 · 3 = 8 ⟨1, 3, 2⟩ 1 · 3 + 3 · 2 = 9 ⟨2, 1, 3⟩ 2 · 1 + 1 · 3 = 5 ⟨2, 3, 1⟩ 2 · 3 + 3 · 1 = 9 ⟨3, 1, 2⟩ 3 · 1 + 1 · 2 = 5 ⟨3, 2, 1⟩ 3 · 2 + 2 · 1 = 8 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	23.10.2018, 21:31 [ТС]
	Серега, она не работает 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	23.10.2018, 21:42
	Как именно не работает? Скрин + текст ошибки. 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	23.10.2018, 21:49 [ТС]
	Вот так Миниатюры 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	23.10.2018, 21:53
	А, это была #486, уже давно исправлено. Обновитесь. 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	23.10.2018, 22:15 [ТС]
	не можешь ли ты объяснить,что и для чего в этой программе? просто я щё учусь,хочу понять способ решения 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	23.10.2018, 22:23
	Ок, какие части непонятны? 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	23.10.2018, 22:28 [ТС]
	Ну, вообще, как бы, я не проходил ещё таких функций, так что было бы неплохо, если бы ты объяснил всё. Спасибо большое!!! 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	23.10.2018, 22:37
	Каких таких? yield - есть презентация на PascalABC.Net Что ещё? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.10.2018, 18:00
	А задача точна на "brute force" ? Какие ограничения на массив a? 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	24.10.2018, 18:19
	Единственное ограничение - при вычислении суммы может возникнуть переполнение. Но для этого надо такое большое n - что программа никогда не досчитает (очень много перестановок будет). 0

@Суренчик 1 / 1 / 1 Регистрация: 12.02.2017 Сообщений: 28
	24.10.2018, 21:22 [ТС]
	Серёжа, ты можешь перевести на простой АВС с АВСnet? Добавлено через 11 минут Хотя нет, не надо. Спасибо большое!!!! 0

Сложная задача на перестановки

Решение