loj#P6702. 「hyOI2019」henry_y 的莫比乌斯函数

「hyOI2019」henry_y 的莫比乌斯函数

题目描述

Tsukimaru 要给自己的比赛出一道签到题。简单来说,这道题只需要选手使用线性筛筛出 μ(1),μ(2),,μ(m)\mu(1), \mu(2), \ldots, \mu(m),然后暴力求和即可。

为了防止选手用优于暴力做法的做法碾压正解,导致选手浪费多余的时间,Tsukimaru 给题目增加了一个随机数生成器,以使得除了暴力没有别的做法。

定义函数 f(k, seed)

unsigned f(unsigned k, unsigned seed) {
    if (k == 0)
        return 1;

    unsigned t;
    unsigned ans = 0;

    for (t = 1; t <= n; t++) {
        ans += absmu(seed % m + 1) * ~seed * f(k - 1, (seed >> 16) | (seed << 16));
        seed ^= seed << 16;
        seed ^= seed >> 5;
        seed ^= seed << 1;
    }

    return ans;
}

其中 absmu(p)=μ(p)\text{absmu}(p) = |\mu(p)|。该函数满足:

  • 若存在大于 11 的整数 xx 使得 x2x^2pp 的因子,则 absmu(p)=0\text{absmu}(p) = 0
  • 否则 absmu(p)=1\text{absmu}(p) = 1

给出 n,m,xn, m, x,请你求出 f(6, x) 的值。


Tsukimaru 想出了一个 O(n6m)O(n^6 \sqrt m) 的优秀解法。Tsukimaru 相信没有更优的做法了,于是,他高兴地、蹦蹦跳跳地去找

https://loj.ac/user/6189

Tsukimaru:帮我验一下这道题
henry_y:好
henry_y:这个可以加强到 n=25,m=107n = 25, m = 10^7
Tsukimaru:?

Tsukimaru 认为 henry_y 可以直接 A 掉这道题。

henry_y 说:「黑的实在逼真 =.=,你起码把时限开到每个测试点 1500 ms1500\ \text{ms} 吧。」

Tsukimaru 觉得 henry_y 说的有道理,于是想让你帮他求 f(6, x) 的结果。

输入格式

只有一行,三个正整数 n,m,xn, m, x

输出格式

只有一行,一个非负整数,表示答案。

4 5 19260817
509600808

数据范围与提示

对于 30%30\% 的数据,1n15,1m10001 \leq n \leq 15, 1 \leq m \leq 1000

另外 70%70\% 的数据,1n25,5×106m1071 \leq n \leq 25, 5 \times 10^6 \leq m \leq 10^7

对于 100%100\% 的数据,1x1091 \leq x \leq 10^9

欢迎 Hack。如果你发现了可以让标程运行超时的数据,可以在题目讨论提出。

提醒:如果你希望提出 Hack 数据,请认真检查输入数据中 n,mn, m 的范围是否合法。如果你输入的 n>15n > 15,那么 mm 必须不小于 5×1065 \times 10^6

来自 Tsukimaru 的善意提醒:

  • 函数中的所有变量和函数返回值的类型都是 unsigned;这意味着函数中的所有计算都会自动对 2322^{32} 取模。
  • 请注意常数因子给程序运行时间带来的影响。

题目信息

  • Idea / Std / Data:
    https://loj.ac/user/1408
  • Solution:
    https://loj.ac/user/3560
  • Testing:
    https://loj.ac/user/10399