BZOJ5302: [Haoi2018]奇怪的背包

https://lydsy.com/JudgeOnline/problem.php?id=5302

分析:

方程\(\sum\limits_{i=1}^nx_ia_i=y\)有整数解的条件是\(gcd|y\)。
对于这道题，我们可以直接把\(P\)当成一个可以提供负值 or 可以抵消负值的存在。
那么这道题的条件就是\(gcd(d,P)|q_i\)，其中\(d\)是选出那些数的\(gcd\)。
问题缩小到了\(P\)的约数这个范围，最多\(1400\)个。
然后一通预处理就做完了，询问直接用\(gcd(P,q_i)\)对应答案来回答。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

using namespace std;

#define N 1000050

#define mod 1000000007

typedef long long ll;

const int S=100000;

char buf[100000],*p1,*p2;

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int rd() {

	int x=0; char s=nc();

	while(s<'0') s=nc();

	while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();

	return x;

}

int n,m,a[N],P;

int id1[S+10],id2[S+10],w[1450],tot,b[N];

ll f[2][1450],ans[1450];

int gcd(int x,int y) {return y?gcd(y,x%y):x;}

inline void upd(ll &x,ll y) {x+=y; if(x>=mod)x-=mod;}

inline int pos(int x) {return x<=S?id1[x]:id2[P/x];}

inline ll qp(ll x,ll y) {

	ll re=1;

	for(;y;y>>=1,x=x*x%mod) if(y&1) re=re*x%mod; return re;

}

char pbuf[100000],*pp=pbuf;

void push(const char c) {

	if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;

	*pp++=c;

}

int sta[20],tp;

void write(int x) {

	do {

		sta[++tp]=x%10;

		x/=10;

	}while(x);

	while(tp) push(sta[tp--]+'0');

	push('\n');

}

int main() {

	n=rd(),m=rd(),P=rd();

	int i,j;

	for(i=1;i<=n;i++) a[i]=rd();

	for(i=1;i*i<=P;i++) {

		if(P%i==0) {

			w[++tot]=i;

			if(i*i!=P) w[++tot]=P/i;

		}

	}

	sort(w+1,w+tot+1);

	for(i=1;i<=tot;i++) {

		if(w[i]<=S) id1[w[i]]=i;

		else id2[P/w[i]]=i;

	}

	for(i=1;i<=n;i++) b[pos(gcd(a[i],P))]++;

	for(i=1;i<=tot;i++) b[i]=qp(2,b[i])-1;

	f[0][0]=1;

	for(i=0;i<tot;i++) {

		int i0=i&1,i1=(i+1)&1;

		for(j=0;j<=i+1;j++) if(f[i0][j]) {

			f[i1][j]=(f[i1][j]+f[i0][j])%mod;

			int k=pos(gcd(w[j],w[i+1]));

			f[i1][k]=(f[i1][k]+f[i0][j]*b[i+1])%mod;

		}

		memset(f[i0],0,sizeof(f[i0]));

	}

	int l=tot&1;

	for(i=1;i<=tot;i++) {

		for(j=1;j<=i;j++) if(w[i]%w[j]==0) {

			ans[i]=(ans[i]+f[l][j]);

		}

		ans[i]%=mod;

	}

	while(m--) {

		int x; x=rd();

		write(ans[pos(gcd(x,P))]);

	}

	fwrite(pbuf,1,pp-pbuf,stdout);

}

巴特西

BZOJ5302: [Haoi2018]奇怪的背包

BZOJ5302: [Haoi2018]奇怪的背包

最新文章

热门文章