HDU 5628 Clarke and math （Dirichlet卷积）

骑猪看日落 2022-06-09 10:13 160阅读 0赞

题目链接：  
[HDU 5628][]

题意：  
给你f(i)。(i=1,2,…,n)  
求g(i)=∑i1∣i∑i2∣i1∑i3∣i2⋯∑ik∣ik−1f(ik) mod 1000000007(1≤i≤n)

题解：

h\[i\]恒等于 1.

#### g(i)=∑i1|i∑i2|i1∑i3|i2⋯∑ik|ik−1f(ik) ＝∑i1|i∑i2|i1∑i3|i2⋯∑ik|ik−1f(ik)∗h(ik). ####

化为 Dirichlet 卷积形式，g(i)=(f∗hk)(i)=∑d|if(i)hk(id)。  
根据 狄利克雷卷积 满足交换律和结合律， 先利用快速幂 hk。最后再拿hk的结果与f卷积（注意，两个函数卷积的结果是函数，而不是值）。  
每次 Dirichlet 卷积的 复杂度为 O(n∗logn),进行 logk 次卷积计算，总复杂度O(n∗logn∗logk)。

--------------------

嗯，感觉有点难解释。

就是两个函数 f和 g 的狄利克雷卷积定义为：(f⊗g)(n)=∑j|nf(j)g(nj)。

可以写成这样：(f⊗g)(n)=∑i×j=nf(j)g(i)。

然后可以发现原式的一层就是一次 f 函数和 1 函数的狄利克雷卷积。

又因为狄利克雷卷积满足交换律和结合律，所以g=f⊗1k （其中1函数满足 1(x)=1 ）。

然后快速幂套一个狄利克雷卷积就可以了。

总时间复杂度就是O(n∗logn∗logk)。

--------------------

但是刚才又想了一下。  
发现了一个nlogn的做法。

我们可以考虑 f(j) 对 g(i) 的贡献。

可以发现，g(i)=∑j|iH(ij)f(j),其中， H(i)表示把 i 分成 k 个有序数的乘积的方案数。

然后我们发现 H(i) 居然是积性的。

H(pr)=(k\+r−1r)，可以用线性筛预处理一下。

最后对于每一个 f(j) 枚举 j 的倍数 k ，对 g(k×j) 产生贡献。

总时间复杂度就是O(n∗logn)

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mod =1e9+7;
    int n,k;
    ll f[100010];
    ll ans[100010];
    ll tmp[100010],x[100010];
    void dirichlet(ll *ans, ll *x){
    
        memset(tmp,0,sizeof(tmp));
        for(int i=1;i*i<=n;i++)
        {
            tmp[i*i] += ans[i]*x[i]%mod; if(tmp[i*i]>=mod) tmp[i*i]%=mod;
            for(int j=i+1;i*j<=n;j++)
            {
                tmp[i*j] += ans[i]*x[j]%mod; if(tmp[i*j]>=mod) tmp[i*j]%=mod;
                tmp[i*j] += ans[j]*x[i]%mod; if(tmp[i*j]>=mod) tmp[i*j]%=mod;   
            } 
        }
        for(int i=1;i<=n;i++)
        {
            ans[i] = tmp[i];
        }
    }
    
    void qpower(){
    
        while(k)
        {
            if(k&1) dirichlet(ans,x);
            k>>=1;
            dirichlet(x,x); 
        }
        dirichlet(ans,f);//乘 f 
    } 
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&f[i]);
            ans[i] = 0;
            x[i] = 1;
        }
        ans[1] = 1;
        qpower();
    
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&k); 
            solve();
            for(int i=1;i<n;i++){
                printf("%lld ",ans[i]);
            }
            printf("%lld\n",ans[n]);
        }
        return 0;
    }

[HDU 5628]: http://acm.hdu.edu.cn/showproblem.php?pid=5628