[KMOI R1] 集合 First

Luogu

IDLGP9708

Time1000ms

Memory128MB

DifficultyP3

数学O2优化构造

有一个集合 $A=\{1,2,3\dots,n\}$。定义交替和 $G(B)$ 如下： - 把集合 $B$ 中的元素从大到小排序，得到 $B=\{b_1,b_2\dots,b_{cnt}\}$（$cnt$ 为集合元素个数）。则 $G(B)=\sum\limits_{i=1}^{cnt}\Big((-1)^{i+1}\times b_i\Big)$。例如 $G(\{1,2,4,6,9\})=9-6+4-2+1=6$。特别地，$G(\empty)=0$。现在，给定集合 $A=\{1,2,3,\dots,n\}$，小谢想知道对于 $A$ 的**任意子集 $P$**，求出 $G(P)$ 的总和。由于小谢太菜了，所以请你帮帮忙，**答案对 $911451407$ 取模。** ## Input 一个正整数 $n$，表示给定的集合 $A=\{1,2,3,\dots,n\}$。 ## Output 一个正整数 $ans$，表示对于 $A$ 的**任意子集 $P$**，$G(P)$ 的总和。 **答案对 $911451407$ 取模。** [samples] ## Note ## 样例 $1$ 解释 $G(\empty)=0$ $G(\{1\})=1$ $G(\{1,2\})=1$ $G(\{2\})=2$ 故 $ans=G(\empty)+G(\{1\})+G(\{1,2\})+G(\{2\})=4$。 ## 数据范围 **本题采用 subtask 捆绑测试。** |子任务编号| 测试点 | $n\le$ | 分值 | |:-:| :----------: | :----------: | :----------: | |$1$| $1,2$ | $20$ | $15$ | |$2$| $3\sim5$ | $10^3$ | $10$ | |$3$| $6\sim10$ | $10^{9}$ | $30$ | |$4$| $11\sim17$ | $10^{16}$ | $45$ | 对于 $100\%$ 的数据：$1\le n\le 10^{16}$。 ## 后记 $$\color{orange}{小谢：别打我，我下次再也不研究大小超过\ 30\ 的集合了。}$$ $$\color{purple}{你：我*****}$$

Samples

Input #1

Output #1

Input #2

Output #2

476463243

Input #3

Output #3

193840227

API Response (JSON)

{
  "problem": {
    "name": "[KMOI R1] 集合 First",
    "description": {
      "content": "有一个集合 $A=\\{1,2,3\\dots,n\\}$。 定义交替和 $G(B)$ 如下： - 把集合 $B$ 中的元素从大到小排序，得到 $B=\\{b_1,b_2\\dots,b_{cnt}\\}$（$cnt$ 为集合元素个数）。则 $G(B)=\\sum\\limits_{i=1}^{cnt}\\Big((-1)^{i+1}\\times b_i\\Big)$。 例如 $G(\\{1,2,4,6,9\\})",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9708"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个集合 $A=\\{1,2,3\\dots,n\\}$。\n\n定义交替和 $G(B)$ 如下：\n\n- 把集合 $B$ 中的元素从大到小排序，得到 $B=\\{b_1,b_2\\dots,b_{cnt}\\}$（$cnt$ 为集合元素个数）。则 $G(B)=\\sum\\limits_{i=1}^{cnt}\\Big((-1)^{i+1}\\times b_i\\Big)$。\n\n例如 $G(\\{1,2,4,6,9\\})...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments