1 背包
1.1 解法一
发现输入是一个数，那么尝试打表。
打几个小数的答案就很容易发现了：Ans=N(N+1)(N+2)/6
1.2 解法二
考虑生成函数，我们写出这8 种物品的生成函数：
- 1.肥宅快乐水:f(x)=1+x
- 2.大盘鸡:f(x)=1+x+x2
- 3.啤酒鸡:f(x)=1+x+x2 + x3
- 4.鸡翅:f(x)=1/(1−x2)
- 5.鸡汤:f(x)=x/(1−x2)
- 6.鸡块:f(x)=1/(1−x4)
- 7.鸡腿:f(x)=1+x
- 8.鸡蛋:f(x)=1/(1-x3)
那么将上面八个多项式乘起来，xN 的系数就是答案了，
随手一算，得到Ans(x)=x/(1 − x)4
因为我们是求系数，所以我们需要展开，有：
Ans(x)=x(1+x+x2 +...+x∞)4
从组合意义推导一波，可以得到(1+x+x2 +...+x∞)4 的第N项系数就是将N分成四个无序自然数的方案数，那么就可以得到答案是N(N+1)(N+2)/6了。
2 划分
考虑分治，假设我们当前考虑区间[l,r]。我们设f[0/1][0/1][x]表示：
•区间开头选A[l]还是B[l]•区间结尾选A[r]还是B[r]•在这个区间中，一共选了x个A[i]的方案数容易发现，我们可以将f[0/1][0/1]看成一个关于x的多项式。那么一个区间的答案就可以用4个多项式表示了。显然对于长度不大于2的区间，是可以直接写出这4个多项式的。考虑合并区间：
我们先求出[l,mid]和[mid,r]（注意，是[mid,r]）的多项式，设左边的多项式是fl，右边的是fr。我们定义多项式加法就是对应位置相加。那么我们的转移就类似一个2× 2 的矩阵乘法。
不过有一个小细节：
如果矩乘的时候，中介变量（就是fl[i][k]× fr[k][j]里面的k)取的是0的话，要将这个多项式（即fl[i][0]× fr[0][j]）先乘(1/x)，再加到答案里（这是因为中间的A[mid]会被算到两次）。
最后的答案就是[1,2N]这个区间的4个多项式中xn 的系数的和。因为出题人太良心了，没有卡DFT的次数，所以时限开的非常宽。
3 子串排名
3.1 题解
因为后缀自动机一个结点代表的字符串是长度连续且互为后缀的，所以可以想到一个性质：
对于一个字符串S，我们建立S的反串S′的SAM，那么SAM里的一个结点代表的字符串的反串（即在原串中的方向）在所有S的子串中的排名是一个连续的区间。
那么我们如果我们能够给SAM的结点排序的话，就能够用结点序表示出T串了，询问的时候就二分（这里还要知道right集合的大小）就好了。其实求出结点序很简单，我们考虑fail树，如果一个点x有两个儿子
（如果有多个，不妨只考虑两个），分别是u和v，如图：
那么u和v结点代表的最短字符串都是x结点代表的最长字符串加一个字符，而且u和v加的字符不同（因为如果相同的话这两个结点就不会分开了），如图：
那么我们从fail树的根（空字符串）开始按顺序遍历整个fail树，就可以得到结点序了，具体而言，只要在遍历一个结点儿子之前给这个点的儿子根据之前所说的添加的字符排序（这个可以通过预处理一个结点在原串中的任意一个出现位置得到），之后按顺序遍历即可。
3.2 小结
总结一下具体流程：
- 1.对反串建SAM。
- 2.通过遍历fail得到每一个点的right集合大小，以及每一个结点在原串中的一个出现位置。
- 3. 再次遍历，得到结点序。
- 4. 每次询问的时候，二分定位到结点，再次二分（这个二分可以省略）定位到是这个结点代表的那个字符串，输出对应字符。
这道题运用了许多后缀自动机的性质，能够加深同学对后缀自动机的理解，不失为一道好题。
做了这道题，你就可以通过反串SAM来建SA了（实测比dcs倍增快）。
全部评论
(0) 回帖