{"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$ 的 $f(l,r)$ 的方差 $v$。为避免精度误差，以及答案可能很大，请输出 $(v\\times \\frac{n^2\\times (n+1)^2}{4}) \\kern{3pt}\\mathrm {mod}\\kern{3pt} 998244353$。\n\n**注意：运算过程中不取模，仅将结果取模。**\n\n## Input\n\n第一行一个正整数 $n$。\n\n第二行 $n$ 个正整数 $a_1,a_2,\\cdots,a_n$。\n\n## Output\n\n输出一个整数 $(v\\times \\frac{n^2\\times (n+1)^2}{4}) \\kern{3pt}\\mathrm {mod}\\kern{3pt} 998244353$。\n\n[samples]\n\n## Note\n\n方差的定义：对于 $n$ 个数 $a_1,a_2,\\cdots,a_n$，它们的方差是：\n\n$$\n\\frac 1 n\\sum_{i=1}^n (a_i-\\bar{a})^2\n$$\n\n其中 $\\bar{a}$ 为 $a_1,a_2,\\cdots,a_n$ 的平均数，即 $\\dfrac {1} {n} \\displaystyle\\sum\\limits_{i=1}^n a_i$。\n\n----\n\n对于 $10\\%$ 的数据，$n \\le 50$。\n\n对于 $30\\%$ 的数据，$n \\le 5000$。\n\n对于另 $20\\%$ 的数据，$a_i \\le 100$。  \n\n对于 $100\\%$ 的数据，$1\\le n\\le 10^5,1\\le a_i < 2^{31}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9162","tags":["O2优化"],"sample_group":[["3\n2 1 3","80"],["4\n4 1 3 2","1244"],["5\n1 2 3 2 1","444"]],"created_at":"2026-03-03 11:09:25"}}