叶子川 Math tricks

容斥原理

容斥的暴力方法是寻找条件，然后钦定这些条件不成立。

容斥的证明方法：

$\sum\prod p=\sum\prod(1-q)=\sum(-1)^{|S|}\prod_{i\in S}q_i$

AT_tokiomarine2020_e O(rand)

hhoppitree 有 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$ ，他想要从中选出至多 $k$ 个整数，使得它们的与为 $S$ ，或为 $T$ ，求方案数。

$n\le 50,a\lt 2^{18}$ 。

先筛掉一定不在答案里的，这样我们只需限制每位有什么，而不用限制没有什么。

暴力寻找条件，我们能找到 $36$ 个，你发现每位的 $q_i=\neg p_i$ 不会同时成立，所以暴力容斥是 $3^{18}$ 的。

发现我们只需限制那些既要求有 $0$ 又要求有 $1$ 的位置（其他位置都筛掉不合法的数，一定合法），所以直接把条件设为：该位不能完全相同。

这样只剩 $18$ 个条件了，直接容斥即可。

问题来了，怎么统计方案数？

其实只需要按照 $\rm and$ 上我们枚举的相同位划分为等价类，每个等价类都是一个组合数。

AT_dwacon6th_prelims_e Span Covering

有一个区间 $[0, X)$ ，你有一个数组 $L_1, L_2, \cdots, L_n$ 。对于每个 $i$ ，你可以选择一个整数 $j$ 满足 $0 \le j \le X- L_i$ ，并覆盖 $[j, j + L_i)$ 这个区间。问有多少种方案，使得整个区间都被覆盖，方案数对 $10^9 + 7$ 取模。

方案不同当且仅当存在一个纸带的左端点不同。

$ 1 \leq N \leq100, 1\leq L_i\leq X\leq 500 $。

条件显然是每个位置都被覆盖。

此时我们肯定不能枚举每个位置，考虑贡献的柿子，我们钦定了若干个位置不选，那么全局被划分成了一些能放纸带的连续段，设连续段的长度为 $l_1,l_2,\cdots,l_k$ ，则贡献为：

$(-1)^{k-1}\prod_{i=1}^n\sum_{l_j\ge L_i}(l_j-L_i+1)$

不难发现我们只需要关心 $l_j\ge L_i$ 的连续段（长度 +1）的和。

考虑生成可重集的方法：从大到小枚举每个数添加进去，如果你还需要枚举或记录加了多少数，这种方法通常都能比从小到大枚举让复杂度减少很多。

本题我们恰好需要关心比每个数大的数的信息，直接记 $f_{i,j,k}$ ，表示加完了 $[i,X]$ 这些长度，加了 $j$ 个段，段长和是 $k$ ，扫描到 $i$ 的时候计算所有 $L_s=i$ 的贡献，多次幂可以暴力算也可以 ksm，因为 $N\le X$ 。

复杂度分析是 $\mathcal O(X)\times\sum_{i=1}^X\sum_{j=1}^{[X/i]}\frac{X}{i}=\mathcal O(X^3)\times \sum_{i=1}^X\frac{1}{i^2}$ ，显然后者 $<\frac {\pi^2} 6$ ，是常数。

等量代换

也可以称作反演/容斥的本质，就是小范围复杂化（简单式子变成大的和式），然后交换求和号，化简。

P7324 [WC2021] 表达式求值

给定一个表达式树，每个非叶子节点是 $\min$ 或者 $\max$ 或者问号（可能 $\min$ 可能 $\max$ ），每个叶子节点是 $x_i,i\in[0,9]$ ，每次询问给出 $x_0\sim x_9$ 的值，问将所有问号填成 $\min,\max$ 后，所有情况下表达式的值的和。

$n,q\le 5\times 10^4$ 。

暴力思路： $10!$ 枚举大小关系，然后跑树形 $\rm dp$ ， $f_{i,j}$ 表示这个子树结果是 $j$ 的方案数。

考虑经典结论： $x=\sum_{i\ge 1}[i\le x]$ ，我们直接离散化成 $0/1$ ，求出 $0$ 的数量即可。

复杂度是 $\mathcal O(2^{10}n+10q)$ 。

另一问题（刚开始看错题了）：给定 $10$ 个数组 $b$ ，求出 $\sum_{x_i\in b_i}ans$ ，保证 $\sum|b|\le 5\times 10^4$ 。

仍然枚举每个间隔统计，系数就是每个变量的选择个数乘起来，这样甚至能做 $\sum|b|\le 10^6$ 。

