hdu6125 Free from square(状态压缩+分组背包)

题意:

在从1-n个数里选不超过m个数,至少选一个,这些数的乘积没有平方数因子(除了1),有多少种选法。

思路

大致是一个状态压缩+分组背包的问题。
其实还没怎么搞懂,先贴上代码,尝试写了一些注释,有问题可以留言交流

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<ctime>
#include "vector"
using namespace std;
#define maxn 505
#define mod 1000000007
#define inf 0x3f3f3f3f
#define ll long long
int p[]={2,3,5,7,11,13,17,19};
int sta[maxn],b[maxn],num[maxn],a[maxn][maxn];
//sta[i]表示i这个数的质因子状态 num存i这个数能有的状态个数
//b[i]表示i这个数除掉质因子后的那个数。a存第i组有哪些数
ll dp[maxn][maxn];//dp[i][j]表示取i个数,状态为j的方案数.
int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){//初始化
            num[i]=0;b[i]=i;sta[i]=0;
        }
        for(int i=1;i<=n;i++)//枚举每一个数的平方数的状态
            for(int j=0;j<8;j++)
                if(sta[i]!=-1&&i%p[j]==0&&i%(p[j]*p[j])!=0){
                    //如果这个数有这个质因子而且因子没有这个质因子的平方
                    //让这个数的状态上第j位的0变成1 就是说有第j个质因子
                    sta[i]|=1<<j;
                    //这个数除掉这个质因子;可以继续挑到别的质因子
                   b[i]/=p[j];
                 }else if(i%(p[j]*p[j])==0){
                     //如果这个数有平方数的因子,必暴毙
                     //直接break
                     sta[i]=-1;
                     break;
                 }
        for(int i=1;i<=n;i++)
            if(sta[i]!=-1){//如果这个数是一个非平方倍数
            //这句话说明这个数是由一些质因子构成,因为最后除到1了,那么把这个数塞到a[i]组
            //否则塞到a[b[i]]组(他最后变成的那个数)
            //这里其实是开始分组
                if(b[i]==1)a[i][num[i]++]=i;
                else a[b[i]][num[b[i]]++]=i;
            }
        for(int i=1;i<=n;i++){//n组
            if(sta[i]==-1||num[i]==0)continue;//如果这个数有平方数的因子或者这个组里面没东西
            for(int j=m-1;j>=0;j--)//拿了几个东西
                for(int k=0;k<(1<<8);k++)//状态
                    for(int q=0;q<num[i];q++)//组里面的东西
                        if((k&sta[a[i][q]])==0)//如果这个数与目前这个状态的二进制不冲突,也就是没有重复的质因子
                            //放了j个数,看二进制放了哪几个质因子
                            dp[j+1][k|sta[a[i][q]]]=(dp[j+1][k|sta[a[i][q]]]+dp[j][k])%mod;
        }
        ll ans=0;
        //把所有的答案加上去
        for(int i=1;i<=m;i++)
            for(int j=0;j<(1<<8);j++)
                ans=(ans+dp[i][j])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}


全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务