题解 | #Fly#

传送门

问题等价于从 $2^0\cdot a_1,2^1\cdot a_1,\cdots ,2^{59}\cdot a_1,2^0\cdot a_2,\cdots ,2^{59}\cdot a_{n}2^0\backslash cdot\; a\_1,\; 2^1\backslash cdot\; a\_1,\; \backslash cdots,\; 2^\{59\}\backslash cdot\; a\_1,\; 2^0\backslash cdot\; a\_2,\; \backslash cdots,\; 2^\{59\}\backslash cdot\; a\_n$ 共 $60n60n$ 个物品中，扣除所有 $2^{c_i}\cdot a_{b_i}2^\{c\_i\}\backslash cdot\; a\_\{b\_i\}$ 的 $kk$ 个物品后，查询体积不超过 $mm$ 的背包方案数

注意到每个 $a_{i}a\_i$ 前面乘的系数都是 $22$ 的整幂次，若我们对进行背包的物品，按系数的 $22$ 的幂次进行分类，从小到大进行背包；则在 $2^{t}2^t$ 为系数的物品进行背包后，后续物品再次进行背包，是不可能影响低于 $tt$ 位的二进制数码的

为了避免状态过多，我们试图采用数位 dp 的方式，一位一位考虑对答案的贡献

注意到若进行到第 $tt$ 位后，若体积 $VV$ 的二进制低 $tt$ 位大于 $mm$ ，即 $V\mathrm{m}\mathrm{o}\mathrm{d}{2}^t>m\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t}V\backslash bmod\; 2^t>m\backslash bmod\; 2^t$ ，则当且仅当 $VV$ 的第 $t+1t+1$ 位为 $00$ 且 $mm$ 的第 $t+1t+1$ 位为 $11$ 会使得 $V\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}\le m\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}V\backslash bmod\; 2^\{t+1\}\backslash leq\; m\backslash bmod\; 2^\{t+1\}$ ；若体积 $VV$ 的二进制低 $tt$ 位小于等于 $mm$ ，即 $V\mathrm{m}\mathrm{o}\mathrm{d}{2}^t\le m\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t}V\backslash bmod\; 2^t\backslash leq\; m\backslash bmod\; 2^t$ ，则当且仅当 $VV$ 的第 $t+1t+1$ 位为 $11$ 且 $mm$ 的第 $t+1t+1$ 位为 $00$ 会使得 $V\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}>m\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}V\backslash bmod\; 2^\{t+1\}>\; m\backslash bmod\; 2^\{t+1\}$

因此，我们考虑记 $d{p}_{t,i,0\mathrm{/}1}dp\_\{t,\; i,\; 0/1\}$ 表示进行完 $2^{t}2^t$ 为系数的物品的背包后，体积 $VV$ 满足 $\lfloor \frac{V}{2^{t+1}}\rfloor =i\backslash lfloor\{V\backslash over\; 2^\{t+1\}\}\backslash rfloor=i$ ，且 $V\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}V\backslash bmod\; 2^\{t+1\}$ 是否严格大于 $m\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}m\backslash bmod\; 2^\{t+1\}$ ，的方案数

故答案是 ${\displaystyle \sum _{i=1}^n{a}_i{x}_i\le m}\backslash displaystyle\; \backslash sum\_\{i=1\}^n\; a\_ix\_i\backslash leq\; m$ ，即是 $V\le mV\backslash leq\; m$ 的方案数。由于 ，故 ，因此答案为 $d{p}_{59,0,0}dp\_\{59,\; 0,\; 0\}$

