abc390又没ak

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

数组上二分，找到对应下标加上就好了。

关键代码：

CPP

//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

f(L,R)

即统计

A[L,R]

中的数字连续段个数。

我们直接统计有多少个

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

。

文章操作