题目 | 雪菜的式子

武汉大学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}}^{\ast })$.

$$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{array}{ll}1,& \mathrm{若}n=1\\ (-1{)}^k,& \mathrm{若}n=p_1{p}_2\dots p_k,p_i\mathrm{为}\mathrm{不}\mathrm{同}\mathrm{的}\mathrm{质}\mathrm{数}\\ 0,& \mathrm{若}n\mathrm{有}\mathrm{大}\mathrm{于}1\mathrm{的}\mathrm{平}\mathrm{方}\mathrm{数}\mathrm{因}\mathrm{数}\end{array}$$

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

输入

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

输出

一个整数表示答案。

样例

输入

2 2

输出

1

题解

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

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

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

因此，拆分结果每种质数的幂次不能 $>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$ 种安排方式
• $⋮$
• 若 $\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{array}{rl}& \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{array}$$

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

需要注意的是，不要将 $-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;
}