Lflame

【2016/1/21 考题】 Winedag's test 按根号分类

   题意:给定一个N ( N <= 3000) ,表示为1、2、3...N的序列,序列中每个元素可以选择删去,最后得到的分数为序列元素的乘积。求使得分数最大且为完全平方数的方案数。


    我们先将N!分解质因数,那么要删去质因数的即为指数为奇数的质因数,且只使得其指数减一(保证分数最大)。 接下来,我们发现这样的质因数并不多,并且指数为1的质因数不用考虑(因为只有一种选择),这样的话,可以跑一遍程序看到N<=3000时满足的质因数个数最多只有100个不到。

    那么状压DP就可得到40分了。即DP[i][j]表示现在枚举到第i个数(从1枚举到n),已经删去的质因数集合为j的方案数。答案即为DP[n][S]。空间有些不够,再滚动一下就好了。

    

    但是N<=3000时质因数最多有90个以上,状压DP妥妥挂掉。现在再想想这个DP,对于一个质因数,一定是在删去一个不超过N的数时删掉的。也就是说,对于一个大于根号N的质因数(简称大质因数),不会与其他大质因数同时被一个数删去。知道这个性质了,那么我们就可以将大小质因数分开考虑,对每个大质因数枚举与哪些小质因数同时被删去。

    也就是说,DP2[i][j]表示小质因数删去的状态为i,大质因数删到了第j个的方案数。初始值:DP2[i][0]就等于DP[n][i]。转移时就枚举第j个大质因数与哪些小质因数一起被删。每次选中一起被删的小质因数是小于等于4个的,并且总的小质因数是不超过16个(其实会更少)的,所以复杂度没有问题。


    反思一下这道题,既然全部存在状压状态里面会挂,那么我们考虑将大于根号的数提出来放到非状压状态里面,充分利用了大于根号的数的性质。


    

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#ifdef WIN32

#define my_LL "%I64d"

#else

#define my_LL "%lld"

#endif

using namespace std;


int read(int &x)

{

bool f=0; char t=getchar() ; x=0;

while(t<'0'||t>'9'){

if(t=='-')f=1;

if(t==EOF)return EOF ;

t=getchar() ;

}

while(t>='0'&&t<='9'){

x=(x<<1)+(x<<3)+t-'0' ;

t=getchar() ;

}

if(f)x=-x;

return 0 ;

}


int n;

int times[40005] ;

int q[40005] , qnum , bq[40005];

long long dp[78005][405] ;

long long t_dp[2][78005] ;//先跑出小质数的答案

int fac[40005] , fnum , s_xh[40005] ;

bool has[40005] , big[40005] ;

int bnum , b_xh[40005];


bool divi_it(int a)

{

int t=a ; fnum=0 ;

for(int i=2;i*i<=a;++i){

while(t%i==0){

t/=i ;

fac[++fnum]=i ;

if(fnum>1 && fac[fnum]==fac[fnum-1])return false ;

}

}

if(t>1)fac[++fnum]=t ;

for(int i=1;i<=fnum;++i){

if(!has[fac[i]])return false ;

}

return true ;

}


int now_i,now_j ;

void dfs(int now_pro,int S,int t)

{

if(now_pro>n)return ;

dp[now_j][now_i]+=dp[S][now_i-1] ;

for(int i=t;i<qnum;++i){

if(S&(1<<i)){

dfs(now_pro*q[i+1],S^(1<<i),i+1) ;

}

}

}


int main()

{

//freopen("test.in","r",stdin) ;

//freopen("test.out","w",stdout) ;

read(n) ;

for(int i=1;i<=n;++i){

int t=i ;

for(int j=2;j*j<=i;++j){

while(t%j==0){

t/=j ;

times[j] ++ ;

}

}

if(t>1){

times[t]++ ;

}

}

int T=sqrt(n+0.5) ;

for(int i=1;i<=4002;++i){

if(times[i]!=0 && times[i]!=1 && times[i]%2==1){

has[i]=1 ;

if(i>T)big[i]=true , b_xh[i]=++bnum , bq[bnum]=i;

elseq[++qnum]=i , s_xh[i]=qnum ;

}

}

int M=(1<<qnum)-1 ;

t_dp[1][0]=1 ;

for(int i=2;i<=n;++i){

int now=i&1 , pre=now^1 ;

bool suc=divi_it(i) ;

for(int j=1;j<=fnum;++j){

if(fac[j]>T)suc=false ;

}

if(!suc){

for(int j=0;j<=M;++j)t_dp[now][j]=t_dp[pre][j] ;

continue ;

}

for(int j=0;j<=M;++j)t_dp[now][j]=0 ;

int tmp=0 ;

for(int j=1;j<=fnum;++j)tmp+=(1<<(s_xh[fac[j]]-1)) ;

for(int j=0;j<=M;++j){

if((tmp&j)==tmp)t_dp[now][j]+=t_dp[pre][j^tmp] ;

t_dp[now][j]+=t_dp[pre][j] ;

}

}

for(int j=0;j<=M;++j){

dp[j][0]=t_dp[n&1][j] ;

}

for(int i=1;i<=bnum;++i){

for(int j=0;j<=M;++j){

now_i=i,now_j=j ;

dfs(bq[i],j,0) ;

}

}

printf(my_LL"\n",dp[M][bnum]*2) ;

return 0;

}


评论