多串匹配，考虑 A C AC AC自动机。
因为 2 t 2^t 2t个串是独立的，所以算出一个的概率乘上 2 t 2^t 2t就好了。
设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i个位置，走到 A C AC AC自动机上 j j j这个节点，模式串的出现次数是奇数的概率，设 f [ i ] [ j ] f[i][j] f[i][j]为总概率。
设 c n t [ i ] cnt[i] cnt[i]为模数串在 i i i节点代表的节点中出现次数的奇偶性，那么转移时枚举这一位是什么字符，乘上对应的概率。
并且因为要求是奇数，所以转移完要看看如果某个节点的 c n t cnt cnt为1，也就是说走到这个节点就会让奇偶性改变，那么概率取反，也就是用总集 f [ i ] [ j ] f[i][j] f[i][j]减掉不合法的 g [ i ] [ j ] g[i][j] g[i][j]。
同时，因为转移可以写成矩阵乘法的形式，所以我们可以提前把概率的矩阵做一下K次幂，因为矩阵乘法具有结合律。
同时因为对前两个点这样的话跑不过，需要数据分治一下。
第一个点直接就AC自动机匹配就好了，第二个点瓶颈在于矩阵乘法，不过发现只会出现数字1，那么我们只需要把不是1的压成一块就好了。
#include把文本串在AC自动机上跑，走到一个点就给这个点到根的路径权值加1，那么每个点的权值就是出现次数。
可以想到建出所有走过的点的虚树，那么一条虚路径的权值是相同的。
那么我们就是要求 c n t × w cnt\times w cnt×w的 k k k的值。
二分答案，对于每个链单独判断，因为 c n t cnt cnt是相等的，所以就是求
w
≥
⌈
a
n
s
c
n
t
⌉
w\geq \lceil \frac{ans}{cnt}\rceil
w≥⌈cntans⌉
的个数，用主席树维护就好了。
#include
}
}
int account(int mid)
{
Ans=0;
getans(1,mid);
return Ans;
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
read(v[i]);
Extend(i);
}
Build();
while(m--)
{
scanf("%s",s+1);
int len=strlen(s+1);
int k;
read(k);
K=0;
int p=1;
for(int i=1;i<=len;i++)
{
int c=s[i]-'a';
p=tr[p][c];
h[++K]=p;
tim[p]++;
}
Extract();
getsiz(1);
int l=1,r=1e9,mid,ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(account(mid)>=k)
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
getclr(1);
printf("%d\n",ans);
}
return 0;
}
官方题解太神了，写了个较劣的做法。
首先建出AC自动机，设 F [ x ] F[x] F[x]为 x x x到根的路径上经过的字符串的集合，用 b i t s e t bitset bitset存一下。可以在建AC自动机的时候存出来。
设 G [ x ] G[x] G[x]为 t x t_x tx的子串集合，这个只需要把这个串在AC自动机上跑，然后求经过所有节点的 F F F的并就行了。
询问可以直接合并两个bitset。
时间复杂度 O ( n 2 + n m + n q w ) O(\frac{n^2+nm+nq}{w}) O(wn2+nm+nq)可以冲过去，但是空间不太行。
考虑把 n n n分块，每块分别处理，这样空间就变成了了 O ( n + m B w ) O(\frac{n+mB}{w}) O(wn+mB)
在空间保证的情况下B可以取大点。
#include考虑把匹配看成在 A C AC AC自动机上走，那么就是强制不能匹配任何一个串，也就是说不能走到任何一个祖先链上有结束节点的点。
那么询问的就是最短路，答案为 Y e s Yes Yes可以看成无法到达，也就是最短路为正无穷。
设 f [ c ] [ x ] [ y ] f[c][x][y] f[c][x][y]为把 c c c字符变异后从 x x x走到 y y y的最短路。
考虑怎么求，我们用类似SPFA的方式转移，一开始把字符0和1放入队列里。
使用迭代来更新，每次用一个当前队首的字符c来更新其他的，那么只有当c存在于某个字符x的b序列里时，x才可能被更新，因此枚举出现过x的某个突变 o o o。
考虑用这个突变来更新其他的
f
f
f
。
枚举一个起点 S S S,设 d p [ i ] [ x ] dp[i][x] dp[i][x]为考虑了突变序列的前i个位置，S到x号节点的最短路。
转移时简单的，
d
p
[
i
+
1
]
[
y
]
=
m
i
n
(
d
p
[
i
]
[
x
]
+
f
[
b
[
i
]
[
x
]
[
y
]
]
)
dp[i+1][y]=min(dp[i][x]+f[b[i][x][y]])
dp[i+1][y]=min(dp[i][x]+f[b[i][x][y]])
所有的转移完了后看一下有没有某个值被更新了，如果被更新了，那么就把当前字符入队。
复杂度看起来很玄学，但是跑的还挺快的。
#include显然是数位dp，先差分一下。
建出 A C AC AC自动机，那么出现了长度大于 ⌊ d 2 ⌋ \lfloor \frac{d}{2} \rfloor ⌊2d⌋的子串，当且匹配时仅当经过了AC自动机上深度大于这个限制的点。
那么状态就很简单了。
设 d p [ i ] [ 0 / 1 ] [ 0 / 1 ] [ x ] dp[i][0/1][0/1][x] dp[i][0/1][0/1][x]表示填了前 i i i个位置，是否卡上界，是否已经经过了符合的点，走到了AC自动机的某个点的方案数。
转移是简单的。
同样的因为我们只需要支持子串匹配，SAM也是可以的，就是能走就走，不能走就跳。
因为某些原因写的是SAM的版本。
#include前置知识： D i l w o r t h Dilworth Dilworth定理。
可以看一下P4298 [CTSC2008]祭祀
匹配关系也是一种偏序关系。
建出AC自动机，然后把有子串关系的节点连边，那么就会有一个DAG，我们要找出最长反链。
建边可以用路径压缩，详情看代码。
剩下的就是上边的那个题里。
输出方案真恶心。
#include对串长根号分治，
若 s k s_k sk长度大于根号，那么可以对每个 k k k分别做。
把 s k s_k sk经过的点权值加一，那么一个串的出现次数就是子树和。
可以提前预处理一下。
差分一下再扫描线就好了。
小于根号的话，我们把答案拆成两个的差，然后扫描n个串，给每个串的子树加，询问暴力遍历就好了。
用分块平衡复杂度可以做到
O
(
n
n
)
O(n\sqrt n)
O(nn)
#include