{"problem":{"name":"E. Knight Paths","description":{"content":"A knight stands in the top-left corner of an $8 times 8$ chessboard. You can move it *at most* $k$ times. Count such possible paths modulo $2^(32)$. Formally, count paths of cells $(C_1, C_2, \\\\dots,","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10264E"},"statements":[{"statement_type":"Markdown","content":"A knight stands in the top-left corner of an $8 times 8$ chessboard. You can move it *at most* $k$ times. Count such possible paths modulo $2^(32)$.\n\nFormally, count paths of cells $(C_1, C_2, \\\\dots, C_s)$ such that $1 <= s <= k + 1$ and a knight can move from $C_i$ to $C_{i + 1}$ for every $i$.\n\n(A chess knight moves to a square that is two squares away horizontally and one square vertically, or one away horizontally and two vertically.)\n\nAn integer $k$ ($0 <= k <= 10^9$).\n\nPrint the answer modulo $2^(32) = 4294967296$.\n\nIn the first sample test, a knight can either stay in the initial cell $(1, 1)$ or move to $(2, 3)$ or $(3, 2)$. That's 3 ways in total.\n\n## Input\n\nAn integer $k$ ($0 <= k <= 10^9$).\n\n## Output\n\nPrint the answer modulo $2^(32) = 4294967296$.\n\n[samples]\n\n## Note\n\nIn the first sample test, a knight can either stay in the initial cell $(1, 1)$ or move to $(2, 3)$ or $(3, 2)$. That's 3 ways in total.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $, where all vertices are initially strongly connected.  \nLet $ k \\in \\mathbb{Z} $, $ 0 \\leq k < n $, be the number of edges to retain.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ n \\leq m \\leq 2 \\cdot 10^5 $  \n3. $ 0 \\leq k < n $  \n4. All edges are distinct, no self-loops.  \n5. Initially, $ G $ is strongly connected.  \n\n**Objective**  \nSelect a subset $ E' \\subseteq E $ with $ |E'| = k $ such that the subgraph $ G' = (V, E') $ has the **maximum possible number of strongly connected components**.  \n\nOutput:  \n- The maximum number of strongly connected components in $ G' $.  \n- Any subset of $ k $ edge indices achieving this maximum.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10264E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}