bzoj E. Bash Plays with Functions

题意:

设$f_{0,n}=$将n分成两个互质的数的积的方案数。
$f_{r,n}=sum_frac{f_{r-1,u}+f_{r-1,v}}{2}(uv=n)$
多组询问，每次给出$r,n$，求$f_{r,n}$对$10^9+7$取模。

题解：

今天男神出给我们做，因为太菜，考场口胡没时间写。
显然$f_{0,n}=2^{num},num$为n的不同质因子个数。
考虑$f_{r,n}$的意义，显然可以枚举n的因数，那么他对答案最终的贡献就是，将该因数每一次乘一个数，在r次内变成n的方案数，所以可以枚举因数+组合数算贡献。这种做法在cf上T了。但过了男神数据。
%栋老师写法，发现没有必要枚举因数，只需要对每个不同质因数单独算出贡献，最后乘起来即可。具体代码，上面两种都给出来。
code：（TLE）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const LL mod=1e9+7;
bool v[1000010];
int prime[1000010],pr=0,r,n;
LL bin[1000010],f[1000010],F[2000010],inv[2000010];
LL C(int m,int n)
{
    if(n>m) return 0;
    return F[m]*inv[m-n]%mod*inv[n]%mod;
}
void pre()
{
    memset(v,true,sizeof(v));
    F[0]=F[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=2000000;i++) F[i]=F[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=2000000;i++) inv[i]=inv[i-1]*inv[i]%mod;
    for(int i=2;i<=1000000;i++)
    {
        if(v[i]) prime[++pr]=i,f[i]=1;
        for(int j=1;j<=pr&&i*prime[j]<=1000000;j++)
        {
            v[i*prime[j]]=false;
            if(i%prime[j]==0) {f[i*prime[j]]=f[i];break;}
            f[i*prime[j]]=f[i]+1;
        }
    }
    bin[0]=1;for(int i=1;i<=1000000;i++) bin[i]=bin[i-1]*2%mod;
    for(int i=1;i<=1000000;i++) f[i]=bin[f[i]];
}
LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node{
    int a,num;
}a[25];int num;
void dec(int x)
{
    num=0;memset(a,0,sizeof(a));
    for(int i=1;prime[i]*prime[i]<=x;i++)
        if(x%prime[i]==0)
        {
            a[++num].a=prime[i];
            while(x%prime[i]==0) x/=prime[i],a[num].num++;
        }
    if(x!=1) a[++num].a=x,a[num].num=1;
}
LL ans=0;
void dfs(int x,int s,LL t)
{
    if(x>num) {ans=(ans+f[s]*t%mod)%mod;return;}
    for(int i=0;i<=a[x].num;i++)
    {
        dfs(x+1,s,t*C(r+a[x].num-i-1,r-1)%mod);
        s*=a[x].a;
    }
}
int main()
{
    pre();
    int T=read();
    while(T--)
    {
        r=read();n=read();
        if(r==0) {printf("%lldn",f[n]);continue;}
        dec(n);
        ans=0;dfs(1,1,1LL);
        printf("%lldn",ans);
    }
}

AC：

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1e9
using namespace std;

inline void read(int &x)
{
    char c; while(!((c=getchar())>='0'&&c<='9'));
    x=c-'0';
    while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0';
}
const int maxn = 1010000;
const int mod = 1e9+7;
inline void add(int &a,const int &b){a+=b;if(a>=mod)a-=mod;}

int pw(int x,int k)
{
    int re=1;
    for(;k;k>>=1,x=(ll)x*x%mod) if(k&1)
        re=(ll)re*x%mod;
    return re;
}
int inv(int x){return pw(x,mod-2);}

int p[maxn],pri,mp[maxn],pn[maxn];
int r0[maxn];
int s[maxn],invs[maxn];
void pre()
{
    r0[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!mp[i]) p[++pri]=i,mp[i]=i,pn[i]=1;
        for(int j=1,k=p[j]*i;k<maxn;j++,k=p[j]*i)
        {
            mp[k]=p[j];
            if(i%p[j]==0) { pn[k]=pn[i]; break; }
            pn[k]=pn[i]+1;
        }
        r0[i]=(1ll<<pn[i])%mod;
    }

    s[0]=1; for(int i=1;i<maxn;i++) s[i]=(ll)s[i-1]*i%mod;
    invs[maxn-1]=inv(s[maxn-1]);
    for(int i=maxn-2;i>=0;i--) invs[i]=(ll)invs[i+1]*(i+1)%mod;
}
int C(const int n,const int m){return (ll)s[n]*invs[m]%mod*invs[n-m]%mod;}

int t[maxn],tp,tu[maxn];
int m,n;
int solve()
{
    int re=1;
    for(int i=1;i<=tp;i++)
    {
        int tmp=0;
        for(int j=0;j<=t[i];j++)
        {
            int now=!j?1:2;
            if(j<t[i]) now=(ll)now*C(t[i]-j+1+r-2,r-1)%mod;
            add(tmp,now);
        }
        re=(ll)re*tmp%mod;
    }
    return re;
}

int main()
{
    pre();
    read(m);
    while(m--)
    {
        read(r),read(n);
        if(n<=0) { puts("0");continue; }
        if(!r) { printf("%dn",r0[n]); continue; }
        if(n==1) { puts("1"); continue; }
        tp=0; int tmp=n;
        while(tmp>1)
        {
            int pi=mp[tmp]; t[++tp]=0;
            while(mp[tmp]==pi) tmp/=pi,t[tp]++;
        }
        printf("%dn",solve());
    }

    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!