[LMXOI Round 1] Size

Luogu

IDLGP10114

Time1000ms

Memory512MB

DifficultyP4

O2优化

魔女给出一个长度为 $n$ 的序列 $d$，魔女想要求得： $$\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{((d_i\oplus d_j)+(d_i \otimes d_j))}$$ 其中定义 $\oplus$ 代表二进制下两数相加的和数位上 $1$ 的个数， $\otimes$ 代表二进制下较大减较小的差数位上 $1$ 的个数。 ## Input 一行一个整数 $n$ 表示序列的长度。第二行 $n$ 个非负整数，表示序列 $d$。 ## Output 一行一个整数表示答案。 [samples] ## Background 在漆黑的夜晚，魔女带走了 LMX，HQZ 为了拯救 LMX。要完成魔女给出的任务。 ## Note **样例解释 #1** 如下表所示，因此答案为 $1 + 2 + 2 + 2 = 7$。 | $i$ | $j$ | $ans$ | | :-----: | :-----: | :-------: | | $1$ | $1$ | $1$ | | $1$ | $2$ | $2$ | | $2$ | $1$ | $2$ | | $2$ | $2$ | $2$ | 对于 $100 \%$ 的数据，保证 $1 \le n\le 2\times 10^6,\sum\limits d_i\le5\times10^7$。 | 子任务编号 | $n$ | 特殊性质 | 分值 | | :--------: | :------------------: | :-------------------------: | :--: | | Subtask #1 | $\le 2\times10^6 $ | $d_i =1$ | $10$ | | Subtask #2 | $\le 5000$ | 无 | $20$ | | Subtask #3 | $\le 2\times 10^6$ | $d_i$ 是 $2$ 的次幂 | $30$ | | Subtask #4 | $\le 2\times 10^6$ | 无 | $40$ |

Samples

Input #1

2
1 3

Output #1

Input #2

10
114514 19 19 810 1477 44151 15260 369 2010 222

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[LMXOI Round 1] Size",
    "description": {
      "content": "魔女给出一个长度为 $n$ 的序列 $d$，魔女想要求得： $$\\sum\\limits_{i=1}^{ n}\\sum\\limits_{j=1}^{n}{((d_i\\oplus d_j)+(d_i \\otimes d_j))}$$ 其中定义 $\\oplus$ 代表二进制下两数相加的和数位上 $1$ 的个数， $\\otimes$ 代表二进制下较大减较小的差数位上 $1$ 的个数。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10114"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "魔女给出一个长度为 $n$ 的序列 $d$，魔女想要求得：\n\n$$\\sum\\limits_{i=1}^{ n}\\sum\\limits_{j=1}^{n}{((d_i\\oplus d_j)+(d_i \\otimes d_j))}$$\n\n其中定义 $\\oplus$ 代表二进制下两数相加的和数位上 $1$ 的个数， $\\otimes$ 代表二进制下较大减较小的差数位上 $1$ 的个数。\n\n## Inpu...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments