HAOI2018 奇怪的背包

Description

https://www.luogu.com.cn/problem/P4495

Solution

好久没写东西了，来水一发。

先观察部分分。$n=1$ 是即为 $\gcd(x,p)$ 的倍数可以被表示。容易发现可以把体积 $x$ 等价为 $\gcd(x,p)$。

考虑一个物品集合 $S$ 可以表示的重量集合为 $\gcd(S_1,S_2,\dots,S_k,p)$ 的倍数。然后我们就有一个 dp 为 $f_{i,j}$ 表示考虑到前 $i$ 个物品，能表示的选出最大公约数为 $j$ 的集合数量。然后暴力转移是 $O(np)$ 的。发现 $j$ 有用的都是 $p$ 的因数，所以优化到 $O(nd(p))$。又发现本质不同的物品只有 $d(p)$ 个，$x$ 个相同物品的转移系数为 $2^x-1$。

查询先预处理一个前缀和即可。复杂度为 $O(q+d(p)^2\log d(p))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
ll power(ll x,int y=mod-2,int p=mod) {
	ll sum=1;x%=p;
	while (y) {
		if (y&1) sum=sum*x%p;
		x=x*x%p;y>>=1;
	}
	return sum;
}
const int base=1e6;
int	n,q,p;
int id[2005],cnt;
int w[2005],f[2005],g[2005],pw[1000005];
int find(int x) {
	return lower_bound(id+1,id+1+cnt,x)-id;
}
void add(int &x,int y) {x=(x+y)%mod;}
signed main(void){
	int i,j,x;
	read(n);read(q);read(p);
	for (i=1;i*i<=p;i++) if (p%i==0) {
		id[++cnt]=i,id[++cnt]=p/i;
	}
	sort(id+1,id+1+cnt);
	cnt=unique(id+1,id+1+cnt)-id-1;
	for (i=1;i<=n;i++) read(x),w[find(__gcd(x,p))]++;
	f[cnt]=1;
	for (i=1;i<=cnt;i++) {
		copy(f,f+1+cnt,g);
		int res=power(2,w[i])-1;
		for (j=1;j<=cnt;j++) 
			add(f[find(__gcd(id[j],id[i]))],g[j]*res);	 
	}
	for (i=cnt;i>=1;i--) {
		for (j=1;j<i;j++) if (id[i]%id[j]==0) add(f[i],f[j]);
	}
	// for (i=1;i<=cnt;i++) gdb(i,f[i]);
	while (q--) {
		read(x);
		printf("%lld\n",f[find(__gcd(x,p))]);
	}
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i