[ICPC 2020 Shanghai R] Sum of Log

Luogu

IDLGP9821

Time1000ms

Memory1024MB

DifficultyP5

2020上海O2优化数位 DPICPC

Given two non-negative integers $X$ and $Y$, determine the value of $$ \sum_{i=0}^{X}\sum_{j=[i=0]}^{Y}[i\&j=0]\lfloor\log_2(i+j)+1\rfloor $$ modulo $10^9+7$ where - $\&$ denotes bitwise AND; - $[A]$ equals 1 if $A$ is true, otherwise $0$; - $\lfloor x\rfloor$ equals the maximum integer whose value is no more than $x$. ## Input The first line contains one integer $T\,(1\le T \le 10^5)$ denoting the number of test cases. Each of the following $T$ lines contains two integers $X, Y\,(0\le X,Y \le 10^9)$ indicating a test case. ## Output For each test case, print one line containing one integer, the answer to the test case. [samples] ## Note For the first test case: - Two $(i,j)$ pairs increase the sum by 1: $(0, 1), (1, 0)$ - Six $(i,j)$ pairs increase the sum by 2: $(0, 2), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0)$ So the answer is $1\times 2 + 2\times 6 = 14$.

Samples

Input #1

Output #1

14
814
278

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2020 Shanghai R] Sum of Log",
    "description": {
      "content": "Given two non-negative integers $X$ and $Y$, determine the value of  $$ \\sum_{i=0}^{X}\\sum_{j=[i=0]}^{Y}[i\\&j=0]\\lfloor\\log_2(i+j)+1\\rfloor $$ modulo $10^9+7$ where - $\\&$ denotes bitwise AND; - $[A]$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9821"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given two non-negative integers $X$ and $Y$, determine the value of \n$$ \\sum_{i=0}^{X}\\sum_{j=[i=0]}^{Y}[i\\&j=0]\\lfloor\\log_2(i+j)+1\\rfloor $$\nmodulo $10^9+7$ where\n- $\\&$ denotes bitwise AND;\n- $[A]$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments