Typical Party in Dorm
考虑对于一个子串 \(s[L, R]\)，在给定 \(S\) 的情况下判断会产生多少种回文串。
可以注意到，首先 \(S\) 需要包含某一个特定集合 \(T\)，然后会有 \(|S|^{cnt}\) 的贡献。
怎么做？对于每个集合维护 \(ccnt\)，\(\mathcal{O}(17\times 2^{17}\times n)\) 高维前缀和即可。
不会真是这个复杂度吧？
实际上 \(|S|\) 很小，对于每一种 \(|S|\) 直接做就行了，我傻逼了。
[CEOI2019] Amusement Park
设 \(f_S\) 表示将 \(S\) 集合内的边定向后形成 DAG 的方案数。
转移可以枚举最外层的点集 \(T\) 进行转移。但是有一个问题：这样会算重。
设 \(f(T)\) 表示最外层点集为 \(T\) 的方案数，我们枚举了 \(T\)，实际上算的是 \(\sum_{T\subseteq S}f(S)\)。
怎么办呢？考虑赋容斥系数 \((-1)^{|T|+1}\)。解决了。我操？
\(g(T)=\sum_{T\subseteq S} f(S)\Leftrightarrow f(T)=\sum_{T\subseteq S} g(S)\times (-1)^{|S|-|T|}\)。
\(\sum f=\sum g\times (-1)^{*}\)。原来如此。
怎么，会子集反演但只会子集反演？差不多得了。fjy666，你是傻逼吗？
不过也可以套基本容斥的式子。
[NOI Online #3 提高组] 优秀子序列
\(\varphi(a+b)\) 完全不能用正常方法维护。考虑计算出所有 \(\sum b_i=x\) 的方案数。
由于 \(\forall i\neq j, b_i\operatorname{and} b_j=\mathbb{0}\)，因此 \(\sum b_i=\operatorname{OR} b_i\)。
然后你会发现，相当于做 \(n\) 次子集卷积。你可以在值域上分治从而做到 \(\mathcal{O}(v\log^3 v)\)。好蠢。
好吧，题解一部分 \(\mathcal{O}(3^n)\)，一部分 \(\mathcal{O}(2^nn^2)\)，没有我的容身之地。
这里是对 \(\mathcal{O}(2^nn^2)\) 的口胡。本来值域分治就是不必要的，你只要做 \(\log\) 次合并就行了。
标签：log,sum,times,Escapee,mathcal,点集,subseteq From： https://www.cnblogs.com/fjy666/p/-/2024-June