DQS DQS

【hdu6125】Free from square 状压DP

in 状压DP,算法,DPread (95) 文章转载请注明来源!

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(1≤T≤5), denoting the number of test cases.
For each test case:
A single line contains two positive integers n,k(1≤n,k≤500).

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

Source

2017 Multi-University Training Contest - Team 7

Recommend

liuyiding | We have carefully selected several similar problems for you: 6132 6131 6130 6129 6128


今天一个多校题,BB对了代码写的时候思路混乱,最后代码和思路都GG了,很伤心。

题意:在1~n中选至多k个数,要求乘积不能是任意数的平方数的倍数,求方案数。$1<=n,k<=500$

即每个数唯一分解后的幂必须小于等于1.
考虑NOI2015寿司晚宴的思路:对于小于$\sqrt{500}=22$的质数,只有8个,可以状压。对于每个数,大于22的质数至多只有一个。

所以对于唯一分解后没有大质数的数,$f[i][j][S]$表示考虑前i个数,当前选了j个数,当前状态是S的方案数,可以直接转移。
对于有大质数的数,可以对这些数放到对应的每个大质数的桶里。这时每个桶至多选一个数,不要忘了按小质数的状压转移。
不要忘了考虑1。
空间需要优化掉一维。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1010;
const LL INF = 100000000000000010ll;
const int mod = 1000000007;
const int MAXC = 1 << 8;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int pri[233] = {2,3,5,7,11,13,17,19}; //10

struct haha{
    int x,a,p;
}l[SZ];

bool operator <(haha a,haha b)
{
    return a.p < b.p;
}

bool cmp(int x,int y)
{
    return l[x].x < l[y].x;
}

void calc(int x,int id)
{
    l[id].x = x;
    int xx = x;
    for(int i = 0;i < 8;i ++)
    {
        int v = pri[i];
        if(x % v == 0)
        {
            while(x % v == 0) x /= v;
            l[id].a |= (1 << i);
        }
    }
    l[id].p = x;
}

bool use[SZ];

int f[510][MAXC + 1],a[SZ],dp[510][MAXC + 1];

vector<int> t[SZ];

int main()
{
    int tot = 0;
    for(int i = 2;i <= 500;i ++)
    {
        bool flag = 0;
        for(int j = 2;j * j <= i;j ++)
            if(i % (j * j) == 0)
                {flag = 1; break;}
        if(!flag) calc(i,++ tot);
    }
    sort(l + 1,l + 1 + tot);
    int m = 0;
    for(int i = 1;i <= tot;i ++)
    {
        if(!use[l[i].p])
            m ++,use[l[i].p] = 1;
        t[m].push_back(i);
    }
    for(int i = 1;i <= m;i ++)
        sort(t[i].begin(),t[i].end(),cmp);

    int T = read();
    while(T --)
    {
        int n = read(),k = read();
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        memset(f,0,sizeof(f));
        for(int i = 1;i <= m;i ++)
        {
            for(int j = 0;j < t[i].size();j ++)
                if(l[t[i][j]].x <= n) a[i] ++;
        }

        f[0][0] = 1;
        for(int i = 1;i <= a[1];i ++)
        {
            int x = t[1][i - 1];
            for(int j = i;j >= 1;j --)
                for(int S = MAXC - 1;S >= 0;S --)
                    if((S & l[x].a) == 0)
                        (f[j][S | l[x].a] += f[j - 1][S]) %= mod;
        }

        a[m + 1] = 1;
        for(int i = 0;i <= k;i ++)
            for(int S = 0;S <= MAXC - 1;S ++)
                dp[i][S] = f[i][S];

    /*    for(int i = 0;i <= k;i ++)
            for(int S = 0;S <= MAXC - 1;S ++)
                dp[i][S] = f[i][S];*/


        for(int i = 2;i <= m + 1;i ++)
        {
            if(!a[i]) continue;

            if(i != m + 1)
                for(int j = k;j >= 1;j --)
                    for(int S = MAXC - 1;S >= 0;S --)
                        for(int x = 0;x < a[i];x ++)
                        {
                            int d = l[t[i][x]].a;
                            if((d & S) == 0)
                                (dp[j][d | S] += dp[j - 1][S]) %= mod;
                        }
            else
                for(int j = k;j >= 1;j --)
                    for(int S = MAXC - 1;S >= 0;S --)
                            (dp[j][S] += (LL)dp[j - 1][S]) %= mod;
        }
        int ans = 0;
        for(int i = 1;i <= k;i ++)
            for(int S = 0;S <= MAXC - 1;S ++)
                (ans += dp[i][S]) %= mod;
        printf("%d\n",ans);
    }
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

状压DP算法DP
最后由DQS修改于2017-08-15 19:46
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