Codeforces Round 767 (Div. 1) |
---|
Закончено |
Это сложная версия задачи. Разница заключается в ограничениях на $$$n$$$, $$$m$$$ и $$$t$$$. Делать взломы можно только в том случае, если решены обе задачи.
Алисе и Бобу даются числа $$$n$$$, $$$m$$$ и $$$k$$$, и они играют в следующую игру:
В игре есть счет, который Алиса пытается максимизировать, а Боб старается минимизировать. Первоначально счет равен $$$0$$$. Игра состоит из $$$n$$$ ходов. Каждый ход Алиса выбирает число от $$$0$$$ до $$$k$$$ (необязательно целое), которое Боб либо прибавляет, либо вычитает из счета игры. Но на протяжении всей игры Боб должен прибавить не менее $$$m$$$ из $$$n$$$ ходов.
Боб узнает, какое число выбрала Алиса, прежде чем решит, прибавить или вычесть это число из счета, а Алиса узнает, прибавил Боб или вычел число для предыдущего хода, прежде чем выбрать число для текущего хода (кроме первого хода, поскольку предыдущего хода не было).
Если Алиса и Боб будут играть оптимально, каков будет окончательный счет игры?
Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество тестов. Описание тестовых примеров следует ниже.
Каждый тестовый пример состоит из одной строки, содержащей три целых числа: $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le m \le n \le 10^6, 0 \le k < 10^9 + 7$$$) — количество ходов, сколько из этих ходов Боб должен прибавить, и наибольшее число, которое Алиса может выбрать соответственно.
Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$10^6$$$.
Для каждого тестового примера выведите одно число — результат оптимальной игры по модулю $$$10^9 + 7$$$.
Формально пусть $$$M = 10^9 + 7$$$. Можно показать, что ответ может быть выражен в виде неприводимой дроби $$$\frac{p}{q}$$$, где $$$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}$$$.
Название |
---|