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