Description

给定\(f(i)\),求\(g(i)=\sum_{i_1|i}\sum_{i_2|i_1}\dots\sum_{i_k|i_{k-1}}f(i_k)(mod\;10^9+7)\).

HINT

\(n,k\leq10^5\)

Solution

30分

\(f[i][j]\)表示选了\(i\)个数,积为\(j\)的总和.

#include
#include
#include
#include
#include
#include
#include
#include
#define K 10000
#define N 100001
#define T 300000
#define M 1000000007
using namespace std;
typedef long long ll;
int f[2][N],n,m,k;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+c-'0';c=getchar();}
    return ret;
}
inline int rd(){
    int ret=0ll;bool f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+c-'0';c=getchar();}
    if(f) return ret;
    return M-ret;
}
inline void Aireen(){
    m=read();
    while(m--){
        n=read();k=read();
        for(int i=1;i<=n;++i) f[0][i]=rd();
        for(int i=1;i<=k;++i){
            for(int j=1;j<=n;++j){
                f[i&1][j]=0;
                for(int l=sqrt(j);l;--l){
                    if(!(j%l)){
                        f[i&1][j]+=f[i&1^1][l];
                        if(f[i&1][j]>M) f[i&1][j]-=M;
                        if(l*l!=j) f[i&1][j]+=f[i&1^1][j/l];
                        if(f[i&1][j]>M) f[i&1][j]-=M;
                    }
                }
            }
        }
        for(int i=1;i<=n;++i)
            printf("%d ",f[k&1][i]);
        putchar('\n');
    }
}
int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
} 

100分

inline void sieve(){
    cnt=0;t[1]=1;
    for(int i=1;i<=n;++i) g[i]=0;
    for(int i=2;i<=n;++i){
        if(!g[i]){
            g[i]=i,p[++cnt]=i,t[i]=k;
        }
        for(int j=1,l,q,c,x;j<=cnt&&i*p[j]<=n;++j){
            g[c=i*p[j]]=p[j];
            if(mul[c]) t[c]=C(mul[c]+k-1,k-1); 
            else{
                q=c;t[c]=1;
                while(q>1){
                    x=l=g[q];
                    while(true){
                        if(1ll*x*l>1ll*q||q%(x*l)) break;
                        x=x*l;
                    }
                    q/=x;
                    t[c]=1ll*t[c]*t[x]%M; 
                }
            }
            if(!(i%p[j])) break;
        }
    }
}

相当于求每个数分解\(k\)次得到的可重\(i\)的\(f(i)\)之和.
实际上\(g(i)\)与\(f(j)\;(i|j)\)之间的关系是只与\(k\)有关的.
设\(g(i)=t(\frac{i}{j})\times{f(j)}\).
\(t(x)=\begin{cases}1&x=1\\k&x\;is\;prime\\C_{j+k-1}^{k-1}(隔板法)&x=p_i^j\\ \prod_{i=1}^{k}{t(p_k^{a_k})}&x=p_1^{a_1}\;\times\;p_2^{a_2}\;\times\dots\times\;p_k^{a_k}\\\end{cases}\)
上面的式子很好理解,也很好证明,也就是运用了积性函数,隔板法,乘法原理的思想.
至此,问题求解.

#include
#include
#include
#include
#include
#include
#include
#include
#define K 10000
#define N 100001
#define T 200001
#define M 1000000007
using namespace std;
typedef long long ll;
int f[N],g[N],p[K],t[N],mul[N],fac[T],rev[T],n,m,k,cnt,ans;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+c-'0';c=getchar();}
    return ret;
}
inline int po(int x,int k){
    int ret=1;
    while(k){
        if(k&1) ret=1ll*ret*x%M;
        x=1ll*x*x%M;k>>=1;
    }
    return ret;
}
inline ll C(int n,int m){
    return 1ll*fac[n]*rev[n-m]%M*rev[m]%M;
}
inline int chk(int k){
    int l=g[k],ret=0;
    while(k>1){
        if(k%l) return 0;
        k/=l;++ret;
    }
    return ret;
}
inline void prime(){
    for(int i=2;i1){
                    x=l=g[q];
                    while(true){
                        if(1ll*x*l>1ll*q||q%(x*l)) break;
                        x=x*l;
                    }
                    q/=x;
                    t[c]=1ll*t[c]*t[x]%M; 
                }
            }
            if(!(i%p[j])) break;
        }
    }
}
inline void Aireen(){
    fac[0]=fac[1]=1;
    for(int i=2;i1;--i)
        rev[i]=1ll*rev[i+1]*(i+1)%M;
    prime();
    m=read();
    while(m--){
        n=read();k=read();
        for(int i=1;i<=n;++i) f[i]=read();
        sieve();
        for(int i=1;i<=n;++i) g[i]=0;
        for(int i=1;i<=n;++i)
            for(int j=i;j<=n;j+=i){
                g[j]+=1ll*t[j/i]*f[i]%M;
                if(g[j]>M) g[j]-=M;
            }
        for(int i=1;i<=n;++i)
            printf("%d ",g[i]);
        putchar('\n');
    }
}
int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
} 

2017-04-05 22:54:41