洛谷 P4495 [HAOI2018]奇怪的背包 解题报告

P4495 [HAOI2018]奇怪的背包

题目描述

小\(C\)非常擅长背包问题,他有一个奇怪的背包,这个背包有一个参数\(P\),当他 向这个背包内放入若干个物品后,背包的重量是物品总体积对\(P\)取模后的结果. 现在小\(C\)有\(n\)种体积不同的物品,第\(i\)种占用体积为\(V_i\),每种物品都有无限个. 他会进行\(q\)次询问,每次询问给出重量\(w_i\),你需要回答有多少种放入物品的方案,能将一个初始为空的背包的重量变为\(w_i\).注意,两种方案被认为是不同的, 当且仅当放入物品的种类不同,而与每种物品放入的个数无关.不难发现总的方案数为\(2^n\). 由于答案可能很大,你只需要输出答案对\(1e9+7\)取模的结果.

输入输出格式

输入格式

第一行三个整数\(n,q,P\),含义见问题描述. 接下来一行\(n\)个整数表示\(V_i\). 接下来一行\(q\)个整数表示\(w_i\).

输出格式:

输出\(q\)行,每行一个整数表示答案.

说明

对于所有数据,有\(1\le n,q\le 10^6,3 \le P \le 10^9,0 < V_i,w_i < P\),保证\(V_i\)两两不同。

测试点标号 \(n\) \(q\) \(p\)
\(1\) \(=1\) \(\le 10^3\) \(\le 10^9\)
\(2\) \(\le 10\) \(\le 10^3\) \(\le 10\)
\(3\) \(\le 10\) \(\le 10^3\) \(\le 250\)
\(4\) \(\le 10\) \(\le 10^3\) \(\le 250\)
\(5\) \(\le 10^3\) \(\le 10^3\) \(\le 10^4\)
\(6\) \(\le 10^3\) \(\le 10^3\) \(\le 10^4\)
\(7\) \(\le 10^3\) \(\le 10^3\) \(=998244353\)
\(8\) \(\le 10^3\) \(\le 10^3\) \(\le 10^9\)
\(9\) \(\le 10^6\) \(\le 10^6\) \(\le 10^9\)
\(10\) \(\le 10^6\) \(\le 10^6\) \(\le 10^9\)

是什么限制了我做题的想象力。。

我们要求

\[\sum x_ia_i \equiv w_i \pmod p
\]

有多少个解,换成方程,即

\[\sum x_ia_i -py =w_i
\]

有裴蜀定理可以猜到,有解的要求是\(gcd(x_1,x_2,\dots,x_n,p)|w_i\)

于是我们可以做\(DP\),令\(dp_{i,j}\)表示前\(i\)个数选择的数的\(gcd\)和\(p\)做\(gcd\)后的结果为\(j\)

发现这样的状态是\(O(nd(p))\)的,\(d(p)\)表示\(p\)的约数个数

我们可以把\(V_i\)与\(p\)的\(gcd\)相同的放在一起做,这样状态就优化到了\(O(d^2(p))\)了

转移的时候要求\(gcd\),那么\(dp\)的总复杂度就是\(O(d^2(p)\log p)\)的

最后对每个\(w_i\)统计答案是\(\sum_{i|w_i}dp_{n,i}\),不可以暴力统计,注意到是可以实现预处理的。

总复杂度\(O(\sqrt p+d^2(p)\log p+n\log p+q)\)的


Code:

#include <cstdio>
#include <algorithm>
#define ll long long
const int N=1e6+10;
const int M=2010;
const ll mod=1e9+7;
int n_,n,q,p,v[N],siz[N],cnt;
ll dp[M][M],f[M],d[M],po[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int Find(int x){return std::lower_bound(d+1,d+1+cnt,x)-d;}
int main()
{
scanf("%d%d%d",&n_,&q,&p);
po[0]=1;
for(int i=1;i<=n_;i++)
{
scanf("%d",v+i);
v[i]=gcd(v[i],p);
po[i]=(po[i-1]<<1ll)%mod;
}
std::sort(v+1,v+1+n_);
for(int i=1;i<=n_;i++)
{
if(v[i]==v[n])
++siz[n];
else
v[++n]=v[i],siz[n]=1;
}
for(int i=1;i*i<=p;i++)
if(p%i==0)
d[++cnt]=p/i,d[++cnt]=i;
std::sort(d+1,d+1+cnt);
cnt=std::unique(d+1,d+1+cnt)-d-1;
for(int i=0;i<n;i++)
{
for(int j=1;j<=cnt;j++)
{
int pos=Find(gcd(v[i+1],d[j]));
(dp[i+1][pos]+=dp[i][j]*(po[siz[i+1]]-1)%mod)%=mod;
(dp[i+1][j]+=dp[i][j])%=mod;
}
(dp[i+1][Find(gcd(v[i+1],p))]+=po[siz[i+1]]-1)%=mod;
}
for(int i=1;i<=cnt;i++)
for(int j=1;j<=i;j++)
if(d[i]%d[j]==0)
(f[i]+=dp[n][j])%=mod;
for(int w,i=1;i<=q;i++)
{
scanf("%d",&w);
printf("%lld\n",f[Find(gcd(w,p))]);
}
return 0;
}

2018.10.31

上一篇:luogu P4389 付公主的背包


下一篇:索尼Sony ATI显卡驱动 Win7 Win8 Win8.1 视频黑屏 解决方法