推了好久的莫反柿子炸了 讨厌T^T

一个$dp$题解

若只放体积为$a$的物品，则能得到的重量$b$满足$\exists x,y$使得$ax+Py=b$。

根据裴蜀定理 $b|\gcd(a,P)$。

对于多个数同理。

那么我们现在所求的内容就是，$\gcd$为某个数因数的子集个数。

我们可以$O(\sqrt{P})$求出$P$的所有因数，只在它的这些因数上考虑。

我认为最困难的是想到$dp$。记$dp_{i,j}$表示考虑了$P$的前$i$个因数，组成的$gcd$为$P$的第$j$个因数的子集个数。

转移也是容易的。

对于每个询问，设$\gcd(w,P)$是$P$的第$k$个因数，记$s_i$为$P$的第$i$个因数，$S$为$P$的因数个数，答案为$\sum\limits_{s_i|s_k}dp[S][i]$。

对于每个$k$都可以预处理，复杂度$O(S^2)$，总复杂度$O(S^2\log{P})$。

原题：P4495 [HAOI2018] 奇怪的背包

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define mkp make_pair
#define psb push_back
const int mod=1e9+7;
int n,Q,P;
int sons[101000],stot;
unordered_map<int,int>mp;
int cnt[101000];
int dp[2552][2552],f2[1010000];
int ans[101000];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
//	system("fc my.out ex.out");return 0;
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
	cin>>n>>Q>>P;
	for(int i=1;i<=sqrt(P);i++){
		if(P%i==0){
			sons[++stot]=i;
			if(i*i!=P) sons[++stot]=P/i;
		}
	}sort(sons+1,sons+1+stot);
	for(int i=1;i<=stot;i++){
		mp[sons[i]]=i;
	}
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		x=__gcd(x,P);
		cnt[mp[x]]++;
	}dp[0][stot]=1;
	f2[0]=1;
	for(int i=1;i<=n;i++)f2[i]=f2[i-1]*2%mod;
	for(int i=1;i<=stot;i++){
		for(int j=1;j<=stot;j++){
			dp[i][j]=dp[i-1][j];
			int to=mp[__gcd(sons[i],sons[j])];
			dp[i][to]=(dp[i][to]+(dp[i-1][j])*(f2[cnt[i]]-1+mod))%mod;
		}
	}
	for(int i=1;i<=stot;i++){
		for(int j=1;j<=stot;j++){
			if(sons[i]%sons[j]) continue;
			ans[i]=(ans[i]+dp[stot][j])%mod;
		}
	}while(Q--){
		int x;
		cin>>x;
		x=mp[__gcd(x,P)];
		cout<<ans[x]<<"\n";
	}
	return 0;
}