{"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$ 的最大值为 $P$，异或最小值为 $Q$，异或之力即为 $P$ 和 $Q$ 的差值。\n\n作为王国的继承者，你被赋予了一个正整数 $n$。你的任务是寻找所有长度为 $n$ 的 01 字符串（注意：字符串可含前导零，即 $(0011)_2$ 是合法的，与 $(11)_2$ 相同都代表着数字 3）中，最大异或之力是多少。这个数可能很大，请输出其对 $10^9 + 7$ 取模之后的结果。\n\n异或运算（$\\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$。\n\n## Input\n\n一行包含一个正整数 $n$，表示字符串的长度。\n\n## Output\n\n一个整数，表示最大异或之力对 $10^9 + 7$ 取模之后的结果。\n\n[samples]\n\n## Background\n\n题目来源：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)）。\n\n## Note\n\n#### 样例解释\n\n长度为 3 的 01 字符有 111、110、101、100、011、010、001、000。  \n对于 $(110)_2$ 也就是 6 来说，当分解成 4 和 2 时取得异或最大值 6，当分解成 3 和 3 时取得最小异或值 0。没有其他情况使得最大与最小异或值差大于 6，故答案为 6。\n\n#### 数据范围\n\n- 对于 $20\\%$ 的数据，$2 \\le n < 10$；  \n- 对于 $40\\%$ 的数据，$2 \\le n < 64$；  \n- 对于 $60\\%$ 的数据，$2 \\le n \\le 10^6$；  \n- 对于 $100\\%$ 的数据，$2 \\le n \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4372","tags":["贪心","2025","广西","位运算"],"sample_group":[["3","6"]],"created_at":"2026-03-03 11:09:25"}}