武汉大学2023年新生程序设计竞赛

H - 雪菜的式子

https://ac.nowcoder.com/acm/contest/66651/H

1s / 512MB

题目

雪菜定义 $S(n)$ 为前 $n$ 个质数任意幂次方相乘和 $1$ 构成的集合，例如 $S(2)=\{1,2^a,3^b,2^a\times 3^b\}(a,b\in\mathbb{N}^*)$.

$$ f(n)=\sum_{a_1\in S(n)}\sum_{a_2\in S(n)}\cdots\sum_{a_k\in S(n)}\mu\left(\prod_{i=1}^k a_i\right) $$

其中 $\mu$ 为莫比乌斯函数。

$$ \mu(n)=\begin{cases} 1,&若\;n=1\\ (-1)^k,&若\;n=p_1p_2\dots p_k,\;p_i\;为不同的质数\\ 0,&若\;n\;有大于\;1\;的平方数因数 \end{cases} $$

给定 $n,k$，求 $f(n)$，答案对 $998244353$ 取模。

输入

第一行两个数 $n,k$ $(1\leq n,k <998244353)$

输出

一个整数表示答案。

样例

输入

2 2

输出

1

题解

本题需要将原问题转化一下，转化后的问题就很好求解了。

首先要对 $\mu(n)$ 做一下转换，该函数的描述可以变成：

$$ \mu(n)=\begin{cases} (-1)^k,&n\;可拆成\;k\;个互不相同的质数相乘,\;1\;看作拆成\;0\;个\\ 0,&其他情况 \end{cases} $$

因此，拆分结果每种质数的幂次不能 $>1$，否则 $\mu(n)$ 直接变成 $0$，这一项就不考虑了。

接下来，就可以对不同的 $\mu(x)$ 进行分类讨论了：

  • 若 $\mu(x)=(-1)^0$，$x$ 包含 $0$ 种质数，选法 $C_{n}^{0}$，这 $0$ 个质数分给 $a_1\sim a_k$ 组合，有 $k^0$ 种安排方式
  • 若 $\mu(x)=(-1)^1$，$x$ 包含 $1$ 种质数，选法 $C_{n}^{1}$，这 $1$ 个质数分给 $a_1\sim a_k$ 组合，有 $k^1$ 种安排方式
  • 若 $\mu(x)=(-1)^2$，$x$ 包含 $2$ 种质数，选法 $C_{n}^{2}$，这 $2$ 个质数分给 $a_1\sim a_k$ 组合，有 $k^2$ 种安排方式
  • $\vdots$
  • 若 $\mu(x)=(-1)^n$，$x$ 包含 $n$ 种质数，选法 $C_{n}^{n}$，这 $n$ 个质数分给 $a_1\sim a_k$ 组合，有 $k^n$ 种安排方式

那么，最终答案便是：

$$ \sum_{i=0}^{n}C_n^i\cdot k^i\cdot(-1)^i $$

根据二项式定理：

$$ (a+b)^n=\sum_{i=0}^n C_n^i\cdot a^i\cdot b^{n-i} $$

原式可以变形：

$$ \begin{align} &\sum_{i=0}^{n}C_n^i\cdot k^i\cdot(-1)^i\\ =&(-1)^{2i-n}\sum_{i=0}^{n}C_n^i\cdot k^i\cdot(-1)^{n-i}\\ =&(-1)^n(k-1)^n \end{align} $$

最后，使用快速幂即可解决。

需要注意的是，不要将 $-1$ 和 $k-1$ 并到一起再用快速幂，负数不能用快速幂。

另外取模时，需要注意正负性。

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int MOD = 998244353;

int qpow(int a, int b)
{
    int ans = 1;
    a %= MOD;
    while (b)
    {
        if (b % 2)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b /= 2;
    }
    return ans;
}

void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = qpow(k - 1, n);
    if (n % 2)
        ans *= -1;
    ans = (ans % MOD + MOD) % MOD;
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}