1. 题目

传送门= ̄ω ̄=

题意:

给定序列$f$,设:

$$\displaystyle g(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_k \mid i_{k-1}} f(i_k) \text{ mod } 1000000007 \quad (1 \le i \le n)$$

给定$n,k,1 \le n,k \le 10^5$,输出$g(i),1 \le i \le n$

有多组数据,数据组数小于等于5组

2. 题解

考场上遇到了这题然后别人都会就我不会。

我太蒻了

前两天boshi还刚发了一篇关于狄利克雷卷积的博客

可惜我没看

我就从来没考过做过的题

我太蒻了

好吧我们来看看这题怎么做

首先对于$k=1$的情况:

$$g(i)=\sum_{i_1\mid i}f(i_1)$$

有点像狄利克雷卷积不是吗?

我们再设这个函数:

$$f'(i)=1$$

那么:
$$g(i)=\sum_{d\mid i}f(d)\cdot f'(\frac{n}{d})$$

也就是说:
$$g=f*f’$$

这里“*”表示狄利克雷卷积

那如果$k=2$呢?

不难发现,我们把$k=1$时得到的$g$看做$f$,再做一次$g=f*f’$就得到了$k=2$时的$g$

也就是说:

$$g=f * f’ * f’ * f’…$$(乘了$k$次)

因为狄利克雷卷积符合交换律与结合律,所以式子可以写成$g=f*f’^k$,其中$f’^k$我们可以用快速幂来计算。

总复杂度就是$O(nlog_2nlog_2k)$的了(因为计算一次狄利克雷卷积复杂度是$O(nlog_2n)$的)

(但其实我的代码里还有一个分解因数,复杂度是$O(n\sqrt{n})$的)

具体看代码里面的注释吧

代码:

#include <bits/stdc++.h>

#define NS (100005)
#define MOD (1000000007)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int T, n, k;

LL tmp[NS];

vector<int> dn[NS];//存约数的动态长数组

struct Func
{
    LL v[NS];
    LL& operator [] (const int a) {return v[a];}
    void operator *= (Func oth)//计算狄利克雷卷积
    {
        memset(tmp, 0, sizeof(tmp));
        for (int i = 1; i <= n; i += 1)
            for (vector<int>::iterator it = dn[i].begin(); it != dn[i].end(); it++)
                tmp[i] = (tmp[i] + v[*it] * oth[i / *it] % MOD) % MOD;
        memmove(v, tmp, sizeof(v));
    }
}g, f, p;

void qpow(Func a, int b)//快速幂
{
    memset(p.v, 0, sizeof(p.v)), p[1] = 1;//先把p设为单位元,和普通快速幂里的1是一个意思
    while (b)
    {
        if (b & 1) p *= a;
        a *= a, b >>= 1;
    }
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), IN(k);
        for (int i = 1; i <= n; i += 1)//O(n sqrt(n))计算每个数字的约数
        {
            dn[i].clear();
            for (int j = 1; j * j <= i; j += 1)
                if (i % j == 0)
                {
                    dn[i].push_back(j);
                    if (i / j != j) dn[i].push_back(i / j);
                }
        }
        for (int i = 1; i <= n; i += 1) IN(g[i]), f[i] = 1;//这里f就是文中的f'
        qpow(f, k), g *= p;
        for (int i = 1; i < n; i += 1) printf("%lld ", g[i]);//这里还PE了一次=。=
        printf("%lld\n", g[n]);
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *