[GXPC-S 2025] 异或之力 / xor

Luogu
IDLGB4372
Time1000ms
Memory512MB
DifficultyP3
贪心2025广西位运算
传说中,只有能够将力量完美分解的勇者,才能获得王国中最强大的能量 —— 异或之力。 对于每一个 01 字符串都含有一定异或之力。假设某个 01 字符串所代表的十进制数为 $C$,当 $C \le 1$ 时异或之力为 $0$;当 $C > 1$ 时,将 $C$ 分解成任意两个正整数 $A$ 和 $B$ ($A > 0$,$B > 0$,$A + B = C$),得到 $A$ 异或 $B$ 的最大值为 $P$,异或最小值为 $Q$,异或之力即为 $P$ 和 $Q$ 的差值。 作为王国的继承者,你被赋予了一个正整数 $n$。你的任务是寻找所有长度为 $n$ 的 01 字符串(注意:字符串可含前导零,即 $(0011)_2$ 是合法的,与 $(11)_2$ 相同都代表着数字 3)中,最大异或之力是多少。这个数可能很大,请输出其对 $10^9 + 7$ 取模之后的结果。 异或运算($\oplus$):对于两个二进制数的每一位,如果相同则为 $0$,不同则为 $1$。例如,$6\oplus 3=(110)_2\oplus (011)_2=(101)_2=5$,$9\oplus 3=(1001)_2\oplus (0011)_2=(1010)_2=10$。 ## Input 一行包含一个正整数 $n$,表示字符串的长度。 ## Output 一个整数,表示最大异或之力对 $10^9 + 7$ 取模之后的结果。 [samples] ## Background 题目来源:2025 年广西中小学生程序设计挑战赛复赛(进阶组[试题](https://mp.weixin.qq.com/s?__biz=MzI3NDM3MzcwNQ==&mid=2247490166&idx=5&sn=e7ba7e3bc8126027b9abd662518c208b&chksm=ea9c06dd4d18206ed9d88124cc78b947298df2555889e98620204c2ea1471f58c135c00f99fb&mpshare=1&scene=23&srcid=0724dNJdhMxpUHag1dqkhiqL&sharer_shareinfo=7e47197d6e5c044ae705613db988029c&sharer_shareinfo_first=7e47197d6e5c044ae705613db988029c#rd))。 ## Note #### 样例解释 长度为 3 的 01 字符有 111、110、101、100、011、010、001、000。 对于 $(110)_2$ 也就是 6 来说,当分解成 4 和 2 时取得异或最大值 6,当分解成 3 和 3 时取得最小异或值 0。没有其他情况使得最大与最小异或值差大于 6,故答案为 6。 #### 数据范围 - 对于 $20\%$ 的数据,$2 \le n < 10$; - 对于 $40\%$ 的数据,$2 \le n < 64$; - 对于 $60\%$ 的数据,$2 \le n \le 10^6$; - 对于 $100\%$ 的数据,$2 \le n \le 10^9$。
Samples
Input #1
3
Output #1
6
API Response (JSON)
{
  "problem": {
    "name": "[GXPC-S 2025] 异或之力 / xor",
    "description": {
      "content": " 传说中,只有能够将力量完美分解的勇者,才能获得王国中最强大的能量 —— 异或之力。 对于每一个 01 字符串都含有一定异或之力。假设某个 01 字符串所代表的十进制数为 $C$,当 $C \\le 1$ 时异或之力为 $0$;当 $C > 1$ 时,将 $C$ 分解成任意两个正整数 $A$ 和 $B$ ($A > 0$,$B > 0$,$A + B = C$),得到 $A$ 异或 $B$ 的最",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4372"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "传说中,只有能够将力量完美分解的勇者,才能获得王国中最强大的能量 —— 异或之力。\n\n对于每一个 01 字符串都含有一定异或之力。假设某个 01 字符串所代表的十进制数为 $C$,当 $C \\le 1$ 时异或之力为 $0$;当 $C > 1$ 时,将 $C$ 分解成任意两个正整数 $A$ 和 $B$ ($A > 0$,$B > 0$,$A + B = C$),得到 $A$ 异或 $B$ 的最大值...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments