haoi2018奇怪的背包题解

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=5302

对于一个物品，设它体积为v，那么，在背包参数为p的情况下，它能达到gcd(v,p)的倍数的重量

对于两个物品，设它们的体积为v1和v2，那么，在背包参数为p的情况下，他能达到gcd(v1,v2,p)的倍数的重量

对于每个物品，我们记下它的gcd(v,p)，问题变为给定一个x，求有多少个v的集合，是集合内所有元素的gcd能被x整除

我们设dp[i][j]表示p的前i个约数有多少种组合是组合后的gcd为j。

接下来，我们考虑怎么转移

先给伪代码(不加取模)：

for(i=1;i<=约数个数;++i)

　　for(j=1;j<=约数个数;++j){

　　　　x=gcd(第i个约数，第j个约数)dp[i][x]+=dp[i-1][j]*(2^约数i的个数-1);

　　　　dp[i][j]+=dp[i][j-1];

　　}

这种转移方式有点奇怪，是个好思路，我们平常的dp都是枚举状态，然后在寻找能转移到我们枚举的状态的状态。这个dp是先枚举已经计算完成的状态，在计算这些状态能转移到哪，更新，有点类似noip2017 提高组day1T3的拓扑排序dp写法。

上AC代码（wxy数组就是dp数组，有些细节上的处理我还没讲，可以自己实现,ps:我常数有点大(两个map)）:

#include <bits/stdc++.h>
using namespace std;
;
;
#define _l long long
int n,q,p,ys[N];
map<int,int>reff;
map<int,int>cnt;
_l p2[N*N],wxy[N][N],an[N];
 ? y:gcd(y,x%y);}
int main(){
    scanf("%d%d%d",&n,&q,&p);
    int i;
    ;i*i<=p;++i)){
        ys[++ys[]]=i,reff[i]=ys[];]]=p/i,reff[p/i]=ys[];
    }
    ;i<=n;++i){
        int x;scanf("%d",&x);x=gcd(max(x,p),min(x,p));
        ++cnt[x];
    }
    ]=;
    ;i<=n;++i)p2[i]=(p2[i-]*)%md;wxy[][reff[p]]=;
    ;i<=ys[];++i);j<=ys[];++j){
        int tmp=gcd(max(ys[i],ys[j]),min(ys[i],ys[j]));
        wxy[i][reff[tmp]]=(wxy[i][reff[tmp]]+wxy[i-][j]*(_l)(p2[cnt[ys[i]]]-))%md;
        wxy[i][j]=(wxy[i-][j]+wxy[i][j])%md;
    }
    ;i<=ys[];++i);j<=ys[];++j))an[i]=(an[i]+wxy[ys[]][j])%md;
    while(q--){
        int x;scanf("%d",&x);x=gcd(max(x,p),min(x,p));
        printf("%lld\n",an[reff[x]]);
    }
}

巴特西

haoi2018奇怪的背包题解

最新文章

热门文章