CF772D Varying Kibibits 题解 / SOS DP 学习笔记

zrl123456 · 2025-10-04 11:37:03 · 题解

:::::info[题目基本信息] 考察：数学，动态规划 DP，容斥（2700）。
题目简介：
给定序列 \{a_n\}，设：

x_k=\lfloor\frac{x}{10^k}\rfloor\bmod 10

f(S)=\sum_{i=0}^510^i\min_{x\in S}x_i

求：

\bigoplus_{i=0}^{999999}i((\sum_{S\subseteq\{a_n\},f(S)=i}(\sum_{x\in S}x)^2)\bmod(10^9+7))

数据范围：

1\le n\le 10^5
\forall i\in[1,n],0\le a_i\le 999999
::::: 不妨设 \displaystyle G(i)=\sum_{S\subseteq\{a_n\},f(S)=i}(\sum_{x\in S}x)^2，注意到 f(S)=i 这个条件过于严格，不好统计，考虑容斥。
设 \displaystyle g(i)=\sum_{S\subseteq\{a_n\},i\subseteq f(S)}(\sum_{x\in S}x)^2，其中，定义两个整数 x,y 之间满足 x\subseteq y 当且仅当 \forall k\in[0,5],x_i\le y_i，最终我们也可以得到 g(i) 的转移方程式（？）：
\begin{aligned}g(i)&=\sum_{S\subseteq\{a_n\},i\subseteq f(S)}(\sum_{x\in S}x)^2\\&=\sum_{S\subseteq\{a_n\}}[\forall x\in S,i\subseteq x](\sum_{x\in S}x)^2\end{aligned}
好像并不容易，我们记 S_i=\{x\in\{a_n\}|i\subseteq x\}，则 \displaystyle g(i)=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2。
好像还是不容易，但是我们观察到 x\subseteq y\Rightarrow S_y\subseteq S_x，这种情况我们就要考虑从 y 合并到 x。
考虑如何合并，假设有两个集合 S_p,S_q，满足 S_p\cap S_q=\varnothing 且 S_p\cup S_q=S_i，这时我们要将 S_p,S_q 的信息合并到 S_i 上，容易得到：
\begin{aligned}g(i)&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2\\&=\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x+\sum_{x\in S_q\cap S}x)^2\\&=\sum_{S\subseteq S_i}((\sum_{x\in S_p\cap S}x)^2+2(\sum_{x\in S_p\cap S}x)(\sum_{x\in S_q\cap S}x)+(\sum_{x\in S_q\cap S}x)^2)\\&=(\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x)^2)+2(\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x)(\sum_{x\in S_q\cap S}x))+(\sum_{S\subseteq S_i}(\sum_{x\in S_q\cap S}x)^2)\\&=(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_p}x)^2)+2(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_p}x)(\sum_{x\in s_q}x))+(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x)^2)\\&=2^{|S_q|}(\sum_{s_p\subseteq S_p}(\sum_{x\in s_p}x)^2)+2(\sum_{s_p\subseteq S_p}(\sum_{x\in s_p}x)\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x))+2^{|S_p|}(\sum_{s_q\subseteq S_q}(\sum_{x\in s_q}x)^2)\end{aligned}
这时，我们要维护什么就显而易见了，设：
\begin{aligned}F(i,2)&=g(i)\\&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^2\end{aligned} F(i,1)=\sum_{S\subseteq S_i}\sum_{x\in S}x \begin{aligned}F(i,0)&=\sum_{S\subseteq S_i}(\sum_{x\in S}x)^0\\&=\sum_{S\subseteq S_i}1\\&=2^{|S_i|}\end{aligned}
最终，我们可以得到：
F(i,2)=F(p,2)F(q,0)+2F(p,1)F(q,1)+F(p,0)F(q,2)
类似地，我们可以得到：
\begin{aligned}F(i,1)&=\sum_{S\subseteq S_i}\sum_{x\in S}x\\&=\sum_{S\subseteq S_i}(\sum_{x\in S_p\cap S}x+\sum_{x\in S_q\cap S}x)\\&=(\sum_{S\subseteq S_i}\sum_{x\in S_p\cap S}x)+(\sum_{S\subseteq S_i}\sum_{x\in S_q\cap S}x)\\&=(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}\sum_{x\in s_p}x)+(\sum_{s_p\subseteq S_p}\sum_{s_q\subseteq S_q}\sum_{x\in s_q}x)\\&=2^{|S_q|}(\sum_{s_p\subseteq S_p}\sum_{x\in s_p}x)+2^{|S_p|}(\sum_{s_q\subseteq S_q}\sum_{x\in s_q}x)\\&=F(p,1)F(q,0)+F(p,0)F(q,1)\end{aligned} F(i,0)=F(p,0)F(q,0)
现在我们得到了 g(i)=F(i,2)，要容斥出 G(i)，这个就是平凡的高维差分。
最后计算出答案即可。
时间复杂度为 \Theta(n+V\log V)，空间复杂度为 \Theta(V)。