Решение задачи "Разбиения перестановки" с Codeforces

Без пояснения   Просмотров: 10


Вам дана перестановка p1,p2,…,pn целых чисел от 1 до n и целое число k, такое что 1≤k≤n. Перестановка обозначает, что каждое значение от 1 до n содержится в p ровно один раз.

Рассмотрим все разбиения этой перестановки на k отрезков. Формально, такое разбиение это множество отрезков {[l1,r1],[l2,r2],…,[lk,rk]}, такое что:

1≤li≤ri≤n для всех 1≤i≤k.
Для всех 1≤j≤n существует ровно один отрезок [li,ri], такой что li≤j≤ri.
Два разбиения считаются различными, если существует отрезок, лежащий в одном разбиении, но не лежащий в другом.

Давайте посчитаем значение разбиения ∑i=1kmaxli≤j≤ripj для всех возможных разбиений перестановки на k отрезков. Ваша задача найти максимальное значение разбиения по всем таким разбиениям и количество таких разбиений, значение которых равно максимально возможному. Поскольку второе число может быть слишком большим, вы должны найти его остаток при делении на 998244353.

Код

#include <iostream>
using namespace std;
main() {
	int n, m, len = 0;
	long long ans = 0;
	cin >> n >> m;
	cout << 1ll * (2 * n - m + 1) * m / 2 << ' ';
	for (int i = 0; i < n; ++i) {
		++len;
		int a;
		cin >> a;
		if (a > n - m) ans *= len, ans %= 998244353, len = 0, ans += ans == 0;
	}
	cout << ans;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться