E. 【拓展题】晶体分裂

    Type: Default 1000ms 256MiB

【拓展题】晶体分裂

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

  你受命前往一颗遥远的行星,完成一项极其重要的任务。这颗行星的核心储存着古老的能量晶体,这些能量晶体拥有神秘的自我分裂特性。为了通过这一考验,你需要分裂这些能量晶体,将它们变成能量稳定的形式。

Description

  最初,这颗能量晶体的能量数值为 m。你可以在每次操作中选择能量值大于 1 的晶体,将其分裂为三个较小的能量晶体,例如现有晶体能量为 xx,分解为三个小晶体:$\lfloor x/2 \rfloor,\ x \mod 2,\ \lfloor x/2 \rfloor$。分裂的过程会持续,直到所有晶体的能量都稳定为 01

  在完成所有分裂后,你需要在一定范围内(从第 k 个到第 s 个位置)观察这些能量晶体的状态,确定其中有多少晶体的能量值为 1。只有正确回答这个问题,你才能完成任务,安全返回母舰。

Format

Input

  第一行包含三个整数 m,k,sm, k, s $(0 \leq m \leq 10^{14}, 0 \leq s - k \leq 10^5, 1 \leq k, s)$,表示初始能量数值与查询范围。

  输入保证 k,sk, s 合法,下标从 1 开始。

Output

  一个整数,表示给定范围内 1 的总数。

Samples

7 1 4
4
77186498974 15392062479 15392086306
13383

实验二 树与分治策略

Not Claimed
Status
Done
Problem
5
Open Since
2024-10-5 14:00
Deadline
2024-10-5 17:30
Extension
144 hour(s)