题目大意:
文章图片
给定f（1~n），求g(1~n)
【狄利克雷卷积 【HDU5628】Clarke and math】题目分析：（狄利克雷卷积）
狄利克雷卷积：
文章图片
狄利克雷卷积满足：交换律，结合律，分配率等性质（和乘法是一样的）。
我们设函数g(i)=1
如果k==1，则 i 的答案为： (f?g)(n)=∑d1|nf(d1)( f ? g ) ( n ) = ∑ d 1 | n f ( d 1 )
如果k==2，则 i 的答案为： ((f?g)?g)(n)=∑d1|n∑d2|d1f(d2)( ( f ? g ) ? g ) ( n ) = ∑ d 1 | n ∑ d 2 | d 1 f ( d 2 )
以此类推
则最终答案为 f?(gk)f ? ( g k )
所以只要求logk次狄利克雷卷积就可以了。
但是如果是枚举i，枚举i的约数，时间复杂度为n^2,明显接受不了。
所以我们直接枚举约数，然后枚举该约数和哪些数相乘。
这样时间复杂是nlogn的。
总时间复杂度O（nlognlogk）
代码如下：
#include
#define N 120000
using namespace std;
const int mod=1e9+7;
int T,n,k;
struct fun{
int a[N];
void make_f()
{
for(int i=1;
i<=n;
i++)
scanf("%d",&a[i]);
}
void make_g()
{
for(int i=1;
i<=n;
i++)
a[i]=1;
}
fun operator * (const fun &c) const
{
static fun z;
for(int i=1;
i<=n;
i++) z.a[i]=0;
for(int i=1;
i*i<=n;
i++)
for(int j=i;
j*i<=n;
j++)
{
z.a[i*j]+=1ll*a[i]*c.a[j]%mod,z.a[i*j]%=mod;
if(i!=j) z.a[i*j]+=1ll*a[j]*c.a[i]%mod,z.a[i*j]%=mod;
}
return z;
}
void print()
{
printf("%d",a[1]);
for(int i=2;
i<=n;
i++)
printf(" %d",a[i]);
printf("\n");
}
};
void Fast_Power(fun &ans,fun a,int k)
{
while(k)
{
if(k&1) ans=ans*a;
a=a*a;
k>>=1;
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
fun f,g;
f.make_f();
g.make_g();
Fast_Power(f,g,k);
f.print();
}
return 0;
}
