Tiny Counting

题目描述

给定长度为 $n$ 的数组 $S$,下标为 $1∼n$,你需要统计有多少个四元组 $(a,b,c,d)$ 满足:$1 \leq a < b \leq n; 1 \leq c < d \leq n; S_a < S_b; S_c > S_d$,且 $a,b,c,d$ 互不相等。

思路

首先我们预处理每个点前后比它大 / 小的数字数量,同时计算所有的顺序对和逆序对个数,令答案为两者之积,然后把出现重复数字的四元组从答案里删去。

代码

Medium Counting

题目描述

这里你需要解决一道中型计数题——关于捉摸不定的字典序。

有 $n$ 个字符串,分别记为 $S_1,S_2,⋯,S_n$,它们由小写字母和 $?$ 组成,你需要给每个 $?$ 都填上一个小写字母。

你需要统计,有多少种不同的给 $?$ 填上字母的方法,使得对于每个 $i \in [1, n-1]$,$S_i$ 的字典序严格小于 $S_{i+1}$ 的字典序。

思路

⾸先把每个字符串在末尾补 0 使得它们等⻓,接着令 $f_{l,r,p,c}$ 表示只考虑 $S_{l\cdots r}$ 从第 $p$个字符开始的后缀,若要填上其中所有的 $?$ 且保证字典序,且要求第 $p$ 位⾄少为 $c$ 的⽅案数。
第⼀种转移是我们考虑更⼤的 $c$,即转移到 $f_{l,r,p,c+1}$。
第⼆种转移是每次我们枚举 $mid\in [l,r]$,令 $S_{l\cdots mid}$的第 $p$ 位都为 $c$,则可以转移到 $f_{l,mid,p+1,0}\times f_{mid+1,r,p,c+1}$,如此转移直到 $mid==\max len_i$,$l==r$ 为⽌。

代码

Huge Counting

题目描述

有一个定义在 k 维非负整点上的函数 $f(x_1,x_2,\cdots,x_k): N_0^k \rightarrow {0,1}$,定义方法如下:

若存在 $j \in [1,k], x_j = 0$,则 $f(x_1,x_2,\cdots,x_k) = 0$
若对于 $j \in [1,k]$ 都有 $x_j = 1$,则 $f(x_1,x_2,\cdots,x_k) = 1$
否则 $f(x_1,x_2,\cdots,x_k) = \sum_{j=1}^k f(x_1,x_2,\cdots,x_{j-1},x_j – 1,x_{j+1},\cdots,x_k) \mod 2$
现在给出 $k$,并对每一维坐标给出区间 $l_j,r_j$,求:

$$\sum_{x_1 \in [l_1,r_1], x_2 \in [l_2,r_2],\cdots, x_k \in [l_k,r_k]} f(x_1,x_2,\cdots,x_k)$$

思路

我们先观察这个式子:$f(x_1,x_2,\cdots,x_k) = \sum_{j=1}^k f(x_1,x_2,\cdots,x_{j-1},x_j – 1,x_{j+1},\cdots,x_k) \mod 2$。如果不考虑 $\mod 2$,结合 $f_{1\cdots 1}=1, f_{0\cdots 0}=0$,发现这个式子计算的是从 $(1,\cdots ,1)$ 走到这个点的方案数,这个点的值取决于方案数的奇偶性。为了方便讨论,我们将每个点的每个维度的坐标向原点移动一个单位。我们知道,在 $k=2$ 的时候,对于点 $(x,y)$,方案数为 $\binom {x+y}{x}$。对于高维的情况,从原点走到点 $(x_1,x_2,\cdots ,x_k)$ 的方案数为:

$$\prod_{i=1}^{K-1} \binom{\sum_{j=i}^{k}x_j}{x_i}$$

现在我们考虑如何判断 $\binom {n}{k}$ 的奇偶性。有一个结论是,如果 $k\in n$,那么它就是奇数。回到上面的式子。由于维度可以互换,则答案中必含有因子 $\binom {x_i+x_j}{x_i}$。所以我们可以认为,使 $f_x = 1$ 的必要条件是对于 $1\leq i \neq j \leq k$,有 $x_i\in x_i+x_j$。

我们可以进一步证明它是个充分条件。若这个条件满⾜对于任意位都最多只有⼀个 $x_i$ 在这⼀位上为 $1$ ,那么对于任意维度⼦集 $S\in [k]$,有 $\sum_{i\in S } x_i \& x_k = x_k$,于是每个因⼦都是奇数。

有了这个条件就可以数位 DP 了。记录当前位置和每⼀维是否到达上界,枚举当前位是否为 $1$,有的话在哪⼀维上。

对于 $l_i \neq 0$ 的情况,按维容斥。令 $count(x)$ 表示从原点到点 $(x_1,\cdots,x_k)$ 的计算结果,那么答案就是 $\sum_{\text { p positions of } x_i \text { equal to the } l_i-1 \text { at the same positions }} -1^p \cdot count(x)$。

代码