标签：Training le rs int sum Records ls dp

9.6

*B

题目描述

小诗有一个不可重集 $S$ ，她记得 $S$ 的元素数量 $n$ 与 $\gcd⁡(S)+\operatorname{lcm}⁡(S)$ 的值 $m$ ，但她已经忘记 $S$ 由什么元素构成，她想知道有多少种符合条件的构成方案。由于答案过大，你只需告诉她答案 $\bmod P$ 的值。

对于所有测试点，$1\le n,m \le 10^9,10^8 \le P \le 10^9+7$，保证 $P$ 为素数。

赛时读错题，读成 $n$ 按位与 $\gcd(S)+\operatorname{lcm}(S)$ 的值为 $m$。

枚举 $\gcd$ 设为 $g$，$g \mid m$。可以计算出 $\operatorname{lcm}$，设为 $l$。

将 $g,l$ 分解质因数，$g=\sum p_i^{k_{1,i}}, l = \sum p_i^{k_{2,i}}$。设对于集合中元素 $a_x$ 分解质因数为 $a_x\sum p_i^{t_{x,i}}$。可知

\[\begin{aligned} k_{1,i} &= \min_{x=1}^{n} t_{x,i}\\ k_{2,i} &= \max_{x=1}^{n} t_{x,i} \end{aligned} \]

对于集合中的每个数分解质因子后，每个质因子都有出现次数的上下界。每个质因子出现次数的上下界都至少在一个数中出现过。

容斥解决这个问题。设 $k_i = k_{2,i} - k_{1,i}$。对于每个质因子枚举是否卡上下界，共 $4^{w(l)}$ 种状态。对于上下界都没有限制的情况，其贡献为

\[{\prod(k_i+1) \choose n} \]

虽然 $n$ 很大，但是 $\prod(k_i+1)$ 很小，组合数可以计算。

设 $c$ 为这个状态下为每个质因子上下界限制次数的和。例如钦定不能选择上界，则对 $c$ 贡献 $1$；钦定上下界都不能选，则对 $c$ 贡献 $2$。容斥系数是 $(-1)^c$。

发现可以 $3^{w(l)}$ 枚举状态，为限制了多少个上下界。设枚举的状态有 $s$ 个质因子限制了 $1$ 个上界或下界。则当前状态的贡献乘 $2^s$。

代码

#include <cstdio>
#include <algorithm>

#define int long long

using namespace std;

const int N = 1000005;

int n, m, ans, mod, cnt, t[20], P[20], fac[N], inv[N], ifa[N];

int C(int x, int y)
{
    if(y > x)
        return 0;
    return fac[x] * ifa[y] % mod * ifa[x - y] % mod;
}

void solve(int x)
{
    cnt = 0;
    for(int i = 2; i * i <= x; ++ i)
    {
        if(x % i == 0)
            t[++ cnt] = 1;
        while(x % i == 0)
            x /= i, t[cnt] ++;
    }
    if(x != 1)
        t[++ cnt] = 2;

    int res = 0;
    for(int i = 0; i < P[cnt]; ++ i)
    {
        int a = 0, b = 0, c = 0, w = 1;
        for(int j = 1; j <= cnt; ++ j)
        {
            int o = i / P[j - 1] % 3;
            if(o == 0)
                ++ a, w *= t[j];
            else if(o == 1)
                ++ b, w *= t[j] - 1;
            else
                ++ c, w *= t[j] - 2;
        }
        if(b & 1)
            res = (res - C(w, n) * (1 << b) % mod + mod) % mod;
        else
            res = (res + C(w, n) * (1 << b)) % mod;
    }
    ans = (ans + res) % mod;
}

signed main()
{
    scanf("%lld%lld%lld", &n, &m, &mod);

    P[0] = fac[0] = inv[0] = inv[1] = ifa[0] = ifa[1] = 1;
    for(int i = 1; i <= 10; ++ i)
        P[i] = P[i - 1] * 3;
    for(int i = 1; i <= 1e6; ++ i)
        fac[i] = fac[i - 1] * i % mod;
    for(int i = 2; i <= 1e6; ++ i)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 2; i <= 1e6; ++ i)
        ifa[i] = ifa[i - 1] * inv[i] % mod;

    for(int i = 1; i * i <= m; ++ i)
    {
        if(m % i)
            continue;
        int A = i, B = m - i;
        if(B >= A && B % A == 0)
            solve(B / A);
        if(i * i == m)
            continue;
        A = m / i, B = m - A;
        if(B >= A && B % A == 0)
            solve(B / A);
    }
    printf("%lld\n", ans);

    return 0;
}

可以使用莫反。

设 $f(k)$ 表示 $\gcd = 1,\operatorname{lcm} = k$ 的 $S$ 的个数。$g(k)$ 表示 $\gcd = 1,\operatorname{lcm} \mid k$ 的 $S$ 的个数。

根据转化可知，枚举 $\gcd$ 后，答案为 $f(\dfrac {m - g} g)$。

根据莫反得到：

\[\begin{aligned} g(k) &= \sum_{i \mid k} f(i)\\ f(k) &= \sum_{i \mid k} g(i) \mu(\frac k i) \end{aligned} \]

现在需要求 $g$。

\[\begin{aligned} g(k) =& \sum_{\forall x \in S,x \mid k} [\gcd_{x \in S} x = 1]\\ =& \sum_{d \mid k} \mu(d) \sum_{\forall x \in S, x \mid k, d \mid x} 1\\ =& \sum_{d \mid k} \mu(d) {\sum_x[x \mid \frac k d] \choose n} \end{aligned} \]

设 $h(k) = {\sum_x[x \mid k] \choose n} = {\sigma_0(k) \choose n}$，则 $g = \mu * h,f = \mu * \mu * h$。$\mu * \mu$ 是积性函数，可以直接计算。最后卷起来即可。

Training Records 2

9.6

*B

*C

D

9.7

*B

C

*D

9.14

A

B

*C

9.20

*B

C

9.23

C

D

9.24

A

*C

*D

9.25

A

*B

**C

D

9.27

A

B

C

D

杂

9.28

A

B

*D

相关文章

赞助商

阅读排行