这种情况下，${\displaystyle 0\le t\le 59,0\le i\le \lfloor \frac{V}{2^t}\rfloor \le \frac{1}{2^t}\sum _{x=0}^t\sum _{i=1}^n{2}^x\cdot a_i=\sum _{i=1}^n{a}_i\cdot \frac{1}{2^t}\sum _{x=0}^t{2}^x\le 2\sum _{i=1}^n{a}_i:=2A}\backslash displaystyle\; 0\backslash leq\; t\backslash leq\; 59,\; 0\backslash leq\; i\backslash leq\; \backslash lfloor\{V\backslash over\; 2^t\}\backslash rfloor\; \backslash leq\; \{1\backslash over\; 2^t\}\backslash sum\_\{x=0\}^t\backslash sum\_\{i=1\}^n\; 2^x\backslash cdot\; a\_i=\backslash sum\_\{i=1\}^n\; a\_i\backslash cdot\; \{1\backslash over\; 2^t\}\backslash sum\_\{x=0\}^t\; 2^x\backslash leq\; 2\backslash sum\_\{i=1\}^n\; a\_i:=2A$

考虑该 $dpdp$ 的转移，首先，我们需要知道系数为 $2^{t}2^t$ 的物品的背包结果，它可以用生成函数 ${\displaystyle \prod _{i=1(i,t)\in ̸\{(b_k,c_k)\}}^n(1+x^{2^t\cdot a_i})}\backslash displaystyle\; \backslash prod\_\{i=1\backslash \backslash (i,\; t)\backslash not\backslash in\; \backslash \{(b\_k,\; c\_k)\backslash \}\}^n\; (1+x^\{2^t\backslash cdot\; a\_i\})$ ，我们记为 $g_t(x^{2^t})g\_t(x^\{2^t\})$ ，即 ${\displaystyle g_t(x)=\prod _{i=1(i,t)\in ̸\{(b_k,c_k)\}}^n(1+x^{a_i})=\prod _{i=1}^n(1+x^{a_i})\cdot [\prod _{(i,t)\in \{(b_k,c_k)\}}(1+x^{a_i}){]}^{-1}}\backslash displaystyle\; g\_t(x)=\backslash prod\_\{i=1\backslash \backslash (i,\; t)\backslash not\backslash in\; \backslash \{(b\_k,\; c\_k)\backslash \}\}^n\; (1+x^\{a\_i\})=\backslash prod\_\{i=1\}^n(1+x^\{a\_i\})\backslash cdot\; [\backslash prod\_\{(i,\; t)\backslash in\; \backslash \{(b\_k,\; c\_k)\backslash \}\}\; (1+x^\{a\_i\})]^\{-1\}$

我们可以先用多项式线段树分治或多项式启发式合并，先在 $O(n{}^{2}n)O(n\backslash log^2\; n)$ 的时间内求出 ${\displaystyle g(x)=\prod _{i=1}^n(1+x^{a_i})}\backslash displaystyle\; g(x)=\backslash prod\_\{i=1\}^n(1+x^\{a\_i\})$ 。后续求解 $g_t(x)g\_t(x)$ 时，只需要反向跑背包进行删除，复杂度为 $O(n)O(n)$ ；由于限制数量为 $k\le 5\times 10^{3}k\backslash leq\; 5\backslash times\; 10^3$ 个，故复杂度 $O(kn)O(kn)$ 是可接受的

现在考虑已知 $d{p}_{t-1,0\cdots ,2A,0\mathrm{/}1}dp\_\{t-1,\; 0\backslash cdots,\; 2A,0/1\}$ 、已知 $[x^l]g_t(x)[x^l]g\_t(x)$ ，如何合并得出 $d{p}_{t,0\cdots 2A,0\mathrm{/}1}dp\_\{t,\; 0\backslash cdots\; 2A,\; 0/1\}$ 的结果

由于 $d{p}_{t-1,i,0}dp\_\{t-1,\; i,\; 0\}$ 表示进行完 $2^{t-1}2^\{t-1\}$ 为系数的物品后，体积 $VV$ 满足 $\lfloor \frac{V}{2^t}\rfloor =i\backslash lfloor\{V\backslash over\; 2^t\}\backslash rfloor=i$ ，且 $V\mathrm{m}\mathrm{o}\mathrm{d}{2}^t\le m\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t}V\backslash bmod\; 2^t\backslash leq\; m\backslash bmod\; 2^t$ 的方案数；$[x^l]g(x)[x^l]g(x)$ 表示系数为 $2^{t}2^t$ 的物品，拼出体积为 $2^t\cdot l2^t\backslash cdot\; l$ 的方案数

因此将两者合并后，新体积 ${\displaystyle V^{\mathrm{\prime }}=V+2^t\cdot l\Rightarrow \lfloor \frac{V^{\mathrm{\prime }}}{2^{t+1}}\rfloor =\lfloor \frac{V+2^t\cdot l}{2^{t+1}}\rfloor =\lfloor \frac{i+l}{2}\rfloor }\backslash displaystyle\; V\text{'}=V+2^t\backslash cdot\; l\backslash Rightarrow\; \backslash lfloor\{V\text{'}\backslash over\; 2^\{t+1\}\}\backslash rfloor=\backslash lfloor\{V+2^t\backslash cdot\; l\backslash over\; 2^\{t+1\}\}\backslash rfloor=\backslash lfloor\{i+l\backslash over\; 2\}\backslash rfloor$ ，大小关系 ${\displaystyle b=[V^{\mathrm{\prime }}\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}>m\mathrm{m}\mathrm{o}\mathrm{d}{2}^{t+1}]=[V_t^{\mathrm{\prime }}>m_t]=[\lfloor \frac{V^{\mathrm{\prime }}}{2^t}{\rfloor }_0>m_t]=[(i+l)\mathrm{m}\mathrm{o}\mathrm{d}2>m_t]}\backslash displaystyle\; b=[V\text{'}\backslash bmod\; 2^\{t+1\}>m\backslash bmod\; 2^\{t+1\}]=[V\text{'}\_t>m\_t]=[\backslash lfloor\{V\text{'}\backslash over\; 2^t\}\backslash rfloor\_0>m\_t]=[(i+l)\backslash bmod\; 2>m\_t]$

于是可以写出一部分的转移式：${\displaystyle d{p}_{t,\lfloor \frac{I}{2}\rfloor ,[I\mathrm{m}\mathrm{o}\mathrm{d}2>m_t]}=\sum _{i+l=I}d{p}_{t-1,i,0}\cdot [x^l]g_t(x)}\backslash displaystyle\; dp\_\{t,\; \backslash lfloor\{I\backslash over\; 2\}\backslash rfloor,\; [I\backslash bmod\; 2>m\_t]\}=\backslash sum\_\{i+l=I\}dp\_\{t-1,\; i,\; 0\}\backslash cdot\; [x^l]g\_t(x)$ ，显然是加法卷积的形式，可以在 $O(2A\log 2A)O(2A\backslash log\; 2A)$ 的时间内求解

同理，另一部分转移式为：${\displaystyle d{p}_{t,\lfloor \frac{I}{2}\rfloor ,[I\mathrm{m}\mathrm{o}\mathrm{d}2\ge m_t]}=\sum _{i+l=I}d{p}_{t-1,i,1}\cdot [x^l]g_t(x)}\backslash displaystyle\; dp\_\{t,\; \backslash lfloor\{I\backslash over\; 2\}\backslash rfloor,\; [I\backslash bmod\; 2\backslash geq\; m\_t]\}=\backslash sum\_\{i+l=I\}dp\_\{t-1,\; i,\; 1\}\backslash cdot\; [x^l]g\_t(x)$ ，同样是加法卷积，可以在 $O(2A\log 2A)O(2A\backslash log\; 2A)$ 的时间内求解

初始时，是 $d{p}_{0,i,0\mathrm{/}1}dp\_\{0,\; i,\; 0/1\}$ 表示进行完 $2^{0}2^0$ 为系数的物品后，体积 $\lfloor \frac{V}{2}\rfloor =i\backslash lfloor\{V\backslash over\; 2\}\backslash rfloor=i$ 且 $V\mathrm{m}\mathrm{o}\mathrm{d}2V\backslash bmod\; 2$ 是否严格大于 $m\mathrm{m}\mathrm{o}\mathrm{d}2m\backslash bmod\; 2$ ；也是直接由 $[x^l]g_0(x)[x^l]g\_0(x)$ 贡献到 $d{p}_{0,\lfloor \frac{l}{2}\rfloor ,l\mathrm{m}\mathrm{o}\mathrm{d}2>m\mathrm{m}\mathrm{o}\mathrm{d}2}dp\_\{0,\; \backslash lfloor\{l\backslash over\; 2\}\backslash rfloor,\; l\backslash bmod\; 2>m\backslash bmod\; 2\}$

综上，先对 $(1+x^{a_i})(1+x^\{a\_i\})$ 进行 $O(n{}^{2}n)O(n\backslash log^2\; n)$ 的多项式启发式合并或多项式线段树分治；接着对数位进行 DP，先求出 $g_t(x)g\_t(x)$ ，再分别利用 $d{p}_{t-1,0\cdots 2A,0},d{p}_{t-1,0\cdots 2A,1}dp\_\{t-1,\; 0\backslash cdots\; 2A,\; 0\},dp\_\{t-1,\; 0\backslash cdots\; 2A,\; 1\}$ 与 $g_t(x)g\_t(x)$ 卷积递推 $d{p}_{t,0\cdots 2A,0\mathrm{/}1}dp\_\{t,\; 0\backslash cdots\; 2A,\; 0/1\}$ 的贡献

求 $g_t(x)g\_t(x)$ 的总复杂度为 $O(nk)O(nk)$ ，卷积递推的复杂度为 $O(\log m\cdot 2\cdot 2A\log 2A)=O(\log m\cdot A\log A)=O(\log m\cdot n\log n)O(\backslash log\; m\backslash cdot\; 2\backslash cdot\; 2A\backslash log\; 2A)=O(\backslash log\; m\backslash cdot\; A\backslash log\; A)=O(\backslash log\; m\backslash cdot\; n\backslash log\; n)$

故总复杂度为 $O(n\log n(\log n+\log m)+nk)O(n\backslash log\; n(\backslash log\; n+\backslash log\; m)+nk)$

【核心代码】

const int Lim=8e4, MAXN=Lim+10;
int n, k, a[MAXN];
ll m, mask[MAXN];
poly f, g, h;
inline void divit(poly &f, int a) {
	for(int i=sz(f)-1, j=i-a; j>=0; --i, --j)
		f[j]=f[j]-f[i];
	for(int i=0, j=a, J=sz(f); j<J; ++i, ++j)
		f[i]=f[j];
	rsz(f, sz(f)-a);
}

vir dp[2][MAXN][2];
inline void work() {
	g=f;
	for(int i=1; i<=n; ++i) if(mask[i]&1) divit(g, a[i]);
	for(int i=sz(g)-1; ~i; --i) dp[0][i>>1][(i&1)>(m&1)]=dp[0][i>>1][(i&1)>(m&1)]+g[i];
	
	for(int t=1; t<=59; ++t) {
		auto lst=dp[t+1&1], now=dp[t&1];
		int mt=(m>>t)&1;
		for(int i=0, I=Lim; i<=I; ++i) now[i][0]=now[i][1]=0;
		g=f;
		for(int i=1; i<=n; ++i) if((mask[i]>>t)&1) divit(g, a[i]);
		
		rsz(h, Lim+1);
		for(int i=0; i<=Lim; ++i) h[i]=lst[i][0];
		Poly::get_mul(h, g, sz(h), sz(g));
		for(int i=sz(h)-1; ~i; --i)
			now[i>>1][(i&1)>mt]=now[i>>1][(i&1)>mt]+h[i];
		rsz(h, Lim+1);
		for(int i=0; i<=Lim; ++i) h[i]=lst[i][1];
		Poly::get_mul(h, g, sz(h), sz(g));
		for(int i=sz(h)-1; ~i; --i)
			now[i>>1][(i&1)>=mt]=now[i>>1][(i&1)>=mt]+h[i];
	}
	
	cout<<(int)dp[1][0][0];
}
inline void init() {
	Poly::init();
	cin>>n>>m>>k;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
		poly &p=Poly::T[i];
		rsz(p, a[i]+1);
		p[0]=p[a[i]]=1;
	}
	f=Poly::get_merge(n);
	
	for(int i=1, x, y; i<=k; ++i)
		cin>>x>>y, mask[x]|=pw(y);
}