HDU-5628 Clarke and math

$Description$
图片说明

$Solution$
$g(n)=(f\cdot u^k)(n)$

$idea \; 1$
$u^l\cdot u^r=u^{l+r},\cdot 是狄利克雷卷积运算,可以用快速幂进行优化$ .

$Code\; 1$

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e5+5;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=x*(a/b);}
int n,k;
ll f[N];
ll g[N],h[N];
ll x[N];
void DT(ll *a,ll *b){
  for(int i=1;i<=n;i++)x[i]=0;
  for(int i=1;i<=n;i++){
      for(int j=i;j<=n;j+=i){
          x[j]+=a[i]*b[j/i]%mod;
          if(x[j]>=mod)x[j]-=mod;
      }
  }
  for(int i=1;i<=n;i++)a[i]=x[i];
}
void ksm(){
  while(k){
      if(k&1)DT(h,g);
      k>>=1;
      DT(g,g);
  }
}
int main(){
  int t;cin>>t;
  while(t--){
      sc("%d%d",&n,&k);
      for(int i=1;i<=n;i++)sc("%lld",&f[i]),g[i]=1,h[i]=0;
      h[1]=1;
      ksm();
      DT(f,h);
      for(int i=1;i<=n;i++)printf("%lld%c",f[i]," \n"[i==n]);
  }
}

$idea \; 2$
$令h(n)=u^k(n),g(n)=\sum_{d|n}f(d)\cdot h(\frac{n}{d})$
$显然h(n)为积性函数 \color{red}{h_(n)=\sum_{i_1\cdot i_2\cdot ..i_k=n}1=\prod_{p^a||n}h(p^a)},只需要求出\color{blue}{h(p^a)}即可.$
$\color{purple}{h_(p^a)=\sum_{i_1\cdot i_2\cdot ..i_k=p^a}1=\sum_{p^{x_1}\cdot p^{x_2} \cdot ..p^{x_k}=p^a}1}$
$\color{darkblue}{问题等价于求x_1+x_2+..x_k=a的划分方法数},采用隔板法可以得到\color{purple}{h(p^a)=\binom{a+k-1}{a}}$

$Code\; 2$

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=1e5+1775;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
ll inv[N],inv_fac[N],fac[N];
int prime[N],tot=0;
bool vis[N];
ll f[N],h[N],g[N];
ll C(int n,int m){
  return fac[n]*inv_fac[n-m]%mod*inv_fac[m]%mod;
}
void pre(){
  inv[0]=inv[1]=inv_fac[0]=fac[0]=1;
  for(int i=2;i<N;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
  for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
  for(int i=1;i<N;i++) inv_fac[i]=inv_fac[i-1]*inv[i]%mod;
  for(int i=2;i<N;i++){
      if(!vis[i])prime[++tot]=i;
      for(int j=1;j<=tot&&i*prime[j]<N;j++){
          vis[i*prime[j]]=1;
          if(i%prime[j]==0)break;
      }
  }
}
int main(){
  pre();
  int t;cin>>t;
  while(t--){
      int  n,k;
      sc("%d%d",&n,&k);
      for(int i=1;i<=n;i++)sc("%lld",&f[i]),h[i]=1,g[i]=0;
      for(int i=1;i<=tot&&prime[i]<=n;i++){
          for(int j=prime[i];j<=n;j+=prime[i]){
              int m=j;
              int a=0;
              while(m%prime[i]==0)m/=prime[i],a++;
              h[j]*=C(a+k-1,a);
              if(h[j]>=mod)h[j]-=h[j]/mod*mod;
          }
      }
      for(int i=1;i<=n;i++){
          for(int j=i;j<=n;j+=i){
              if(k==1){
                  g[j]+=f[i];
                  if(g[j]>=mod)g[j]%=mod;
                  continue;
              }
              g[j]+=f[i]*h[j/i]%mod;
              if(g[j]>=mod)g[j]%=mod;
          }
      }
      for(int i=1;i<=n;i++)printf("%lld%c",g[i]," \n"[i==n]);
  }  
}