{"problem":{"name":"「DBOI」Round 1 未完成的约定","description":{"content":"$m^3$ 可以表示为 $m$ 个连续奇数的和 $(m \\geqslant 1)$：   $$ 1^3 = 1\\\\ 2^3 = 3 + 5\\\\ 3^3 = 7 + 9 + 11\\\\ 4^3 = 13 + 15 + 17 + 19\\\\ 5^3 = 21 + 23 + 25 + 27 + 29\\\\ \\cdots\\cdots $$ 在左昂对奇数的狂热崇拜的影响下，苏信好写出来的歌只会是奇数长度。显然歌","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":800,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9396"},"statements":[{"statement_type":"Markdown","content":"$m^3$ 可以表示为 $m$ 个连续奇数的和 $(m \\geqslant 1)$：  \n$$\n1^3 = 1\\\\\n2^3 = 3 + 5\\\\\n3^3 = 7 + 9 + 11\\\\\n4^3 = 13 + 15 + 17 + 19\\\\\n5^3 = 21 + 23 + 25 + 27 + 29\\\\\n\\cdots\\cdots\n$$\n\n在左昂对奇数的狂热崇拜的影响下，苏信好写出来的歌只会是奇数长度。显然歌曲的长度不能是负数。\n\n对于一首长度为 $x$ 的歌，它的悦耳值 $f(x)$ 满足将 $f(x)^3$ 按照上面的规律表示出来后，$x$ 是其中的一个加数。例如 $f(21) = 5, f(11) = 3,f(3) = 2$。\n\n第二天，左昂前来参观，发现苏信好只写出来了一首歌，鄙夷不已。苏信好怒从心起，写出了以 $1\\sim k$ 内所有长度为奇数的歌。\n\n现在左昂想要知道苏信好所有歌的悦耳值之和，以预估他的狂热崇拜的效果。即：给定一个正奇数 $k(1\\leqslant k< 2^{64})$，求 $s = \\sum\\limits_{i = 1}^{\\frac{k + 1}{2}} f(2\\times i - 1)$，即 $f(1) + f(3) + f(5) + \\cdots +f(k)$。  \n\n由于苏信好实在太生气，写出来的歌的悦耳值可能十分之大，你只需要输出 $s\\bmod{10^9 + 7}$ 的结果。\n\n**本题有多组数据。**\n\n## Input\n\n为避免输入量过大，你需要使用下面的方式读入，因此请将这段代码复制到你的代码中。**下列程序与此题做法无关，请仔细阅读示例代码中的注释。**\n\n```cpp\nnamespace Mker {\n\ttypedef unsigned long long ull;\n\tull SA, SB, SC, p = -1;\n\tint base;\n\tvoid init(){scanf(\"%llu%llu%llu%d\", &SA, &SB, &SC, &base); p = p << (65 - base) >> (65 - base);}\n\tull rand() {\n\t\tull now = SC; now += !(now & 1);\n\t    SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;\n\t    ull t = SA;\n\t\treturn SA = SB, SB = SC, SC ^= t ^ SA, (now & p) + p + 1;\n\t}\n}\n```\n先读入一个数 $T$，表示数据组数，然后你**需要调用** `Mker::init()`。这个函数将输入四个数 $SA,SB,SC,base$，表示对于这组数据，$k<2^{base}$。\n\n接下来，对于每一组询问，你应当令 $k$ 的值即为 `Mker::rand()`。\n\n示例代码：\n\n```cpp\n#include <bits/stdc++.h>\nusing namespace std;\nint T;\n\nnamespace Mker {\n\ttypedef unsigned long long ull;\n\tull SA, SB, SC, p = -1;\n\tint base;\n\tvoid init(){scanf(\"%llu%llu%llu%d\", &SA, &SB, &SC, &base); p = p << (65 - base) >> (65 - base);}\n\tull rand() {\n\t\tull now = SC; now += !(now & 1);\n\t    SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;\n\t    ull t = SA;\n\t\treturn SA = SB, SB = SC, SC ^= t ^ SA, (now & p) + p + 1;\n\t}\n}\n\nint main() {\n\tscanf(\"%d\", &T); Mker::init(); // 不要忘记 init\n//\tcout << Mker::base << endl; 你可以通过这种方式输出得到 base 的值 \n\twhile (T--) {\n\t\tunsigned long long k = Mker::rand(); // 通过这种方式，获得一次询问的 k\n\t\tif (k == 1) puts(\"1\");\n\t\telse if (k == 17) puts(\"26\");\n\t\telse puts(\"I AK IOI\");\n\t\t\n//\t\tcout << k << endl; 你可以通过这种方式输出得到真实的 k 以调试代码 \n\t}\n\treturn 0;\n}\n```\n\n## Output\n\n$T$ 行，每行一个数 $s\\bmod{10^9 + 7}$，其中 $s$ 表示苏信好的歌的悦耳值之和。\n\n[samples]\n\n## Background\n\n>  _生活快得停不下来_\\\n_璀璨的也最终衰败_\\\n_他感到负荷已过载_\\\n_车窗外_\\\n_天上大朵云彩_\\\n_追随他的速度跑得飞快_\\\n_不由自主比赛_\\\n——《笨小孩的道歉信》\n\n不管多少个日夜，为你一直唱。\n\n## Note\n\n|  Subtask |  数据范围  | 分值 |\n|:----:|:----:|:----:|\n| Subtask 1 | $T=1$，$k< 2^{25}$ | $20$ |\n| Subtask 2 | $T\\leq 5$，$k< 2^{48}$ | $30$ |\n| Subtask 3 | $T\\leq 10^6$，$k < 2^{48}$ | $40$ |\n| Subtask 4 | $T\\leq 3\\times 10^6$，$k < 2^{64}$ | $10$ |\n\n**请注意常数因子对程序效率的影响。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9396","tags":["数学","O2优化"],"sample_group":[["1 114514 1919810 19950501 5","35"],["5 231421 523434 31243 5","50\n30\n40\n55\n35"]],"created_at":"2026-03-03 11:09:25"}}