Вам дано число . Нужно посчитать суммарное количество инверсий по всем перестановкам длины . Но поскольку это число может быть очень большим, требуется сообщить его остаток при делении на число . Перестановка - это массив длины , где каждое число от 1 до

Добавлена: 09.04.2026
Обновлена: 09.04.2026
Предмет: Высшая математика
Автор: Кэмп

#Дискретная математика
#Теория чисел

Вам дано число . Нужно посчитать суммарное количество инверсий по всем перестановкам длины . Но поскольку это число может быть очень большим, требуется сообщить его остаток при делении на число . Перестановка - это массив длины , где каждое число от 1 до

Условие:

Вам дано число $n$ . Нужно посчитать суммарное количество инверсий по всем перестановкам длины $n$ . Но поскольку это число может быть очень большим, требуется сообщить его остаток при делении на число $10^{9}+7$ .

Перестановка - это массив длины $n$ , где каждое число от 1 до $n$ встречается ровно один раз. А количество инверсий в перестановке $p_{1}, p_{2}, \ldots, p_{n}-$ это количество пар $i, j$ таких, что $i<j$ и $a_{i}>a_{j}$ .

Решение:

Решение задачи о суммарном количестве инверсий

1. Дано

Число $n$ , где $1 \leq n \leq 10^5$ .

2. Найти

Суммарное количество инверсий по всем перестановкам длины $n$ , по модулю $M = 10^9 + 7$ .

3. Решение

Пусть $S_n$ — суммарное количество инверсий по всем перестановкам длины $n$ .

Шаг 1: Определение общего количества перестановок

Общее количество перестановок длины $n$ равно $n!$ .

Шаг 2: Рассмотрение вклада каждой пары индексов

Инверсия определяется парой индексов $(i, j)$ такой, что $i < j$ и $p_i > p_j$ .

Вместо того чтобы перебирать все $n!$ перестановок, мы мож...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какой математический принцип позволяет значительно упростить подсчет суммарного количества инверсий по всем перестановкам, избегая прямого перебора всех перестановок?

Принцип включения-исключения

Принцип линейности ожидания (или принцип симметрии)

Принцип Дирихле (принцип голубиных клеток)