use iterative segment tree

Can I delete all my personal data here?

Edited by author 28.08.2025 15:29

My Accepted solution got wrong answer on test:

10 3
1 1 6
??????????

My output: X?X?XXXXXX
Correct output: X.X.XXXXXX

1) Посмотрим, как выглядят плохие расстановки. Тогда ответ = количество хороших расстановок / количество всех расстановок. Обозначим расстановки карт как x = x_1 x_2 ... x_2n.
2) Количество всех расстановок (2n)!
3) Как выглядят плохие расстановки, те когда пасьянс в конце будет содержать >=3 карт?
Чтобы нельзя было сделать ход, нужно чтобы суффикс имел вид (1) ai * bj либо (2) bi * aj, где i != j, а * - любая карта. Заметим, что если какой-то суффикс x после всех просеиваний переходит в один из таких видов, то пасьянс не сойдётся. Можно доказать обратное: если никакой суффикс x при просеиваниях не перейдёт в (1) или (2), то пасьянс сойдется.
4) Из 3) можно построить все плохие расстановки. Они будут иметь вид:
x_1 ... x_[2n-3] bj x_[2n-1] ai
x_1 ... x_[2n-4] bj a_l1 a_l2 ai
x_1 ... x_[2n-5] bj a_l1 a_l2 a_l3 ai
x_1 ... x_[2n-5] bj a_l1 a_l2 a_l3 a_l4 ai
...
Здесь bj, ai, a_l1, a_l2, ... - выбранные карты (j != i), x_k - оставшиеся карты.
Аналогично к плохим расстановкам будут относится все с заменой местами bj и ai (вместо a_l1, a_l2, ... будут b_l1, b_l2, ...).
Первых расстановок ровно 2n*(n-1)*(2n-2)!
Вторых расстановок  2n*(n-1)*(n-1)*(n-2)*(2n-4)! = 2n*(n-1)*(n-1)! * (2n-4)!
Третьих расстановок  2n*(n-1)*(n-1)*(n-2)*(n-3)*(2n-5)! = 2n*(n-1)*(n-1)! / 2! * (2n-5)!
Четвертых расстановок  2n*(n-1)*(n-1)*(n-2)*(n-3)*(n-4)*(2n-6)! = 2n*(n-1)*(n-1)! / 3! * (2n-6)!
И т.д. до n+1.

Итого плохих расстановок bad_cnt = 2n*(n-1)*(2n-2)! + 2n*(n-1)*(n-1)! * sum((2n-k)!/(n-k+1)!), k=4,...,n+1

good_cnt = (2n)! - bad_cnt
d = gcd(good_cnt, (2n)!)
Ответ = (good_cnt / d, (2n)! / d)

PS: надеюсь не опечатался


Тесты:
(2, '2/3')
(3, '8/15')
(4, '13/28')
(5, '19/45')
(6, '13/33')
(7, '34/91')
(8, '43/120')
(9, '53/153')
(10, '32/95')
(11, '76/231')
(12, '89/276')
(13, '103/325')
(14, '59/189')
(15, '134/435')
(16, '151/496')
(17, '169/561')
(18, '94/315')
(19, '208/703')
(69, '2483/9453')
(100, '5149/19900')
(666, '111388/443223')
(1234, '381614/1522139')
(10000, '50014999/199990000')
(100000, '5000149999/19999900000')

Edited by author 12.08.2025 22:29

k = 1

ez

Precalc + don't use set, use bitsets instead

"You have to determine whether such a stupid DEFEAT is possible." NOT a victory, but a DEFEAT.

Edited by author 11.08.2025 12:41

Problem with accuracy, you should print exactly 3 digit after dot

You can use sqrt-decomposition to find nearest point. It much easier than tangent, but slowly

period + preperiod always < 100, so you can use bruteforce:)

WA21;
My tests:
N=9 =>286
N=13 =>12486
N=20 =>12826228
N=25 =>1142161275355632
N=33 =>13654755591665021157

3
0 0 6 8
6 -3 11 6
11 -3 21 0

Answer
21

Please, help!!! Tell me the test 28!

if you use dp + bimatching your matching algo is wrong

We have number n = a * (10 ^ n) + b.

n mod a = 0
and
n mod b = 0

If n mod a = 0 that b mod a = 0.
If n mod b = 0 that a * (10 ^ n) mod b = 0

We have now
b mod a = 0
a * (10 ^ n) mod b = 0

Ok, now let's imagine b = k * a. First condition is fulfilled.
a * (10 ^ n) / (k * a) = 10 ^ n / k

K is divider of 10 ^ n.
Let's note that k is less then 10. Why? Because a * 10 have n + 1 digit but b must have n digit.
Now for all 1 <= k <= 9 and 10^n mod k = 0 we calculate how many good numbers a we can use, a * k must have n digit that 10 ^ (n - 1) <= a <= (10 ^ n - 1) // k. Sum of all good ways to choose a and k is answer!

Let l="line which connects top corner of cone and one of the points on the corner of base"
Also a="angle between 'l' and surface"

A line is drawn on the surface with distance d to the center of cone. Then two 2d planes are drawn through this line. The angle between plane and surface is equal to 'a'. These planes are directed in the opposite angles. Set of points that are in the cone and between these 2d planes will fall in the slit

At first N = p * q, let's find this prime numbers p and q.
Now we have x * x = x mod N.
x * x - x = 0 mod N
x * (x - 1) = 0 mod N
Let's note that x != pq, because x < n. That means x mod p = 0, x - 1 mod q = 0 or x mod q = 0, x - 1 mod p = 0.
Consider {
x mod p = 0
x mod q = 1
}
another case is symmetrical.
x = k * p, because x mod p = 0.
Now we have k * p mod q = 1
k = 1 / p mod q
k = p ^ (-1) mod q
Use Fermat's little theorem k = p ^ (q - 2) mod q.
We find x = k * p, problem is solved.

Rotations with cycles of length 2 actually have two fixed points