A
使用动态规划，\(f_{i,j}\) 代表竖着的前 \(i\) 个，第 \(i\) 个被第 \(j\) 个横着的挡住的方案数，当然前提是有 \(l_j\ge i\)，否则 \(f_{i,j}=0\)。转移就是做一遍前缀和。
考虑优化，把前缀和写成 \(\frac{1}{1-x}\) 的形式，就可以拆成组合数了（这里用那个广义二项式定理）。显然我们是在给一个分段函数求前缀和，总共只会有 \(n\) 段，每段是在做多项式乘法，于是可以用 fft 在 \(O(n^2\log n)\) 的复杂度解决该问题。
B
经典问题，这里证明一下一定有解。
\(p=2\) 是平凡情况，这里不讨论。下面假设 \(p\) 是奇素数。记录把 \(n\) 个数分成 \(k\) 组，每组 \(t_i\) 个数的方案数是 \(C(n;t_1,t_2,…,t_k)\)。
反证法若不存在 \(p\) 的倍数，对所有取法求 \(p-1\) 次方之和，由Fermat小定理知这个值等于 \(C(2p-1;p,p-1)\)。又由Lucas定理知这个值在 \(\bmod p\) 意义下不等于 \(0\)。
用多项式定理展开 \(p-1\) 次方之和，发现这个多项式的任意项系数是酱紫的：\(C(p-1;t_1,…,t_k)C(2p-1-k;p-k,p-1)a_1^{t_1}a_2^{t_2}…a_k^{t_k}\)。根据Lucas定理这玩意是 \(p\) 的倍数，所以这个和是 \(p\) 的倍数，矛盾。
故存在一个集合的和是 \(p\) 的倍数。
这玩意叫Erdos-Ginzburg-Ziv定理。
关于构造，这有篇论文，https://arxiv.org/abs/2208.07728
C
建出acam后，对所有t跑到的节点建fail树的虚树，并在虚树的链上暴力跳。可以证明对fail树来说这复杂度是 \(O(L^{4/3})\) 的。
标签：11,前缀,题解,定理,倍数,多项式,Uoj,Round From： https://www.cnblogs.com/zcr-blog/p/16909813.html