{"raw_statement":[{"iden":"statement","content":"Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility.\n\nInitially Sam has a list with a single element _n_. Then he has to perform certain operations on this list. In each operation Sam must remove any element _x_, such that _x_ > 1, from the list and insert at the same position , , sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.\n\nNow the masters want the total number of 1s in the range _l_ to _r_ (1\\-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?"},{"iden":"input","content":"The first line contains three integers _n_, _l_, _r_ (0 ≤ _n_ < 250, 0 ≤ _r_ - _l_ ≤ 105, _r_ ≥ 1, _l_ ≥ 1) – initial element and the range _l_ to _r_.\n\nIt is guaranteed that _r_ is not greater than the length of the final list."},{"iden":"output","content":"Output the total number of 1s in the range _l_ to _r_ in the final sequence."},{"iden":"examples","content":"Input\n\n7 2 5\n\nOutput\n\n4\n\nInput\n\n10 3 10\n\nOutput\n\n5"},{"iden":"note","content":"Consider first example:\n\nElements on positions from 2\\-nd to 5\\-th in list is \\[1, 1, 1, 1\\]. The number of ones is 4.\n\nFor the second example:\n\nElements on positions from 3\\-rd to 10\\-th in list is \\[1, 1, 1, 0, 1, 0, 1, 0\\]. The number of ones is 5."}],"translated_statement":[{"iden":"statement","content":"Jon 勇敢地战斗，营救了在 Hardhome 遭到白 walkers 攻击的野人。当他到达时，Sam 告诉他，他想去旧镇的学城接受训练，成为一名学士，以便返回黑城堡，接替已故的 Aemon 的位置。Jon 同意了 Sam 的提议，Sam 便启程前往学城。然而，成为学城的学徒并非易事，因此学城的学士们给了 Sam 一个问题来测试他的资格。\n\n最初，Sam 有一个仅包含一个元素 #cf_span[n] 的列表。然后他必须对该列表执行某些操作。在每次操作中，Sam 必须从列表中移除任意一个满足 #cf_span[x > 1] 的元素 #cf_span[x]，并在相同位置依次插入 #cf_span[x / 2], #cf_span[x % 2], #cf_span[x / 2]。他必须持续进行这些操作，直到列表中的所有元素均为 #cf_span[0] 或 #cf_span[1]。\n\n现在，学士们希望知道在区间 #cf_span[l] 到 #cf_span[r]（1-索引）中 #cf_span[1] 的总数。Sam 想成为一名学士，但他无法解决这个问题。你能帮助 Sam 通过资格测试吗？\n\n第一行包含三个整数 #cf_span[n], #cf_span[l], #cf_span[r]（#cf_span[0 ≤ n < 250], #cf_span[0 ≤ r - l ≤ 105], #cf_span[r ≥ 1], #cf_span[l ≥ 1]）——初始元素和区间 #cf_span[l] 到 #cf_span[r]。\n\n保证 #cf_span[r] 不超过最终列表的长度。\n\n请输出最终序列中区间 #cf_span[l] 到 #cf_span[r] 中 #cf_span[1] 的总数。\n\n考虑第一个例子：\n\n\n\n列表中从第 #cf_span[2] 个到第 #cf_span[5] 个位置的元素为 #cf_span[[1, 1, 1, 1]]。其中 1 的数量为 #cf_span[4]。\n\n对于第二个例子：\n\n\n\n列表中从第 #cf_span[3] 个到第 #cf_span[10] 个位置的元素为 #cf_span[[1, 1, 1, 0, 1, 0, 1, 0]]。其中 1 的数量为 #cf_span[5]。\n\n"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n], #cf_span[l], #cf_span[r]（#cf_span[0 ≤ n < 250], #cf_span[0 ≤ r - l ≤ 105], #cf_span[r ≥ 1], #cf_span[l ≥ 1]）——初始元素和区间 #cf_span[l] 到 #cf_span[r]。保证 #cf_span[r] 不超过最终列表的长度。"},{"iden":"output","content":"请输出最终序列中区间 #cf_span[l] 到 #cf_span[r] 中 #cf_span[1] 的总数。"},{"iden":"examples","content":"输入\n7 2 5\n输出\n4\n\n输入\n10 3 10\n输出\n5"},{"iden":"note","content":"考虑第一个例子：\n列表中从第 #cf_span[2] 个到第 #cf_span[5] 个位置的元素为 #cf_span[[1, 1, 1, 1]]。其中 1 的数量为 #cf_span[4]。\n\n对于第二个例子：\n列表中从第 #cf_span[3] 个到第 #cf_span[10] 个位置的元素为 #cf_span[[1, 1, 1, 0, 1, 0, 1, 0]]。其中 1 的数量为 #cf_span[5]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ n \\in \\mathbb{N} $, $ n < 2^{50} $, be the initial single element.\n- Define a transformation rule: any element $ x > 1 $ is replaced by the sequence $ [x-1, x-2, x-1] $ at the same position.\n- The process continues recursively until all elements are $ 0 $ or $ 1 $.\n- Let $ S(n) $ denote the final binary sequence (composed of $ 0 $s and $ 1 $s) obtained by recursively applying the transformation to the initial element $ n $.\n\n**Given:**\n\n- Integers $ n, l, r \\in \\mathbb{N} $, with $ 0 \\leq n < 2^{50} $, $ 1 \\leq l \\leq r $, and $ r - l \\leq 10^5 $.\n- It is guaranteed that $ r \\leq |S(n)| $, the length of the final sequence.\n\n**Objective:**\n\nCompute the number of $ 1 $s in the subsequence $ S(n)[l:r] $ (inclusive, 1-indexed).\n\n---\n\n**Mathematical Formulation:**\n\nLet $ f(x) $ be the final sequence generated from initial value $ x $, defined recursively by:\n\n$$\nf(x) =\n\\begin{cases}\n[1] & \\text{if } x = 1 \\\\\n[0] & \\text{if } x = 0 \\\\\nf(x-1) + f(x-2) + f(x-1) & \\text{if } x > 1\n\\end{cases}\n$$\n\nLet $ L(x) = |f(x)| $, the length of the sequence for initial value $ x $, defined by:\n\n$$\nL(x) =\n\\begin{cases}\n1 & \\text{if } x = 0 \\text{ or } x = 1 \\\\\n2 \\cdot L(x-1) + L(x-2) & \\text{if } x > 1\n\\end{cases}\n$$\n\nLet $ C(x, i, j) $ be the count of $ 1 $s in $ f(x)[i:j] $ (1-indexed, inclusive), for $ 1 \\leq i \\leq j \\leq L(x) $.\n\nWe are to compute $ C(n, l, r) $.\n\n---\n\n**Note:** Due to the exponential growth of $ L(x) $, direct construction of $ f(n) $ is infeasible. Instead, use recursive divide-and-conquer with memoization over $ x $, and range queries based on the recursive structure of $ f(x) = f(x-1) + f(x-2) + f(x-1) $.","simple_statement":null,"has_page_source":false}