Это сложная версия задачи. Разница заключается в ограничениях на n, m и t. Делать взломы можно только в том случае, если решены обе задачи.
Алисе и Бобу даются числа n, m и k, и они играют в следующую игру:
В игре есть счет, который Алиса пытается максимизировать, а Боб старается минимизировать. Первоначально счет равен 0. Игра состоит из n ходов. Каждый ход Алиса выбирает число от 0 до k (необязательно целое), которое Боб либо прибавляет, либо вычитает из счета игры. Но на протяжении всей игры Боб должен прибавить не менее m из n ходов.
Боб узнает, какое число выбрала Алиса, прежде чем решит, прибавить или вычесть это число из счета, а Алиса узнает, прибавил Боб или вычел число для предыдущего хода, прежде чем выбрать число для текущего хода (кроме первого хода, поскольку предыдущего хода не было).
Если Алиса и Боб будут играть оптимально, каков будет окончательный счет игры?
Первая строка входных данных содержит единственное целое число t (1≤t≤105) — количество тестов. Описание тестовых примеров следует ниже.
Каждый тестовый пример состоит из одной строки, содержащей три целых числа: n, m и k (1≤m≤n≤106,0≤k<109+7) — количество ходов, сколько из этих ходов Боб должен прибавить, и наибольшее число, которое Алиса может выбрать соответственно.
Гарантируется, что сумма n по всем тестам не превышает 106.
Для каждого тестового примера выведите одно число — результат оптимальной игры по модулю 109+7.
Формально пусть M=109+7. Можно показать, что ответ может быть выражен в виде неприводимой дроби pq, где p и q — целые числа, q \not \equiv 0 \pmod{M}. Выведите целое число, равное p \cdot q^{-1} \bmod M. Другими словами, выведите такое целое число x, что 0 \le x < M и x \cdot q \equiv p \pmod{M}.
73 3 22 1 106 3 106 4 10100 1 14 4 069 4 20
6 5 375000012 500000026 958557139 0 49735962
В первом тестовом примере вся игра имеет 3 хода, и, поскольку m = 3, Боб должен добавить в каждый из них. Следовательно, Алиса должна каждый ход выбирать самое большое число, которое она может, а именно k = 2.
В третьем тестовом примере у Алисы есть стратегия, гарантирующая оценку \frac{75}{8} \equiv 375000012 \pmod{10^9 + 7}.
В четвертом тестовом примере у Алисы есть стратегия, гарантирующая оценку \frac{45}{2} \equiv 500000026 \pmod{10^9 + 7}.
| Codeforces Round 767 (Div. 1) |
|---|
| Закончено |
