题解：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)

的，剪掉没用状态就能过，但是空间消耗会比较大。

CPP

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;
}
/*

*/

题解：P6274 [eJOI 2017] 六

文章操作

前言

Solution

相关推荐

评论

题解：P6274 [eJOI 2017] 六