HDU 6125 Free from square（状态压缩+分组背包）

时间：2023-03-08 18:14:29

http://acm.hdu.edu.cn/showproblem.php?pid=6125

题意：

在${1,2,3，...n}$的数中选择1~k个数，使得它们的乘积不能被平方数整除（1除外），计算有多少种取法。

思路：

考虑一下他们的质因子，如果两个数有相同的质因子，那么它们两个肯定是不能同时选的。这是不是很像分组背包，但是如果以质因子来分类的话，一个数就可能处于多个背包当中，这样就不行了，因为一个数你只能在一个背包中。

这题的数据范围很小，在500的范围内，质数的平方数小于500的就8个数，${2,3,5,7,11,13,17,19}$，那我们就可以二进制压缩来记录每个数的质因子情况，当然了，大于19的质因子每个数最多只会有一个。这样的话到最后就能很方便的划分背包了。

最后分组背包求解。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,ll> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 const int mod=1e9+;

 int n, k;

 int prime[]={,,,,,,,};

 int st[maxn];

 int dp[maxn][maxn];

 int leave[maxn];

 vector<int> v[maxn];

 void solve()

 {

     memset(st,,sizeof(st));

     for(int i=;i<=n;i++)  leave[i]=i;

     for(int i=;i<=n;i++)

     {

         for(int j=;j<;j++)

         {

             if(st[i]==-)  break;

             if(i%prime[j]== && i%(prime[j]*prime[j])!=)

                 st[i]|=<<j, leave[i]/=prime[j];

             else if(i%(prime[j]*prime[j])==)

                 st[i]=-;

         }

     }

     for(int i=;i<=n;i++)  v[i].clear();

     for(int i=;i<=n;i++)

     {

         if(st[i]==-)  continue;

         if(leave[i]==)  v[i].push_back(i);

         else v[leave[i]].push_back(i);

     }

     memset(dp,,sizeof(dp));

     dp[][]=;

     for(int i=;i<=n;i++)

     {

         if(st[i]==- || v[i].size()==)  continue;

         for(int j=k-;j>=;j--)

         {

             for(int s=;s<(<<);s++)

             for(int t=;t<v[i].size();t++)

             {

                 int id=v[i][t];

                 if((s&st[id])==)

                     dp[j+][s|st[id]]=(dp[j+][s|st[id]]+dp[j][s])%mod;

             }

         }

     }

     ll ans=;

     for(int i=;i<=k;i++)

     {

         for(int s=;s<(<<);s++)

             ans=(ans+dp[i][s])%mod;

     }

     cout<<ans<<endl;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&k);

         solve();

     }

     return ;

 }

相关文章