HDU-5628 Clarke and math

HDU-5628 Clarke and math

• 
  .

• 

  #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]);
    }
  }

• 
  
  
  
  
• 

  #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]);
    }  
  }