随笔记录，表达式树代码：

int tg=0;
stack<int> st1,st2;
F(i,1,k) {
    if(s[i]=='(') {
        ++tg;
    } else if(s[i]==')') {
        --tg;
    } else if(isdigit(s[i]))  {
        s[i]-='0';
        st1.push(i);
    } else {
        while(sz(st2)&&Lv[st2.top()]>=tg) {
            int c=st1.top(),op=st2.top();
            st1.pop();st2.pop();
            rs[op]=c;
            st1.pop();st1.push(op);
        } ls[i]=st1.top();st2.push(i);
        Lv[i]=tg;
    }
} 
while(sz(st2)) {
    int c=st1.top(),op=st2.top();
    st1.pop();st2.pop();
    rs[op]=c;
    st1.pop();st1.push(op);
}
rt=st1.top();

[ARC163D] Sum of SCC

考虑一张竞赛图 $G$ ，其中有 $N$ 个节点，节点编号为 $1,2,\dots,N$ ，且 $G$ 满足：

对于 $G$ 中的所有边 $u\to v$ ，恰好有 $M$ 条边满足 $u<v$ 。

设 $f(G)$ 表示图 $G$ 中的强连通分量数量。请你求出所有满足条件的 $G$ 的 $f(G)$ 之和。

答案对 $998244353$ 取模。

$1\le N\le30$ ， $0\le M\le\frac{N(N-1)}2$ 。

结论：竞赛图缩点之后会变成一个全序关系，即一条链，每个左右关系都有左边连向右边。

我们不好数这条链，考虑刻画链的一个前缀，一定是左边的所有点连向右边的所有点，进一步发现这是一个双射（即左边和右边一定没有两个点在同一个 SCC 里面）。

所以就是数把图划分成两个集合的方案数，集合中的边没有限制，集合间的边都是 $A\to B$ ，为了避免算重我们钦定 $A$ 非空。

我们还需要关心 $u<v$ 的边的数量，考虑先求出集合间的边有哪些好边，剩下的边自己钦定，从小到大加入点即可， $f_{i,j,k}$ 表示加了 $i$ 个点，左集合大小为 $j$ ，集合间有 $k$ 条好边。

[ARC082E] ConvexScore

给定平面上 $n$ 个两两不相同的点，对于一个点集 $S$ ，如果该点集构成一个（面积 $>0$ 的）凸多边形（这个点集中不能有三点共线），那么设在它轮廓上或内部的点数为 $k$ ，它的权值就是 $2^{k-|S|}$ 。求所有凸多边形的权值之和。

$n≤200$ 。

把 $2^k$ 看作随便在内部选了一个点集。

随便取一个点集，显然它只会被统计 $0/1$ 次，且几乎总是被统计 $1$ 次（将该点集建凸包，内部作为一个子集被统计）。

不会被统计当且仅当所有点都共线，暴力枚举即可。

「PA 2022」Drybling Bajtessiego

给定 $n$ 个括号序列，对每个 $(i,j)$ 求出 $s_i+s_j$ 中本质不同合法括号子序列的数量。

$n\le 600$ 。

首先要会求一个串的本质不同合法括号子序列。

我竟然不会这个。

究极弱化：求一个串的本质不同子序列。

其实就是子序列自动机上跑（对每个子序列贪心匹配），如果再限定是合法括号就再记一维前缀和。

这样枚举 $i,j$ ，我们就会了 $n^4$ 。

考虑一下问题的形式：将子序列自动机视为一个 $\rm DAG$ ，拼起两个图的部分其实很少，任意一条路径要么终止于第一个图，要么跨过分界线，那么第一种我们在终点统计，第二种我们在分界线上统计。

考虑我们需要什么信息，首先要找到第一张图的最后一个点，为了避免它在第一个图上继续匹配，我们需要钦定下一个字符。

第二个图上的部分直接转置原理倒着转移即可。

空间复杂度太高了，我们要避免 $n^3$ 的空间，第一部分显然跑完 $\rm dp$ 后无需全部记录下来，只需要记录前缀和是多少、钦定下一个字符是多少。

非递归式整体二分

更接近本质的叙述。

每个询问维护一个 $[L,R]$ ，进行充分多次的整体值域扫描，我们会遇到 $\mathcal O(n)$ 个事件，即遇到一个 $\rm mid$ 就判断，遇到一个修改事件就修改，总复杂度 $\mathcal O(n\log V)$ 。

好处是避免了撤销，更清晰直观。