出题人我谢谢你
前置知识：Floyd 判环，分段打表
看到题目中给出的这个奇怪的线性递推式就可以猜测没有什么简单的性质可以入手了，因此容易想到去打表求循环节长度。直接用 umap 存所有出现过的数肯定是不行的，于是考虑使用 Floyd 判环，在 的空间复杂度内求得循环节长度为 ，在第 位开始进入循环节。
这里简要的介绍一下 Floyd 判环算法（这个好像挺冷门的）：考虑维护两个指针 ，初始两个指针都指向 。
第一步让指针 每次从 移动到 ，让指针 每次从 移动到 ，直到 为止。
然后让 指针回到 位置，然后每次操作让 每次从 移动到 ，让 每次从 移动到 ，直到 为止。
最后只移动 指针，直到 条件再次成立为止。容易证明最后一步 指针移动的次数就是循环节的最小长度。
:::success[打表代码]
namespace Loyalty
{
inline void init() {}
inline int solve(int x) { return (x + (x >> 20) + 12345) % (1ll << 40); }
inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc)
{
const int S0 = 0x600DCAFE;
int p1 = S0, p2 = S0;
do { p1 = solve(p1), p2 = solve(solve(p2)); } while (p1 != p2);
p1 = S0; do { p1 = solve(p1), p2 = solve(p2); } while (p1 != p2);
int cnt = 0; do { p2 = solve(p2), ++cnt; } while (p1 != p2);
cout << "QwQ " << cnt << '\n'; cnt = 0;
p1 = S0; while (p1 != p2) { ++cnt, p1 = solve(p1); }
cout << "AwA " << cnt << '\n';
}
} // namespace Loyalty:::
然后注意到这个 序列是一直不变的，所以考虑直接 处理完整循环节部分，然后对序列进入循环节之前的开头部分和不完整的循环节前缀求和部分直接分段打表处理，然后做完了。
不知道有没有不用分段打表的做法，感觉应该是没有的（）
namespace Loyalty
{
int buc[N];
inline void init() {}
inline int solve(int x) { return (x + (x >> 20) + 12345) % (1ll << 40); }
int buc_val[] = {1611516670, 14370630249, 38312556854, 83248007737, 167560289742, 325792323073, 622741727028, 937685173, 13107744445, 35943646365, 78802032994, 159235062884, 310147760736, 593348380684, 295498034, 11901289737, 33681877906, 74557367833, 151258698876, 295206930517, 565345893787, 1072246754882, 10752858133, 31526697331, 70512631458, 143677078963, 280954761586, 538598461112, 1022070324749, 9655697881, 29466792348, 66642984633, 136417233148, 267368060404, 513107125545, 974225187667, };
int buc_pre[] = {0, 5004364, 10006017, 15011683, 20012408, 25031296, 30040232, 35042602, 40042828, 45056959, 50056831, 55056278, 60057168, 65062411, 70077204, 75074286, 80089334, 85076566, 90060817, 95067617, 100089173, 105080524, 110081437, 115071718, 120091493, 125100277, 130104566, 135114812, 140110603, 145118771, 150119937, 155117508, 160106698, 165108248, 170101751, 175085228, };
int circ_val[] = {516914, 11347508705, 32642538921, 72602179030, 147587596515, 288299158592, 552368730897, 1047889963499, 10220465107, 30528085091, 68635277779, 140147868236, 274358548202, 526208585828, 998852854893, 9149398605, 28517124738, 64866088952, 133077482701, };
int circ_pre[] = {1, 4989280, 9983340, 14984747, 19988258, 24980217, 29971111, 34971436, 39962817, 44967154, 49973217, 54964749, 59985791, 64989688, 69988721, 74980113, 79977391, 84979858, 89965024, };
int circ_all = 91029304;
inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc)
{
int n;
cin >> n;
if (!n) { cout << 0 << '\n'; return; }
--n;
int pre = min(350125309ll, n), x = buc_val[pre / 10000000];
int cnt = buc_pre[pre / 10000000] + (~x & 1);
for (int i = pre / 10000000 * 10000000 + 1; i <= pre; ++i)
cnt += ~(x = solve(x)) & 1;
if (n > 350125309ll)
{
n -= 350125310ll;
int circ = n / 182129209;
cnt += circ * circ_all;
n %= 182129209;
pre = n / 10000000;
cnt += circ_pre[pre], x = circ_val[pre];
for (int i = 1; i <= n % 10000000; ++i)
cnt += ~(x = solve(x)) & 1;
}
cout << cnt << '\n';
}
} // namespace Loyalty
喜欢的话，留下你的评论吧～