abc390又没ak
analysis
·
·
个人记录
D - Stone XOR
注意到就是把这些数分组，答案是每组加法和的异或和。
异或运算是存在交换律的，所以分组的方案就是 B(n)=[x^n]\exp(e^x-1)。
检验发现 B(n) 不是很大，于是暴力深搜即可。
E - Vitamin Balance
注意到三种维生素是独立的，即一个物品只对一种维生素做贡献。
于是可以先 O(NX) 的跑一遍背包，得到 f_{i,j} 表示不超过 j 的代价最多得到 i 类维生素 f_{i,j} 单位。
然后可以二分答案。如何算答案下的代价呢？直接在 f_i 数组上二分，找到对应下标加上就好了。
关键代码：
//f[i][x+1]=1e9+1;
bool ck(int ans){
int res=0;
for(int i=1;i<=3;i++){
res+=lower_bound(f[i]+1,f[i]+1+x+1,ans)-f[i];
}
return res<=x;
}
F - Double Sum 3
我们直接统计有多少个 $i$ 满足 $i \in A[L,R] \wedge i+1 \not\in A[L,R]$，就可以求得 $f(L,R)$。
换个方向，我们只要对于每个 $i$，求得有多少个 $(L,R)$ 满足 $i \in A[L,R] \wedge i+1 \not\in A[L,R]$ 就是答案了。
考虑 $x|A_x=i+1 \vee x=0 \vee x=n+1$。他们把序列分为若干区间。要每个区间中有多少子区间含有 $i$。假设 $L,R$ 中的所有 $i$ 的位置与 $L$ 按顺序构成序列 $P$，答案就是 $\sum_{i \geq 1}(p_i-p_{i-1})(R-p_i+1)$。直接统计就是线性的。
### G - Permutation Concatenation
观前提示：$3 \times 10^5$ 是 $6$ 个数，而不是 $5$ 个（不要问为什么要提示）。
---
考虑先求出 $len_i$ 表示长度为 $i$ 的数有多少个，以及 $s_i$ 表示长度为 $i$ 的数之和。
我们对数 $x$ 统计其造成的所有贡献，可以写出（注意 $x$ 对应的 $len$ 要减 $1$）：
$$
\sum_{\{v_i\}}(x\prod_{i=1}^{6}(10^{i})^{v_i})(\prod_{i=1}^{6}\binom{len_i}{v_i})(\sum v_i)!(n-1-\sum v_i)!
$$
稍微解释下，枚举每种数有多少个在 $x$ 之前，然后贡献就是 $(x\prod_{i=1}^{6}(10^{i})^{v_i})$，方案数就是 $(\sum v_i)!(n-1-\sum v_i)!$。
整理一下：
$$
\sum_{\{v_i\}}x(\prod_{i=1}^{6}(10^{i})^{v_i}\binom{len_i}{v_i})(\sum v_i)!(n-1-\sum v_i)!
$$
设哑元 $L(u^i)=i!(n-1-i)!$，根据线性性，原式：
$$
x\sum_{\{v_i\}}(\prod_{i=1}^{6}\binom{len_i}{v_i}(10^iu)^{v_i})\\=x\prod_{i=1}^{6}(1+10^iu)^{len_i}
$$
直接对同一类数求和，答案就是：
$$
\sum_{i=1}^{6}s_i\prod_{j=1}^{6}(1+10^ju)^{len_j-[j=i]}\\ans=\sum_{i=1}^{6}\sum_{k=0}^{n-1}s_ik!(n-1-k)![u^k]\prod_{j=1}^{6}(1+10^ju)^{len_j-[j=i]}
$$
具体求解可以先快速幂 $O(n\log^{2}{n})$ 求出，再除掉一个 $(1+10^{i}u)$，容易做到 $O(n)$。
时间复杂度就是 $O(n\log^2{n}+V(n+k)),V=6$。