首页 > > 程序设计 > C/C++ >

hdu 6125 -- Free from square(状态压缩+分组背…

2018-06-17 22:00:35来源：未知阅读 ()

题目链接

Problem Description

There is a set including all positive integers that are not more then

Input

The first line contains a positive integer

Output

For each test case:
A single line contains a nonnegative integer, denoting the answer.

Sample Input

4 2

6 4

Sample Output

题意：从1~n中任意取1~K个数（同一个数不能用多次），这些数的乘积不能被任意一个数的平方整除（除了 1 ），求有多少种取法？

思路：可以从以上题意分析出，取的多个数不能有相同的质数因子。由于n<=500，所以一个数小于sqrt(n)的质数因子可能有多个，但大于sqrt(n)的质数因子只可能有一个。而小于sqrt(n)的质数有2 、3、5、7、11、13、17、19，一共8个，所以对这8个质数因子进行状压。然后就是背包DP，因为成绩不能含有质数因子的平方，所以需要进行分组，将含有相同大于sqrt（n）的数放在一组，保证这样的数只能每次取一个，也就是分组背包。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int mod=1e9+7;
const int N=505;
int dp[N][256];
int r[N],st[N];
int p[8]={2,3,5,7,11,13,17,19};
vector<int>v[N];

int main()
{
    int T; cin>>T;
    while(T--)
    {
        int n,m; scanf("%d%d",&n,&m);
        for(int i=0;i<N;i++)
        {
            v[i].clear();
            r[i]=i;
            st[i]=0;
        }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<8;j++)
            {
                if(i%p[j]==0 && i%(p[j]*p[j])!=0) st[i]|=1<<j,r[i]/=p[j];
                else if(i%(p[j]*p[j])==0){
                    st[i]=-1; break;
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(st[i]==-1) continue;
            if(r[i]==1) v[i].push_back(i);
            else v[r[i]].push_back(i);
        }
//        for(int i=1;i<=n;i++)
//        {
//            for(int j=0;j<v[i].size();j++)
//                cout<<v[i][j]<<" ";
//            cout<<endl;
//        }
        for(int i=1;i<=n;i++)
        {
            if(st[i]==-1 || v[i].size()==0) continue;
            for(int j=m-1;j>=0;j--)
            {
                for(int s=0;s<256;s++)
                {
                    for(int k=0;k<v[i].size();k++)
                    {
                        int d=st[v[i][k]];
                        if((s&d)!=0) continue;
                        dp[j+1][s|d]=(dp[j+1][s|d]+dp[j][s])%mod;
                    }
                }
            }
        }
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<256;j++)
                ans=(ans+dp[i][j])%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}