#B. [CZOJ 一周一测 R8 B] 【模板】数位 dp

    传统题 1000ms 256MiB

[CZOJ 一周一测 R8 B] 【模板】数位 dp

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.

题目背景

注意:这 不 是 数位&*!@#(dp)!#模?>.\版*题!@$=@。

题目描述

对于一个正整数 nn,令 nn 在二进制下从最低位到最高位的数位依次为 n0,n1,,nkn_0, n_1, \dots, n_k,例如,若 n=11n = 11,则 k=3k = 3n0=1,n1=1,n2=0,n3=1n_0 = 1, n_1 = 1, n_2 = 0, n_3 = 1

nn权值 f(n)f(n) 表示为 $\sum\limits_{i=0}^k [i \bmod 2 = 1]n_i - \sum\limits_{i=0}^k [i \bmod 2 = 0]n_i$。对于一个正整数 nn,它被称作是 好的 当且仅当 f(n)\lvert f(n) \rvert33 的倍数。

给出 L,RL, R,请你求出满足 LnRL \leq n \leq R好的 nn 的个数。

输入格式

本题单个测试点内有多组数据。

第一行一个整数 TT,表示数据组数。

接下来 TT 行,每行两个整数 L,RL, R 描述一组数据。

输出格式

TT 行,每行一个整数表示答案。

样例

1
4 7
1

样例解释

[4,7][4, 7] 之间的数中只有 66 满足 f(n)=0\lvert f(n) \rvert = 033 的倍数。

数据规模与约定

本题采用捆绑测试。

  • Subtask 0(13 pts):R10R \leq 10
  • Subtask 1(20 pts):R3×103R \leq 3\times 10^3
  • Subtask 2(20 pts):R5×105R \leq 5\times 10^5
  • Subtask 3(47 pts):无特殊限制。

对于所有数据,1LR10181 \leq L \leq R \leq 10^{18}1T2×1041 \leq T \leq 2\times 10^4

[CZR-008] CZOJ Weekly Exercise Round 8

未参加
状态
已结束
规则
IOI
题目
6
开始于
2024-2-17 17:00
结束于
2024-2-17 22:00
持续时间
5 小时
主持人
参赛人数
20