[ICPC2019西安C] Dirichlet k-th root

[ICPC2019西安C] Dirichlet k-th root - 结论

给定函数 f，求它关于 Dirichlet 卷积的 k 次方根 g，函数用点值表示。

Description

给定函数 f，求它关于 Dirichlet 卷积的 k 次方根 g，函数用点值表示。

Solution

Dirichlet 卷积有个很好的性质，n 次方根等于 n 逆元次方（卷积，模意义下）

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 998244353;

int n, k;

int qpow(int p, int q)
{
    return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
}

int inv(int p)
{
    return qpow(p, mod - 2);
}

vector<int> operator*(const vector<int> &a, const vector<int> &b)
{
    vector<int> ans(a.size());
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 0)
            continue;
        for (int j = 1; j * i <= n; j++)
        {
            if (b[j] == 0)
                continue;
            ans[i * j] += a[i] * b[j];
            ans[i * j] %= mod;
        }
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
    vector<int> g(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> g[i];
    k = inv(k);
    vector<int> ans(n + 2), bas(n + 2);
    bas = g;
    ans[1] = 1;
    while (k)
    {
        if (k & 1)
            ans = ans * bas;
        bas = bas * bas;
        k /= 2;
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
}