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

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

新老客户大回馈,云服务器低至5折

题目链接

 

Problem Description
There is a set including all positive integers that are not more then n. HazelFan wants to choose some integers from this set, satisfying: 1. The number of integers chosen is at least 1 and at most k. 2. The product of integers chosen is 'free from square', which means it is divisible by no square number other than 1. Now please tell him how many ways are there to choose integers, module 10^9+7.
 

 

Input
The first line contains a positive integer T(1T5), denoting the number of test cases.
For each test case:
A single line contains two positive integers n,k(1n,k500).
 

 

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

 

Sample Input
2
4 2
6 4
 

 

Sample Output
6
19

 

题意:从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;
}

 

 

 

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1824 进击的奶牛

下一篇:P2421 A-B数对(增强版)