{"problem":{"name":"L. Kim Possible and the Mooks and the Swappinator","description":{"content":"Kim Possible has infiltrated Dr. Drakken's lair again and has to fight off some MOOKS and MEEKS in order to stop him from his evil schemes. Like last time, Dr. Drakken knew Team Possible was coming f","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10253L"},"statements":[{"statement_type":"Markdown","content":"Kim Possible has infiltrated Dr. Drakken's lair again and has to fight off some MOOKS and MEEKS in order to stop him from his evil schemes.\n\nLike last time, Dr. Drakken knew Team Possible was coming for him as they always have. So he prepared a magical scientific device to strengthen his army of MOOKS and MEEKS.\n\nAll the MOOKS and MEEKS form a straight line and Kim Possible has to fight them starting from the first one. The MEEKS don't fight because they are tired, but the MOOKS take Kim one minute to defeat. Whenever Kim Possible defeats a MOOK, the MOOK will use his McGuffin which drains all of his energy and throws Kim Possible back to the start of the line. All the MEEKS in front of the MOOK get re-energized and turn back into MOOKS with their McGuffin fully recharged, but the MOOK that used his McGuffin turns into a MEEK, fully drained of energy.\n\nThis time however, Team Possible was more prepared and the scientific genius Wade provided Kim Possible with a device called the Swappinator. The Swappinator can swap the positions of any two distinct opponents of Kim Possible and can be used $k$ times.\n\nGiven the initial line of MOOKS and MEEKS and the optimal use of the swappinator, how many minutes will it take for Kim Possible to defeat all the MOOKS and turn them into MEEKS? Note that the Swappinator must be used _exactly_ $k$ times and must be used before any attacks.\n\nOutput the answer mod $10^9$.\n\nThe input is composed of two lines. The first line contains two integers $n$ and $k$, the number of MOOKS/MEEKS and the number of times Team Possible can use the Swappinator, respectively. $n$ lines follow, each is either a MOOK or a MEEK, describing their order in their line.\n\n*Constraints*\n\n$0 <= k <= n$\n\n$2 <= n <= 10^5$\n\nFor each test case, output a single integer which is the #cf_span(class=[tex-font-style-underline], body=[shortest]) amount of time, in minutes and in mod $10^9$, before Kim possible defeats all MOOKS.\n\n## Input\n\nThe input is composed of two lines. The first line contains two integers $n$ and $k$, the number of MOOKS/MEEKS and the number of times Team Possible can use the Swappinator, respectively. $n$ lines follow, each is either a MOOK or a MEEK, describing their order in their line.*Constraints*$0 <= k <= n$$2 <= n <= 10^5$\n\n## Output\n\nFor each test case, output a single integer which is the #cf_span(class=[tex-font-style-underline], body=[shortest]) amount of time, in minutes and in mod $10^9$, before Kim possible defeats all MOOKS.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ t \\in \\mathbb{Z}^+ $ be the number of sequences.  \nFor each sequence $ j \\in \\{1, \\dots, t\\} $:  \n- Let $ n_j, k_j, \\ell_j \\in \\mathbb{Z}^+ $ denote the required number of polynomials, maximum degree, and sequence length, respectively.  \n- Let $ S_j = (s_{j,1}, s_{j,2}, \\dots, s_{j,\\ell_j}) \\in \\mathbb{Z}^{\\ell_j} $ be the sequence of integers.  \n\n**Constraints**  \n1. All arithmetic is performed modulo $ p = 999983 $.  \n2. For each sequence $ j $, we seek nonzero polynomials $ P(x) \\in \\mathbb{Z}_p[x] $ such that:  \n   $$\n   P(s_{j,i}) \\equiv 0 \\pmod{p} \\quad \\forall i \\in \\{1, \\dots, \\ell_j\\}\n   $$  \n3. Each polynomial has degree at most $ k_j $.  \n4. Leading coefficient $ \\neq 0 \\pmod{p} $.  \n5. All coefficients are integers with absolute value $ \\leq 10^9 $.  \n\n**Objective**  \nFor each sequence $ j $:  \n- Output $ \\min(n_j, N_j) $ polynomials, where $ N_j $ is the total number of distinct nonzero polynomials of degree $ \\leq k_j $ over $ \\mathbb{Z}_p $ that vanish on all $ s_{j,i} $.  \n- Each polynomial is output as:  \n  $$\n  d \\quad c_d \\quad c_{d-1} \\quad \\dots \\quad c_0\n  $$  \n  where $ d \\in \\{0, \\dots, k_j\\} $ is the degree, and $ c_d, \\dots, c_0 \\in \\mathbb{Z} $ are coefficients in decreasing order, with $ c_d \\not\\equiv 0 \\pmod{p} $.  \n- Polynomials are considered distinct if their coefficient vectors are not congruent modulo $ p $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10253L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}