这个题怎么不直接取名
优秀的子序列中任意两个元素01位无交，这是一个标准的子集卷积形式
\(\varphi\) 的计算显然与 \(a_i\) 的卷积独立，可以线性筛/埃氏筛
可以暴力 \(3^{18}\) 过，枚举时为了避免重复可以通过强制枚举的数包含最高位的1
注意 \(a_i=0\) 要特殊处理
1 | bool Mbe; |
就是直接套集合幂计数的 \(\text{exp}\)
同样要特殊处理 \(a_i=0\) 的
1 | const int N=1<<18,P=1e9+7; |
相同边连接的点同一颜色，直接模拟即可
1 | namespace pt1{ |
相同边连接的点同一颜色，即在相同边构成的树上形成了若干联通块
很容易想到可以强制一些边保留，设保留 \(i\) 条边的方案数是 \(F_i\) ,则答案就是 \(\sum_i F_i\cdot y^{n-i}\)
考虑 \(dp\) 那些边相同，但是不好直接计算剩下边不同的方案，所以考虑计算最多有 \(i\) 条边相同的方案数，即
\[G_i=\sum_{j=i}C(j,i)F_j\]
二项式反演得到 \(F_i=\sum_{j=i}(-1)^{j-i}C(j,i)G_j\)
设分成了 \(m\) 个联通块，大小分别为 \(size_i\) ，则这些联通块随意构成树的方案数就是 \(n^{m-2}\cdot\prod size_i\)
根据上述性质可以写出一个简单的 \(O(n^4)\) 树形dp求得 \(G_i\) ，即 \(dp[i][j][k]\) 表示在 \(i\) 的子树里，有 \(j\) 条边相同，当前还剩下一个大小为 \(k\) 的联通块,每多转移一条相同边，系数是 \(\frac{1}{ny}\)
考虑优化 \(dp\)
联通块大小的问题，可以转化为每次在联通块里选择一个关键点的方案数， \(dp\) 第三维 \(0/1\) 表示当前联通块里是否已经选出了关键点
每次断开一个联通块时必须已经存在关键点
答案是
\(\sum_i F_i\cdot y^{n-i}\)
\(=\sum_i y^{n-i} \sum_{j=i}(-1)^{j-i}C(j,i)G_j\)
\(=y^n G_j\sum_{i=0}^j(-1)^{j-i}C(j,i)y^{-i}\)
发现右边的式子 \(\sum_0^j(-1)^{j-i}C(j,i)y^{-i}=(\frac{1}{y}-1)^j\)
那么直接把 \(\frac{1}{y}-1\) 带入作为保留一条边的转移系数，消去了第二维
那么这个 \(\text{dp}\) 可以被优化到 \(O(n)\)
\[ \ \]
1 | namespace pt2{ |
有了上面的 \(dp\) ，这一部分就简单多了，设分成了 \(m\) 个联通块，每个大小为 \(a_i\) ，则贡献为
\[\begin{aligned}\frac{n!\cdot a_i^{a_i-2}\cdot (n^{m-2})^2(\frac{1}{y}-1)^{n-m}(\frac{1}{n}^{n-m})^2\cdot a_i^2}{\prod a_i! m !}\end{aligned}\]
即枚举每个联通块生成树的数量，且需要考虑两棵树分别的联通块之间的连边数量，这一部分需要平方
很显然，可以直接对于 \([x^i]F(x)=\frac{1}{i!}\cdot (\frac{1}{n^2}\cdot (\frac{1}{y}-1))^{i-1} i^2i^{i-2}\) 这个多项式求exp得到
1 | const int M=1<<18|10,K=17; |
题面数据范围锅了导致枚举炸裂，写了正解却只有50分。。。。。。。
记限制涉及到的不同的点个数为 \(P\)
首先是不同的会被限制的个数 \(\leq 12\) ，所以应该直接枚举这些点的状态，枚举部分的复杂度是 \(O(2^P)\)
(然后我枚举了 \(p\) ，实际
\(p\leq 66\) 啊啊啊啊啊啊)
对于没有被限制的点，可以优先预处理出每个类型的答案，注意到 \(L=T-\sum s_i\leq 40\) ，则可以每次只取出长度为 \(O(L)\) 的这一部分，类型之间合并为 \(O(ML^2)\) 的复杂度
或许比较难的点是在于每种类型内的合并，注意到 \(w\in\{1,2,3\}\)
把每种 \(w\) 排序后，令 \(dp_i\) 为总权值为 \(i\) 的最小花费，同时记录最小花费时选取的三种 \(w\) 的个数，最优决策肯定是取最小的几个
每次转移，可以直接枚举选取的 \(w\) ，在排序好的数组上找到下一个最小花费
ps:事实证明，这个做法显然是假的，但是为什么就是没卡掉呢？正确的做法是先dp，w=1或2，再和3的暴力合并求出最大的 \(L\) 个值，这样的复杂度为 \(O(NL)\)
ps2:后来测试，这个错误做法在值域只有200的情况下，随机情况下，整个值域中的错误率只有1/1001/1000左右，而答案需要用到的部分又奇少，只有L个，于是乎，嘿嘿嘿嘿~
如果用这种邪教写法，预处理的转移复杂度就是 \(O(N)\) 的
每次枚举之后，把被改变的几个类型答案重新计算，重新合并，这一部分复杂度就是 \(O(PL^2)\) 的
算上 \(2^P\) 次枚举，得到总复杂度是 \(O(N+2^PPL^2)\)
题意：一个人在 \(k\) 维平面上，每一维范围是 \([1,W_i]\) 上的任意一个位置，初始可以在任何一个位置
这个人在空间上游走，每 \(n\) 步为一轮不断重复，每一步是一个方向上走-1或者1，求所有情况下 最后他离开空间范围的时间 之和
分析：
行走是循环的，每一维可以先看做独立，然后离开范围的时间就是每一维取 \(\min\)
求出每一维每一个位置离开的时间，然后 \(k\) 路归并得到答案，复杂度为 \(O((\sum W_i)k+nk)\)
容易想到根据循环来优化计算，但是如果以每一个位置为元素进行考虑，难以处理不同长度循环之间的合并
\[ \ \]
简单的计数方法的转换：
从初始位置离开的时间之和 = 前 \(i(i\ge 0)\) 步还未离开空间的初始位置个数之和
令 \(F_{i,j}\) 为 \(i\) 这一维 \(j\) 步还未离开的初始位置个数，则答案就是 \(\begin{aligned} \sum_{i\ge 0}\prod F_{i,j}\end{aligned}\)
此时观察发现除了第一轮需要特殊考虑以外，其它的 \(F_{i,j}\) 可以表示为 \(\max\lbrace0,F_{i,j-n}-D_i\rbrace\) (其中 \(D_i\) 为每一轮 \(i\) 这一维偏移的量)
对于前面 \(n\) (好像是 \(2n\) )个特殊考虑，后面对于每一个不同的 \(i\mod n\) 可以放在一起考虑，用一个统一的式子表示
然后计算就是类似 \(\begin{aligned} \sum_{i\ge 0}\prod (G_j-i D_j)\end{aligned}\) ，以 \(i\) 为元，所求的就是是一个 \(k\) 次多项式前缀和，也就是一个 \(k+1\) 次多项式的点值
暴力的方法就是 求出前面 \(k+2\) 项的值，然后用 拉格朗日插值/高斯消元 得到答案，复杂度为 \(O(nk^2-nk^3)\) (如果插值写好一点，复杂度主要受限于求值)
~~然后甚至可以无脑吸多项式做到 \(O(nk\log ^2k)\) ~~
求值时可以发现 对于 \(i\) 所求的 \(j\) 处点值的积式里面 最多只有一项和 \(i-1\) 不同，因而可以特殊考虑以优化求值复杂度
下面是 \(nk^2\) ，由于求值已经是 \(k^2\) 了，所以插值也没优化
1 | #include<bits/stdc++.h> |
题目大意：给定串 \(A\) , \(B\) ，求 \(B\) 中有多少本质不同的连续子段是 \(A\) 的子序列
\(n\leq 3000\)
暴力枚举 \(B\) 中的子段，同步维护与 \(A\) 的匹配指针 \(p\)
每次插入一个字符 \(c\) ，找到 \(A\) 中 \(p+1\) 之后第一个字符 \(c\) ，令匹配指针跳过去
可以预处理出这样的下一个字符 \(nxt_{i,c}\) ，完成 \(O(1)\) 匹配
除此以外，我们还需要对于本质不同去重
如果用 \(\text{trie}\) 树去重，需要开一个 \(\frac{n^2}{2}\cdot 26\) 的数组，面临着内存不够的问题
你可以信仰不开这么大
也可以去学习一下 \(\text{DAT(Double Array Trie)}\) 算法
也可以用 \(\text{hash+set/map/hash table/sort unique}\)
也可以用链表暴力存储trie树的情况，每次暴力for过去找儿子
这样内存均为 \(O(n^2)\)
以下是链表trie树的版本
1 | #include<bits/stdc++.h> |
倍增维护 \([x,x+2^d)\) 内部所有 \(b\) 的权值和 以及 \(a\) 的，用多项式表示
具体的，维护两个多项式 \(F_0(x),F_1(x)\) ，每次倍增的转移如下
\(F_0(x)\leftarrow F_0(x)+F_1(x+d)\)
\(F_1(x)\leftarrow F_1(x)+F_0(x+d)\)
因此暴力倍增复杂度为 \(O(nk^2)\) ，实现上需要记录每次倍增之后多项式与答案的前面部分相拼接需要额外的偏移
\[ \ \]
如果你输出多项式，就会发现，倍增 \(k\) 次之后，所有 \(a,b\) 位置对应的多项式就完全相同了
形式化地理解这个过程
一开始， \(F_0(x)=A(x),F_1(x)=0\) ，其中 \(A(x)\) 为读入的多项式
进行一次转移后， \(F_0(x),F_1(x)\) 的第 \(k-1\) 项只受到对方的 \(k-1\) 项和自己的 \(k-1\) 项影响
因此一次转移后 \([x^{k-1}]F_0(x)=[x^{k-1}]F_1(x)\)
下一次转移，第 \(k-2\) 项值只受到对方的 \(k-2\) 项，已经已经确定相同的 \(k-1\) 项影响
这个过程不断进行，第 \(i\) 次倍增会使得 \([k-i,k-1]\) 项相同
\[ \ \]
对于 \(k\) 次倍增之后，后面多出来的部分，可以直接求一个多项式前缀和，然后除2得到答案
多项式前缀和容易通过拉格朗日插值解决，复杂度为 \(O(k^2)\)
预处理前面的多项式复杂度为 \(O(k^3)\) ，求后面的式子为 \(O(k^2)\) ，预处理 \(n\) 的值复杂度为 \(O(\log n)\)
因此复杂度为 \(O(\log n+k^3)\)
\[ \ \]
1 | #include<bits/stdc++.h> |
考虑将所有加入 \(i-m\) 这些边的答案一起算出来
模拟删去点的过程容易发现，删去 \(u\) 时， \(u,v\) 在同一个强连通分量里的点满足：
存在仅包含 \(\ge u\) 的点的路径，使得 \(u,v\) 互相连通
设 \(A_{u,v}\) 表示最大的 \(i\) 使得 \(u\) 能仅通过 \(\ge u\) 的点到达 \(v\)
设 \(B_{u,v}\) 表示最大的 \(i\) 使得 \(v\) 能仅通过 \(\ge u\) 的点到达 \(u\)
计算 \(\min\{A_{u,v},B_{u,v}\}\) 即可确定一个点对能够贡献到的区间
考虑依次加入每一条边 \((u,v)\) ，在正反图上计算 \(A,B\) 中每个元素第一次被确定的时间
以计算 \(A\) 为例，每次会被更新的 \(A_{i,..}\) 一定满足
\(i\ge \min\{u,v\},i\rightarrow u,i\not \rightarrow v\)
可以暴力 \(\text{for}\) 这样的 \(i\) ，从 \([i,v]\) 开始，让 \(v\) 扩展，每次扩展找到未确定的 \([i,w]\)
每个元素只会被确定一次，复杂度为 \(O(n^2)\) ，暴力枚举起点为 \(O(nm)\)
可以用 \(\text{bitset}\) 优化到 \(O(\frac{nm}{64}+n^2)\) (扩展元素的部分复杂度可能是假的，但是没有关系)
1 | #include<cstdio> |
只是想要祭奠做的时候死去的我
约定下文中的 \(d\) 为题目中的 \(D\)
先从最最暴力的定义转移(可以跳过这个)
\(S\) 表示个数为奇数的颜色集合
转移多项式(集合幂指数) \(F(x)=\sum_0^d x^{\{i\}}\)
\(\text{FWT}\) 得到
\(F'(x)=\sum (d-2|S|)x^S\)
\((F(x)^n)'=\sum (d-2|S|)^nx^S\)
\(\text{IFWT}\) 得到
\(2^d F(x)^n=\sum_S \sum_T (-1)^{|S\cap T|}(d-2|T|)^n x^{S}\)
答案就是
\(2^d Ans=\sum_S\sum_T(-1)^{|S\cap T|}(d-2|T|)^n[|S|\leq Lim]\)
如果枚举 \(|S|,|T|,|S\cap T|\) 进行统计，会出现3个元，无法直接优化到 \(O(n\log n)\)
设最后得到每一种颜色的个数为 \(c_i,\sum c_i=n\)
方案数就是 \(\frac{n!}{\Pi c_i!}\) ，很符合指数型生成函数吧
考虑最朴素的生成函数表示法，考虑每种颜色的选的个数
个数无限制的生成函数 \(F_0(x)=\sum \frac{x^i}{i!}=e^x\)
个数为奇数的生成函数 \(F_1(x)=\frac{x^{1}}{1!}+\frac{x^{3}}{3!}+\cdots=\frac{e^x-e^{-x}}{2}\)
个数为偶数的生成函数 \(F_2(x)=\frac{x^0}{0!}+\frac{x^2}{2!}+\cdots=\sum \frac{e^x+e^{-x}}{2}\)
\(F_1^i=2^{-i}\sum (-1)^jC(i,j)e^{(i-2j)x}\)
\(F_2^i=2^{-i}\sum C(i,j)e^{(i-2j)x}\)
设选中 \(i\) 个奇数的答案为 \(G_i\)
\(G_i=n!C(n,i)[x^n]F_1^iF_2^{d-i}\)
\(=n!C(n,i)[x^n]2^{-d}\sum_j\sum_k C(i,j)(-1)^je^{(i-2j)x} C(n-i,k)e^{(n-i-2k)x}\)
代 \(e^{ax}=\sum \frac{(ax)^i}{i!}\) ，约去 \(n!\)
\(=C(n,i)[x^n]2^{-d}\sum_j\sum_k C(i,j)C(n-i,k)(-1)^j (n-2k-2j)^n\)
诶好像和Part1一样。。。
暴毙结束。。。。
上面这两种方法都要枚举三个元，无法优化，所以考虑先重复计算，再容斥掉
计算 \(\ge i\) 个方案数，然后容斥回去
设最终答案序列为 \(H\)
我们可以快速求出选中 \(i\) 个奇数且带重复的方案数 \(G_i\)
\(G_i=\sum C(j,i)H_j=[x^n]C(d,i)F_1(x)^iF_0(x)^{d-i}\) (强制选 \(i\) 个剩下未知)
\(G_i=C(d,i) \cdot n! \cdot [x^n]\sum (-1)^je^{(d-2j)x}\cdot C(i,j)\cdot {2^{-i}}\)
代 \(e^{ax}=\sum \frac{(ax)^i}{i!}\) ，约去 \(n!\)
\(G_i=C(d,i) \cdot \sum (-1)^j(d-2j)^n\cdot C(i,j)\cdot {2^{-i}}\)
卷积一次可以得到 \(G\)
最后的容斥就是二项式反演
\(H_i=\sum_{j\ge i}(-1)^{j-i}G_jC(j,i)\)
再卷积求出 \(H\)
首先我们考虑对于一个已经确定的 \(t\) 串，如何检查是否合法
对于 \(s\) 串建立 \(\text{kmp}\) ( \(\text{kmp}\) 自动机当然可以)，
如果当前 \(\text{kmp}\) 指针 \(j\) 在 \(\text{fail}\) 树上的祖先所对应的所有下一个位置 \(s[ancestor+1]\) 中，存在一个字符， \(t\) 中当前位置的字符 \(t[i]<s[ancestor+1]\)
那么就是存在一个"有意义的串",并且这个串和s串第一个不同的位置就是 \(ancestor+1\)
所以可以预处理一个 \(fail\) 树上祖先最大的 \(s[ancestor+1],Max[state]\)
1 | rep(i,1,n) Max[i-1]=s[i]; |
配合dfs枚举，可以拿到pts10
设状态转移为 \(Trans[state][c]\)
把kmp状态压进dp状态里
如果把问题直接放到无穷意义下来看
那么跑够长度之后，后面的任意加入 \(m\) 次字符都会构成一个循环
枚举循环开始状态为 \(st\) ， \(\text{dp}\) 走了 \(m\) 步回到 \(st\) 的方案数
如果计算合法方案数，那么还要多一维，所以直接计算不合法方案，也就是
\(Trans[state][Max[state]..25]\) 这一段转移是不会出现合法情况的
最后减一下
复杂度 \(O(m\cdot n^2)\)
1 | namespace pt2{ |
观察上面一档情况，合法的转移 \(Trans[state][Max[state]..25]\)
如果枚举下一个字符 \(c>Max[state]\) ，那么在 \(s\) 串中就找不到任何匹配了，下一个状态就是 \(0\)
否则，下一个状态就是 \(Trans[state][c]\)
也就是说，每个点出发其实只有两种情况，一种是一定会经过 \(0\) 的
所以对于这个环是否经过 \(0\) 进行讨论
如果不经过 \(0\) ，那么考虑直接从 \(st\) 出发走 \(m\) 步非0转移即可
经过 \(0\) 的，预处理一个从 \(0\) 出发，走了 \(i\) 步第一次回到 \(0\) 的方案数
\([st\rightarrow 0,0\rightarrow 0,0\rightarrow 0...,0\rightarrow st]\)
长成这个样子的转移
枚举第一个 \(st\rightarrow 0\) 的时间，后面可以预处理出来
复杂度 \(O(n\cdot m)\)
1 | #include<bits/stdc++.h> |
考虑一个合法的哈密顿路可以表示为什么样子：
按照不同树的编号，分割为一段段，相邻两段属于不同树
同时，如果最后一段和第一段同编号，将最后一段移动到第一段前面
由此，一个哈密顿路可以由唯一表示：
1号点在第一个段中，此后每一段和上一个属于不同树，且最后一段不属于1树
由此，问题分解为两部分：
考虑树形 \(dp\) 求解，每个点记录 \(dp_{i,j,0/1}\) 表示当前 \(i\) 子树内已经产生 \(j\) 条路径， \(i\) 自己是否可以向父亲连边
容易用类似树形背包的方式合并，每次决策儿子是否连接到自己上面
注意：一个长度 \(>1\) 的段，需要考虑正反方向的排放
复杂度为 \(O(\sum k_i^2)\)
\[ \ \]
相邻两段不同色，考虑容斥求解
枚举这棵树中的 \(i\) 个段自己生成了 \(j\) 个不合法的相邻， \(i\) 个段合并生成 \(i-j\) 个段，且乘上容斥系数 \((-1)^j\)
\(i\) 个并掉 \(j\) 个，方案数计算如下：
先把 \(i\) 个排好，乘上 \(i!\) ，然后选择 \(j\) 个间隔合并掉 \(\binom{i-1}{j}\) ，然后对于剩下的 \(i-j\) 个元素无序，需要除掉 \((i-j)!\)
背包合并容斥之后的结果，对于当前的 \(i\) 个元素，任意排列即可
然而上面是理想情况，还需要考虑 \(1\) 号元素不能被排列，要强制最后一个段不是1树的段
这一部分，在树1的容斥以及最终背包合并时特殊处理即可，即少排列一个元素，且最后合并时先选一个放在最后面
1 | #include<bits/stdc++.h> |