CF1924D
先考虑一个串的最长合法序列，维护一个栈，答案就是右括号加入时栈非空的次数。
我们看成从 \((0,0)\) 走到 \((n,m)\)，发现没被匹配的右括号个数就是 \(x-y\) 的最大值。
要想只有 \(k\) 个匹配，那么要和 \(x-y=m-k\) “相切”。
若 \(f(k)\) 表示穿过直线的方案数，答案是 \(f(k)-f(k-1)\).
考虑像算卡特兰数，在折线与 \(x-y=m-k\) 第一个交点处，将之后的折线关于直线翻转。
终点变成了 \((n+m-k,k)\)，方案是 \(C_{n+m-k+k}^k=C_{n+m}^k\)，
这里的方案与满足前面条件的折线都构成双射关系。
CF1930F
若只有两个元素我们来考虑做法，设它们为 \(a,b\)，我们假设最后是 \(a|x-b|x\).
每位贪心，对于第 \(i\) 位，有且仅有若 \(a=1,b=0\)，则这位取 \(0\) 时有贡献。
也就是 \(a|b-b\)，\(a,b\) 反过来就是 \(a|b-a\).
至于一个集合我们考虑枚举 \((a,b)\)，我们每加入一个 \(a\)，都考虑前面对其贡献。
若是 \(a|b-b\) 呢不好算，注意到 \(a+b=a|b+a\&b\)，所以就是 \(a-a\&b\).
只需要计算 \(a|b\) 的最大值和 \(a\&b\) 的最小值。按位贪心，每次查询是否存在 \(b\) 以 \(x\) 为子集。
这个暴力更新，记忆化搜索，是只有 \(O(n)\) 次更新的。
CF1943D2
考虑差分，然后选两个不相邻的数，前者 \(-1\)，后者 \(+1\)，这是个匹配问题。
我们考虑用前面的正数匹配后面的负数，那么对于每个 \(i\) 分别考虑，
若 \(-c_i\le \sum_{j\le i-2} c_j\)， 则 \(i\) 可以匹配前面剩下的。事实上，也就是 \(a_{i+1}+a_{i-1}\ge a_{i}\).
设 \(dp_{i,j,k}\) 表示考虑了 \(i\) 位，前两位是 \(j,k\) 的方案数，考虑用前缀和优化。
再优化考虑容斥，设 \(f(i)\) 表示钦定 \(i\) 个不合法，答案是 \(\sum_{i=0}^n(-1)^if(i)\).
设 \(dp_{i,j,0/1}\) 表示考虑了 \(i\) 位，上一位是 \(j\)，当前不合法个数的奇偶性的方案数。
若当前这位不钦定，那么 \(k\) 随便填，\(dp_{i,k,0/1}=\sum dp_{i-1,j,0/1}\)。
若钦定不合法，若是知道了 \(a_i,a_{i+2}\) 的值，\(a_{i+1}\) 取值范围就已知，
\(dp_{i,j,k}=\sum_{t=1}^mdp_{i-2,t,-k}\times (m-t-j)\)。前缀和优化。