[LSOT-2] Tree and Xor

Luogu

IDLGP10157

Time1000ms

Memory512MB

DifficultyP6

数学贪心二分位运算Ad-hoc分类讨论

给定 $n$，你需要构造一棵 $n$ 个点的以 $1$ 为根的有根树，满足 $\bigoplus\limits_{i=1}^ndegree(i)=0$ 且 $fa_2 \sim fa_n$ 的字典序最小。其中，$\oplus$ 表示异或运算。其中 $degree(i)$ 表示与点 $i$ 相连的点数，$fa_i$ 表示点 $i$ 的父节点且 $fa_i < i$。你需要输出 $\sum\limits_{i=2}^ni \times fa_i$，若无解则输出 $-1$。 ## Input 第一行，一个正整数 $T$，表示询问数量。接下来每 $T$ 行每行一个正整数 $n$ 表示一次询问。 ## Output 一共 $T$ 行，每行一个整数表示答案除 $998244353$ 的余数。 [samples] ## Note **「本题采用捆绑测试」** - $\texttt{Subtask 1(5 pts)：}n \leq 7$。 - $\texttt{Subtask 2(10 pts)：} n \leq 20$。 - $\texttt{Subtask 3(20 pts)：}\sum n \leq 2000$。 - $\texttt{Subtask 4(15 pts)：}n = 2^k-1$，其中 $k$ 是自然数。 - $\texttt{Subtask 5(50 pts)：}$无特殊限制。对于所有数据，$1\le T\le 10^6$，$2 \leq n \leq 10^{9}$。

Samples

Input #1

2
2
3

Output #1

2
-1

API Response (JSON)

{
  "problem": {
    "name": "[LSOT-2] Tree and Xor",
    "description": {
      "content": "给定 $n$，你需要构造一棵 $n$ 个点的以 $1$ 为根的有根树，满足 $\\bigoplus\\limits_{i=1}^ndegree(i)=0$ 且 $fa_2 \\sim fa_n$ 的字典序最小。其中，$\\oplus$ 表示异或运算。 其中 $degree(i)$ 表示与点 $i$ 相连的点数，$fa_i$ 表示点 $i$ 的父节点且 $fa_i < i$。 你需要输出 $\\sum\\l",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10157"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$，你需要构造一棵 $n$ 个点的以 $1$ 为根的有根树，满足 $\\bigoplus\\limits_{i=1}^ndegree(i)=0$ 且 $fa_2 \\sim fa_n$ 的字典序最小。其中，$\\oplus$ 表示异或运算。\n\n其中 $degree(i)$ 表示与点 $i$ 相连的点数，$fa_i$ 表示点 $i$ 的父节点且 $fa_i < i$。\n\n你需要输出 $\\sum\\l...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments