雷姆的动态规划!

终于有雷姆了

P5774 [JSOI2016]病毒感染

考虑线性dp, $f_{i}$ 表示考虑了前i个镇的最小死亡人数,且钦点我停在i

转移枚举j, $f_i=\min f_j+cost(i,j)$

当我选择走到i再回到j进行治疗的时候:

你发现我们一定会让后面的人多被算两个时间段,所以不妨先剪掉

cost(i,j)=(j-i)*3*sum_n-sum_j+(j-i)*(sum_j-sum_i)+(2w_(j,i))

$w_{i,j}=\sum_{k=i}^j(k-i)*a_k$

这个数组要预处理,可以直接扫描线就是 $O(n^2)$ 的

而直接从i走过去显然比这个简单一些

$cost(i,j)=w_{i,j}-(sum_j-sum_i)$

P5301 [GXOI/GZOI2019]宝牌一大堆

~~qwqchang快乐题~~

国士无双直接特判, $13^2$ ,就是枚举哪一张牌选2张

七对子因为宝牌一样的原因相当于选最大的前七个权值的牌

剩下的和牌?

注意麻将一共136张牌,我们可以设计 $O(n^4)$ 级别的dp解决

$f_{i,j,k,l,0/1}$ 表示考虑了前i种牌,然后已经划分了j个杠子/面子,以i-1开始的顺子选了k个,以i开始的顺子打算选l个,有没有雀头的方案数QAQ

转移考虑第i种牌,必须有k+l个拿出来,组合数一下,然后以i开始的面子我们要考虑枚举一下选啥类型的,然后进行转移

比如,我们可以新开顺子/面子/雀子/杠子

但是你注意到这个杠子实际上就是多选了一个的面子,所以直接转移就好了...

而且我们甚至没有限制这个杠子的数量至少为1,有 $[3*4+3]$

就做完了

P3622 [APIO2007]动物园

注意到小朋友看到的范围很小,考虑状压相邻的信息

$f_{i,S}$ 表示考虑了前i个动物i向前5个的动物是否保留了的状态得到的最大值

那么我们会发现相当于转移每一个位置是否选择即可,然后找到 $i-5$ 位置的小朋友直接判断他是否高兴即可....

然后你会发现可以直接转移,但是当成环的时候就暴毙了

所以我们枚举 $N-5到 N$ 的动物的情况,然后再去做这个dp,就没有后效性了

时间复杂度是 $O(N*2^10)$

P2150 [NOI2015] 寿司晚宴

这也是个不错的trick吧qwq

考虑状压,但是你会发现会自闭,因为这个质数可能很大qaq

但是超过 $\sqrt n$ 级别的很少呢!一个数至多有一个

所以可以状压记录所有这个小因子有没有选入哪个集合, $3^{8}$ 差不多状压一下

然后把所有拥有其他因子按照那个因子的排序,然后同时处理相同的拥有那个因子所有数

$f_{i,j,k}$ 表示这样一段的前i个数然后选了小质因数S集合,至多k选了这一段的大质因子的方案数

首先f的初值应该是dp数组值,然后这一段的转移可能也和dp数组一样/jk

但是最后并入的时候 $dp_{i,S}+=f_{i,S,0}+f_{i,S,1}-dp_{i,S}$

因为我们会算重二者都不选的情况,所以最后要剪掉,没有二者都选的情况

当然也可以 $2^{16}$ 状压/cy

P4516 [JSOI2018]潜入行动

设计dp非常简单,还不如解时间复杂度

$f_{i,j,k,l}$ 表示以i为根的子树,选了j个点,然后根有没有被选上,根有没有覆盖的方案数

转移枚举后两维即可,然后直接转移qwq

注意这个复杂度是 $O(nk)$ 的!复杂度证明如下:

对于一次会产生 $k^2$ 的合并,我们必须要两颗子树的大小大于等于k,这样最多合并 $O(n/k)$ 次

对于两个小于k的合并,合并后小于等于k,都一定只会在LCA处算一次

如果只看贡献的话,你会发现其中一个点只会产生 $\sum =k$ 总贡献,因为一旦右边超过了就会

所以每个点最多产生O(k)的贡献,这样还是 $O(nk)$ 的

而合并后第一次大于k的合并显然每个点只会在祖先处被算一次,每次的贡献是 $O(k)$

P2481 [SDOI2010]代码拍卖会

$f_{i,p}$ 表示考虑了前i位,然后和mod p的结果是什么

你发现这个位数是 $1e18$

于是打开题解,有一部非常巧妙的转换:

假如我们有1111222333455666

可以写成下面几个后缀1相加的形式

1111222333455666
1111111111111111
0000111111111111
0000000111111111
0000000000111111
0000000000011111
0000000000000111
0000000000000000

于是问题变为用一些全是1的后缀来凑出一个 $\%p=0$ 的方案数qaq

$g_i$ 表示余数为i的后缀的方案数, $dp_{i,j,k}$ 表示考虑了前i种余数,凑出 $\%p=j$ 的和,选了k个后缀的方案数

可以直接转移了!我们枚举 $g_i$ 选几个对于所有状态转移即可,复杂度 $O(P^2100)$

问题怎么处理 $g_i$ ?

循环节!

你会发现对于 $1e1e18~mod~p$ 的值向前加上前一位的值跳

然后直到我们第一次跳到重复的位置为止,之后都会是一样的

因为是 $f_i=(f_{i-1}*10+1)\%p$

这个式子一定在2p长度会有循环节的时候

因为都是常系数,所以一定会存在循环节

变系数就不一定了QAQ

找到循环节后,把循环节进入前的算一下,然后进入之后的再直接得到,然后最后一点特判

变系数的递推式在系数循环的时候也能有循环节,否则没有,可以暴力枚举判断系数也相同的时候

P4170 [CQOI2007]涂色

区间DP

我的做法是对于区间 $f_{i,j,k}$ 表示区间 $[i,j]$ 都是颜色k,直接枚举子区间进行转移,如果整个区间都是目标区间了就返回这样子

然后复杂度也是 $O(n^4)$ 的

这样的决策足够充分...不需要特判边界

题解有 $O(n^3)$ 只考虑断中间点合并决策的做法

不妨设一开始单独染色每个不符合的位置

然后你会发现,我们可以按照一个顺序合并这些决策,对于区间 $[l,r]$

端点相同的时候,一定可以把左右端点的决策合并,所以 $f_{l,r}=\min f_{l,r-1},f_{l+1,r}$

否则我们左右端点决策不能直接合并,所以要两段区间求和,但是可以枚举这个可行的断点,然后进一步子区间的合并操作即可

本质是合并一个点的染色操作,而不是直接dp染色方案qwq

CF149D Coloring Brackets

这个还是挺妙的

我们考虑边界转移

$f_{l,r,p,q}$ 表示区间 $[l,r]$ 的颜色边界左边括号/右边括号颜色是 $p,q$ 的方案数

转移分类讨论

如果 $[l,r]$ 是匹配的括号

枚举一下两边哪个染色染什么颜色就好了,注意不能和边界染色相同

如果 $r=l+1$ ,此时两个括号一定可以匹配,所以直接根据 $p,q$ 染色求方案即可

否则 $[l,r]$ 并不是匹配的括号,但是他们一定是"()"的形式

所以从左括号的匹配位置(一定在区间内)划分开,变为两端区间,然后各自染色即可qaq

然后我们还要考虑划分的右边区间的情况,所以我们把左括号和匹配了的括号提前染色即可知道我们要染色的mid+1,r区间的限制了!

可能这样转移有些细节,但是是对的

P4342 [IOI1998]Polygon

这个咋做啊!

序列赋值两份,然后区间dp, $f_{l,r}$ 表示把区间 $[l,r]$ 合并在一起的最大收益??

显然是不行的,因为我们没法断开,所以考虑最后一次操作是什么

那么就转移枚举区间$[l,r$最后一次操作在哪里,然后直接转移就好了....

不难发现断开一个位置相当于赋值后序列长为n的区间

但是说这样是萎掉的,因为我们有负数mdzz,还有乘法....

也就是说我们可能两个最小值乘起来变成最大值

再设出一个区间的最小值

那么显然加法是最小值相加最大值相加

而乘法最大值的是最小值相乘/最大值相乘取max,最小值的是最小值相乘和小大值相乘取min

然后还是萎的,竟然有最大值小于0和最小值大于0的case.....

反正再把最小值和最大值相乘取max加进去就好了,都取max都取min才是关键把!

可能分别对应了正负号变号的case,有点难受啊

P3647 [APIO2014]连珠线

这个题有点眼熟啊

观察可知蓝线一定是相邻两端而且存在一个中间点,而且那个中间点只能被一个蓝线代表

设 $f_{i,0/1}$ 表示i是否是蓝线的中点的子树内最大价值

第二维为0时,我们可以任意转移, $f_{i,0}=\sum_{j \subset son_i}max(f_{j,0},f_{j,1}+w_x)$

但是第二维为1的时候,我们相当于选取优势最大的一个1,然后剩下的都只能是0

不难发现我们可以用 $f_{i,0}$ 的信息加速这个判断,就是 $f_{i,0}+max(f_{j,0}+w_j-max(f_{j,0},f_{j,1}+w_j))$

仔细思考你会发现中点的定义是严格向上的

如果不向上,就是一个儿子->父亲->儿子,此时会发现这个是不可能有多个情况存在的,否则按照这个生成方式会多根

做完了一个点为根的,考虑换根对于 $f_{i,0}$ 很好搞,走到哪个子树就剪掉哪个即可

对于 $f_{i,0}$ 直接做, $f_{i,1}$ 我们维护次大值如果向最大值子树走的就用次大值和 $f_{i,0}$

P5680 [GZOI2017]共享单车

首先简化版题面就是对于建立最短路径树后,支持整棵树翻转某些点的颜色,问某个点集其中颜色为1的点和K不连通的最小代价

先建立虚树,因为是多组询问局部问题

先将1作为根

然后考虑DP, $f_i$ 表示将i子树内所有关键点干掉的最小代价,有两种决策,割掉 $i->fa_i$ 这样的代价是这条边的长度,否则是所有儿子的长度求和,特别的,如果i是关键点,一定要割掉 $i->fa$ ,如果i是根,那么不能割掉父边!

然后虚树上DP即可汗...

CF979E Kuro and Topological Parity

只能从编号小向大的连是不能连出环的,但是这个n也太大了吧(雾)

外层DP:记录点的颜色,连边情况

内层DP:需要每个点拓扑排序dp中已知的路径数量/点的颜色/连边情况

如果我们随着连边的进行推进内层DP的话,说不定可以不记录

但是你发现这个是 $\%P=2$

也就是关键在于奇偶性

我们记录偶白偶黑奇白奇黑的点的数量mod 2的值

然后加入一个白色点,如果连接到偶黑,那么无论如何都会是偶数的,奇偶性不变

连接到偶白和奇白,不是黑白相间,路径条数奇偶性不变

奇黑点存在,我们可以挑出一个奇黑点来控制奇偶性,那么这个点作为奇白和偶白的方案数为 $2^{i-2}$

不存在奇黑点,自己算一个黑白相间,加入奇白

观察一下,你会发现对于新的白色点,因为我们只考虑黑白相间的路径增量的奇偶性,所以除了奇白和偶白都是随便的!也就是说我们只需要认识到总方案有 $2^{i-1}$ 种,剩下的就是随便啦

故我们方案数是对的

P4059 [Code+#1]找爸爸

考虑 $f_{i,j}$ 表示A的前i个字符和B的前j个字符匹配的最大相似程度

我们钦定状态 $f_{i,j}$ ,第i个字符和第j个字符处于两个字符串同一个位置!

转移考虑i是否和j匹配

如果i和j匹配,那么我们总有 $f_{i+1,j+1}<-f_{i,j}+d_{i,j}$ ,d表示这两个位置匹配的代价

然后如果i和j不匹配,我们要在i前面加入一个空格或者在j前面加入一个空格,分别对应 $f_{i+1,j},f_{i,j+1}$ 但是你会发现我们要计算加入空格的代价,因此还要记录两维 $0/1$ 表示最后一个位置前面是不是空格

如果是,相当于没有 $-A$ 的额外代价,否则我们需要 $-A$ 的额外代价每次成功匹配会让这一维度清空也就不难转移了

P2340 [USACO03FALL]Cow Exhibition G

我:这题感觉上就好妙啊!

题解:01背包

艹

智商看做容量,最大化情商之和即可

有显然的剪枝,两个都大于0的都选,和小于0的都不选

然后复杂度就是 $O(n^2V)$ ,离谱

就这样还有个老哥23ms搞过去了?

贪心牛逼啊

UVA12991 Game Rooms

$f_{i,j,0/1}$ 表示考虑了前i个数,然后最近的一个位置j放了0/1类型的建筑, $j+1到i$ 都是不同的建筑qwq,第二维一定小于这个i-1,如果第二维为0说明尚未修建

转移钦定i放什么建筑,如果和之前的相同,则i-1一定和之前的不同而且相近,先算出j~i位置的人向两边走的最小代价和只想j走的最小代价

但是有个问题,第二维为0这个没法处理,如果我们不妥善的分配dp值的话,有的状态不会成为最优然后自闭了QAQ

不过好像也可以,我们只把第二维不是0的当做合法状态,其他的当做一个起始状态,当我们开始转移的时候再就算上这个代价即可

$w_{i,j}$ 表示中间向两边走的代价,怎么处理?

枚举那个中间点,再枚举左端点,右端点总是和中间点对称,特殊判断偶回文串,这时候中间点建立在哪里都好qwq

题解给出了简单的二维设计dp的方式QAQ

$f_{i,j}$ 表示前i个建筑,最后一个建筑是类型j的最优代价

转移考虑枚举上一个不同的建筑,然后两边分中间的人

这样我们一定有半的人向前走到 $l-1$ ,有另一半向后走到 $r$

这个东西可以二阶前缀后缀和解决了

P3354 [IOI2005]Riv 河流

吐槽毒瘤,IOI2005就这个样子

转移的最大问题是不知道每个点子树内还要运送多少木料啊

此时我们有一个很妙的想法就是把每一个点的贡献强制先算好,而不是拖到后面再去算

你会发现点u他最多也就是在他祖先某处被搞掉了,那么我们就把搞掉他的祖先计入状态

有 $f_{i,j,k}$ 表示考虑了i子树所有点后,j是距离i最近的伐木场,然后子树内选了k个点的总代价

我们转移采取动态收取代价的方法,枚举一个子树v来合并,然后你会发现如果u不建立伐木场,则v和u都会运到u的第二维j算贡献

即 $f_{u,j,k,1}=f_{u,j,l,1}+f_{v,u,k-l,0}$

类似的我们也能推出 $f_0$ 的转移

然后最后的时候要单独考虑u号点运在哪里的贡献

这个直接加上去即可!

然后我们还要合并 $f_0,f_1$ 的信息!

因为我们最后要考虑的是u祖先建立在某一个地方的这棵子树最小代价,是不考虑u到底v建立不建立的,也很简单, $f_1$ 向 $f_0$ 转移一下即可

P3052 [USACO12MAR]Cows in a Skyscraper G

这个多简单啊!

$f_{S}$ 表示S集合都选完了的最小分组

然后转移考虑枚举一个空集然后选上这个空集次数加1就好了

P2566 [SCOI2009]围豆豆

射线定理:从某个点随意一个方向引一条射线,如果交点为奇数个则落在多边形内部

只会在端点处挂掉

虽然我感觉我举出了反例但是并不太懂

再考虑这道题怎么做吧!

上下左右都能够移动显然是不太妙的,我们搞掉其中一些信息,不妨射线选取向右的

$f_{i,j,S}$ 表示我们走到 $(i,j)$ 而且经过的每一个豆豆的射线奇偶性为S是否可行

转移枚举下一步怎么走,然后将对应的状态点亮

然后要注意我们只有从一个格子向下走的时候才会将这一行想做的都修改一次

所以直接dfs或者bfs即可

时间复杂度 $O(nm2^DD)$

P2337 [SCOI2012]喵星人的入侵

插头DP

很毒瘤的那种,我们考虑记录什么信息才能支持转移

路径,就是留给喵星人走的那种
炮台,包括轮廓线上那些位置选了,选了一共多少个了
障碍,即这个格子直接自闭

路径用上下和左右向两种,因此用0,1表示他们

然后炮台用2表示,障碍用3表示

但是你发现这样我们转移的时候路径可能有拐弯的情况,就完蛋了

我们这样记录状态:左括号为0,右括号为1,无插头为2,独立插头为3

我们独立插头表示障碍或者炮台,无插头表示平凡路径(不是上下插头的路径)

那么有这样子的转移

插头dp括号表示法其实就是((()))的样子,其中匹配成功的括号表示一个连通块

仔细观察题解代码,那么你会发现因为我们记录左右括号都是1/2,而炮台和通道之类的,另外开了一个变量记录信息??

也就是说,本题我们再转移路径的同时去转移这个插头信息,并且同时考虑这个格子放什么

也就是说我们记录所有格子填什么,记录插头类型两个都记录

这样可行的状态数不是乘起来的,开一个vector或者链表记录即可

P6280 [USACO20OPEN]Exercise G

不错的数学题

就和之前期望的border一样,本题会出现一个循环,就是一个环,长度为 $a_i$

那么我们有 $K=lcma_i$

于是考虑dp这样的K的总和,而且我们有 $\sum a_i= N$

又因为LCM相当于质因数指数取max,所以从每个角度质数考虑

$f_{i,j}$ 表示考虑了前i个质数,当前一共的和为 $j$ 的所有 $K$ 的总和是什么,转移考虑枚举一个 $p_i^k$ ,我们 $f_{i,k}=\sum {f_{i-1,j-p_i^{k}}}+p_i^k$

这样DP一下即可

注意如果我们允许1参与分组,直接输出 $f_n$ 就是答案

P4253 [SCOI2015]小凸玩密室

注意到有一个客观事实,就是我们点亮灯泡过程相当于一个dfs的过程,很阴间

如果钦定1先点亮,我们有转移方程

f_{i,dep}=\min (f_{l,depL}+f_{r,depR}+(depL+lenR)a_r+lenLa_L,f_{l,depL}+f_{r,depR}+(depR+1)a_l+lenRa_R),dep=depL=depR

这个是以一为第一个点亮的答案qwq,相当于合并时再计算根的答案

但是此时我们要能够以任何第一次点亮为根

再仔细思考一下,这种诡异的点亮方式,一定是点亮一个点x,然后以某种方式点亮一整颗子树,然后再点亮x的父亲,再点亮x父亲的子树,再点亮父亲的父亲....最后一直到根也处理完了

也就是说,是一个类似dfs的过程,而且是不能违背的

所以我们可以类似的统计答案,枚举一个点x第一次被点亮,然后 $ans+=dp_x$

紧接着从x子树中某个点向父亲跳一步,贪心的选取最小的那个就行了,然后再从父亲的子树向祖先跳一步,也是贪心选取最小的那个

这样做就好了时间复杂度是 $O(npoly(logn))$ 的

CF543D Road Improvement

明摆着让你换根呢

先考虑一个根的时候怎么做吧, $f_i$ 表示accessi子树内所有点到根的方案数

于是我们转移有对于

$f_u=\prod_{v \in son(u)}f_v+[E_v==1]$

$E_v==1$ 表示v这条边是挂掉的,如果挂掉显然有一种方案是v子树全清掉,然后只保留 $E_v$

其他方案都是清掉 $E_v$

然后我们考虑换根,显然根那一侧的影响很好消除,直接除去对应子树的这个即可

然后转移过来再用 $f_u$ 乘上根那一侧的方案数即可

果然我只会计数了!!😢

CF512D Fox And Travelling

果然我连计数都不会了!😞

首先不难看出去掉所有度数为1的点进行拓扑排序可以把原图分裂乘若干个有根树和若干个无根树,其中有根树的根是环上的一个点,无根树是任意的一个树qwq

有根树直接跑树形背包即可,无根树枚举每个点为根跑树形背包

然后你会发现任意一种选了i个点的方案会被算 $s-i$ 次,当且仅当其中某个点做根的时候不会被算重,否则一定会被算重了!

于是这样做完之后,我们把每棵树的方案数卷起来就是答案啦qwq

CF1146F Leaf Partition

计数题,抿了抿,不会了😢

$f_{i,0/1}$ 表示以i为根的子树,i是否有被某个连通子图覆盖的方案数

转移考虑当i没有被覆盖时

左右不能跨过LCA,那么就是 $f_{l,0/1}*f_{r,0/1}$

因为跨过左右本身是没有问题的,注意到我们要卷积,所以 $f_{u,0}*f_{v,0/1}$

当i有被覆盖的时候,应该两侧儿子都是被覆盖的状态,然后再把他们连接一下即可得到一种新方案

$f_{u,1}=f_{l,1}*f_{r,1}$

然鹅卷积的时候回出现问题,因为我们是至少要有两个连接

那么我们不妨用总方案数减去一个都没有连接的方案数

总方案数是左右合并可以连接也可以不连接??好像也行,但是不太聪明啊

于是我们打开题解

$f_{u,0/1/2}$ 表示u向儿子连接了0/1/至少2条染色边的方案数

于是转移考虑加入一个新儿子的方案

$f'_{u,0}=f_{u,0}*(f_{v,0}+f_{v,2})$

$f'_{u,1}=f_{u,0}*(f_{v,1})+f_{u,1}*(f_{v,0}+f_{v,2})$

$f'_{u,2}=f_{u,1}*(f_{v,1}+f_{v,2})+f_{v,2}*(f_{v,0}+f_{v,1}+f_{v,2})$

叶子我们要考虑父亲对于叶子的要求,则为 $f_2=2$

这样子转移一下即可,时间复杂度 $O(n)$

CF908G New Year and Original Order

$N<=1e700$

这提醒我们设计一个按照位数的dp做法,数位DP吧?

对于不到n位的数我们暴力填满0,那么我们相当于

$n=10000$

$S(1)=00001$

$S(10000)=00001$

然后考虑划分方案,如果不考虑上界的话,我们总能够有 $f_{i,j}$

表示前i位,然后我们当前划分到 $j$ 这个数位(最后一段是j),总共的数位和是什么

$f_{i,j}=f_{k,l}+g_{k,l}*cost(i,k,j)$

其中 $cost(i,k,j)$ 是这一段都放j的位和,g是方案数

我谔谔这个东西好像要考虑方案?然鹅方案数这个很毒瘤啊

因为你会发现对于排序后的结果,他的被计算次数是可重组合数qaq

题解告诉我们,限制数字固定为多少并不好球,但是限制数字大于等于多少很好求

我们不妨把贡献横着向上看,某一位为3的贡献就是这一位 $3>=1,3>=2,3>=3$ 产生的三次贡献

这样的好处是对于任意方案,他们的系数是相同的

$f_{i,j,k,l}$ 表示我们考虑了前i个数位,然后有j个数位满足贡献数字大小要大于等于k的方案数,并且有没有卡上界的方案数

转移,考虑下一位放什么数,如果放的是p,那么我们有

f_{i+1,j+p>=k,k,l \& (p>=a_i)} += f_{i-1,j,k,l}

于是我们dp到最后,对于每一个状态的贡献求和即可,即 $(f_{n,i,k,0}+f_{n,i,k,1})*10^i$

相当于我们对于一个数从下到上扫

P4229 某位歌姬的故事

怎么做啊QAQ

And segment提供给了我们这题的dp思路!

首先不难离散化,将所有区间变为左闭右开,然后一段就是一个点

然后我们要解决第一个问题,将所有限制放到每个点上,也就是说求出每个点最严厉的那个限制 $m_i$ ,即最小那个

这一步要 $Q^2$ 枚举区间判断合法性(有没有解)

能发现如果最高音高为 $m_i$ 那么限制不同的点他们也是不同的,因为假设我们从下到上考虑, $m_i$ 较小的点一定不会对于限制 $m_i$ 较大的点产生影响

也就是说 $m_i$ 较小的点的选择方案并不会影响 $m_i$ 较大的点,同理, $m_i$ 较大的点相当于不可能卡到上界消除限制,所以也不会对于小的点产生影响

所以我们要把所有 $m_i$ 相同的点拿出来,dp,乘起来

怎么解决这个呢?此时相当于两种颜色,和andsegment一样了

$f_{i,j}$ 表示考虑了前i个数,然后最近的j号位置防止了超过了 $m_i$ 的方案数

转移考虑第i个数怎么放,显然如果 $f_{i,j}$ ,当 $lim_i \leq j< i$

直接 $f_{i,j}=f_{i-1,j}*(m_i-1)^len_i$

而如果 $f_{i,j}$ 当j==i时,相当于这一段至少放一个黑点卡掉限制

$f_{i,j}=\sum f_{i-1,k}m_i^{len_{i}}-(m_i-1)^{len_i}$

这个系数相当于容斥qwq,总方案减去全不放的方案数

AT3963 [AGC024F] Simple Subsequence Problem

AGC牛逼啊QAQ

首先我们之前学过一个东西叫做子序列自动机

想法就是对于位置i,我们找到B串和A串的i位置第一个相同的位置,然后B的匹配位置跳到那个位置,然后A的串i++

这个东西最大的好处就是他的匹配过程是唯一的,因为是贪心匹配

按照这个匹配流程,我们如果可以计算出对于字符串i他总共在所有串中出现了多少次就能解决这道题了!

$f_{S,T}$ 表示我们考虑的串还剩下S的状态没有匹配,然后已经匹配了对方B,T的状态的总共多少个串

假如是状态 $dp_{00|110110101}$

那么你会发现如果我们下一位匹配一个1,转移到 $f_{001,10110101}$

否则匹配0,转移到 $dp_{000|110101}$

边界条件就是 $dp_{\emptyset|T}=1$ ,其中 $T \in S$

然后 $dp_{A|\emptyset}$ 就是A串出现的次数了!

最后我们暴力枚举 $2^{N+1}-1$ 种串看哪个大于K进行判断即可

时间复杂度是 $O(N2^{N})$

~~序列妙妙机~~

夏晓光(loveJY)的博客