题解：P6274 [eJOI 2017] 六

· · 题解

前言

题解区怎么全是记忆化搜索。

Solution

本人的思路比较搞笑，不需要记搜，但是需要写一坨，所以大家看看就好。

设 k 为质因数个数，首先我们不难想到把 2^k-1 个状态的出现情况全压一起 dp，但是状态数会爆，然后如果你没发现有用状态数很少的话那你就寄了。

考虑质因数个数最多只有 6 个，我们可以记录每个质因数的出现情况。

显然只要两个数的质因数集合有交，那么它们的 \gcd>1，于是我们直接处理所有 2^k-1 个状态的出现次数即可。

然后一个序列最多只会有 2k 个数，做 2k 次 dp 即可。

状态的话就是压 k 位，每一位表示 0/1/2/3/4/5/6/7，0 表示这个质因数没出现过，7 表示这个质因数出现了两次，1 到 6 表示出现一次的质因数的不同出现情况。

举个例子，设 n=2\times 3 \times 5 \times 7 \times 11 \times 13，初始的状态是：000000。此时我们加入 x=2\times 3 \times 5，状态变为 111000；然后加入 y=5\times 7 \times 11\times 13，此时仍然合法，状态为 117222，然后加入 z=3\times 5 \times 7，这个时候就不合法了，因为 z 与 x,y 都有公因子。

所以我们维护一个这样的过程即可，时间复杂度大约是 O(k16^k) 的，剪掉没用状态就能过，但是空间消耗会比较大。

ll c[8],tot=0;
ll n;

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;
}
ll a[128];
void dfs(int x,int y){
    if(x==tot){
        a[y]++;
        return;
    }
    For(i,0,c[x]) dfs(x+1,y+(i>0?(1<<x):0));
}
const ll mod=1e9+7;
ll f[13][1<<18];
int to[1<<18][64];
int t[8],t2[8];

int main()
{ 
    //freopen("six.in","r",stdin);
    //freopen("six.out","w",stdout);
    memset(to,-1,sizeof(to));
    n=read();
    For(i,2,sqrtl(n)){
        if(n%i==0){
            while(n%i==0) c[tot]++,n/=i;
            tot++;
        }
    }
    if(n>1) c[tot++]=1;
    dfs(0,0);
    For(i,0,(1<<(tot*3))-1){
        int now=i,i2=0,mx;
        short v=0;
        For(j,0,tot-1){
            t[j]=now%8,now/=8;
            if(t[j]==7) i2|=(1<<j);
        }
        For(j,1,(1<<tot)-1){
            if((j&i2)){
                continue;
            }
            now=v=0;
            mx=0;
            For(k,0,tot-1){
                if(t[k]!=0 && t[k]!=7){
                    mx=max(mx,t[k]);
                    if((j>>k)&1){
                        if(!now) now=t[k];
                        if(now!=t[k]){
                            v=1;
                            break;
                        }
                    }
                }
            }
            if(v) continue;
            now=0;
            For(k,0,tot-1){
                if((j>>k)&1){
                    if(!t[k]) t2[k]=mx+1;
                    else t2[k]=7;
                }else t2[k]=t[k];
            }
            Rof(k,tot-1,0) now=(now<<3)|t2[k];
            to[i][j]=now;
        }
    }
    f[0][0]=1;
    For(i,0,2*tot-1){
        For(j,0,(1<<(tot*3))-1){
            if(!f[i][j]) continue;
            For(k,1,(1<<tot)-1) if(to[j][k]!=-1) f[i+1][to[j][k]]=(f[i+1][to[j][k]]+f[i][j]*a[k]%mod)%mod;
        }
    }
    ll ans=0;
    For(i,1,2*tot){
        For(j,0,(1<<(tot*3))-1){
            ans=(ans+f[i][j])%mod;
            //cout<<f[i][j]<<' ';
        }
        //cout<<endl;
    }
    cout<<ans;
    return 0;
}
/*

*/