variance

Luogu

IDLGP9162

Time2000ms

Memory256MB

DifficultyP6

O2优化

给定序列 $a_1,a_2,\cdots,a_n$，定义 $f(l,r)=(a_l\oplus a_{l+1}\oplus \cdots \oplus a_r)+(a_l\vee a_{l+1}\vee \cdots \vee a_r)$，其中 $\oplus$ 表示 **按位异或** 运算，$\vee$ 表示 **按位或** 运算。你需要求出所有满足 $1\le l \le r \le n$ 的 $f(l,r)$ 的方差 $v$。为避免精度误差，以及答案可能很大，请输出 $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$。 **注意：运算过程中不取模，仅将结果取模。** ## Input 第一行一个正整数 $n$。第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。 ## Output 输出一个整数 $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$。 [samples] ## Note 方差的定义：对于 $n$ 个数 $a_1,a_2,\cdots,a_n$，它们的方差是： $$ \frac 1 n\sum_{i=1}^n (a_i-\bar{a})^2 $$ 其中 $\bar{a}$ 为 $a_1,a_2,\cdots,a_n$ 的平均数，即 $\dfrac {1} {n} \displaystyle\sum\limits_{i=1}^n a_i$。 ---- 对于 $10\%$ 的数据，$n \le 50$。对于 $30\%$ 的数据，$n \le 5000$。对于另 $20\%$ 的数据，$a_i \le 100$。对于 $100\%$ 的数据，$1\le n\le 10^5,1\le a_i < 2^{31}$。

Samples

Input #1

3
2 1 3

Output #1

Input #2

4
4 1 3 2

Output #2

Input #3

5
1 2 3 2 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "variance",
    "description": {
      "content": "给定序列 $a_1,a_2,\\cdots,a_n$，定义 $f(l,r)=(a_l\\oplus a_{l+1}\\oplus \\cdots \\oplus a_r)+(a_l\\vee a_{l+1}\\vee \\cdots \\vee a_r)$，其中 $\\oplus$ 表示 **按位异或** 运算，$\\vee$ 表示 **按位或** 运算。 你需要求出所有满足 $1\\le l \\le r \\le n$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9162"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定序列 $a_1,a_2,\\cdots,a_n$，定义 $f(l,r)=(a_l\\oplus a_{l+1}\\oplus \\cdots \\oplus a_r)+(a_l\\vee a_{l+1}\\vee \\cdots \\vee a_r)$，其中 $\\oplus$ 表示 **按位异或** 运算，$\\vee$ 表示 **按位或** 运算。\n\n你需要求出所有满足 $1\\le l \\le r \\le n$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments