原题传送门：>Here<

本来是不会去做Ynoi的毒瘤题的。。。

但是为了珂朵莉怎么都要做一下！！！

不过谁让我水平太差。。。其他的那些神仙题都不会，只能做这道了。

原题传送门：>Here<

做过家喻户晓的小凯的疑惑的人应该会熟悉一个性质，即两种互质钱币最大不能表示的数为$ab-a-b​$。

而我们发现一个非常好的性质：$c_ic_j\le 10000(i\ne j)$

设$v=gcd(c_1,c_2,\cdots,c_m)$，则所有$\ge 10000$的$v​$的倍数都可以被表示。

这时我们只需要考虑选出的菜的数量$\%v=i​$的方案数。

设$f=(100-p)+px$，我们对这个多项式做循环卷积，得到$f^n$，$f^n_i$表示的就是在$n$道菜中随机选，选出菜的数量$\%v=i​$的方案数。

这样答案就是$\sum_{i=1}^{v-1}f^n_i(v-i)$

题目大意：选择$[l,r]$中的若干数异或起来（也可以不选），问答案有多少种可能。

首先此题有一个$r-l\le 10000$的部分分很显然，只要把所有数丢到线性基里就ok了。

现在我们考虑正解。

我们发现当一个数可以被比它小的数表示时，就不需要加入线性基中。接下来我们考虑减少加入线性基中的数字数量。

我们发现对于两个相邻的数，$(2n)\oplus(2n+1)=1(n\in \mathbb{N})$。

所以我们找到$[l,r]​$中的第一个偶数（设为$x​$），则从$x+3​$开始的所有奇数都可以被表示为
$$
\begin{equation}
(y-1)\oplus(x)\oplus(x+1) \
=(y-1)\oplus1 \
=y
\end{equation}
$$
其中$y$为奇数。

这样在$[l,r]$的所有奇数中，只有$x-1$和$x+1$无法被这样表示。

以此类推，所有$\%4=2$的数也都是一样的：我们先找到第一个四的倍数$x$，然后把$x-2$和$x+2$加入线性基。

这样我们最多只需要加入$64\times 2$个数就ok了。

原题传送门：>Here<

我们考虑对原串反向建后缀自动机。这样后缀自动机上的每一个点表示的就是原串上的一堆前缀。

我们发现一个性质：这些前缀的排名必定是连续的。

我们考虑证明。

原题传送门：>Here<

看到这个数据范围，果断选择网络流。

我们发现消掉偶数点是没有意义的，所以问题可以转化为：

每消掉一个奇数点，需要消掉两个互为对角的偶数点。

我们看到每次消掉两个点，考虑可以使一个点连源点，另一个点连汇点。

所以我们的算法就是：

• 从源点向偶数行的偶数点连边；

• 从偶数行的偶数点向相邻奇数点连边；

• 从奇数点向相邻奇数行的偶数点连边；
• 从奇数行的偶数点向汇点连边。

同时为了维护费用，奇数点需要拆点。

（偶数点其实是不需要拆点的，然而我脑残了。。。）

原题传送门：>Here<

我们发现$f(i)=0$，当且仅当存在一对01满足01间的距离为$n-i$的倍数。这样就可以得到第4个部分分了。

我们考虑优化这个过程。

定义$A_i=[s_i=0]$，$B_i=[s_i=1]$。

现在我们想要使得

$$(A\times B)k=\sum{i-j=k}A_iB_j$$

我们考虑翻转$B$，即使得

$$B’i=B{n-i-1}$$

这样就变成

$$(A\times B’)k=\sum{n+1+i-j=k}A_iB_j$$

这样就OK了。

原题传送门：>Here<

定义$f$为$S$的生成函数。

则答案为

$$f^n_x$$

其中多项式卷积定义为

$$
(fg)k=\sum{ij\equiv k(mod M)}f_ig_j
$$

这个卷积比较难做。

我们发现出题人给了一个性质：$M$为质数。因此$M$必定有原根。

所以$1\cdots M-1$中的每一个数都可以被表示为原根的整次幂。

我们定义

$$g^{a_i}=i$$

$$f’i=f{a_i}$$

则卷积就变成

$$
{(f*g)k=\sum{i+j\equiv k(mod M)}f_ig_j}
$$

答案就变成
$$
{f’}^n_{a_x}
$$

原题传送门：>Here<

第一问

$prufer$序列乱搞即可，

$$ans={(n-2)! \over \prod_{i=1}^{n}(d_i-1)!}$$

原题传送门：>Here<

我们先考虑只求一个点时怎么做。

设$f_i$为$i$到叶结点的最短距离。

假设我们在处理$root$的答案。可以发现，

当$dis_{root,i}\ge f_i$时，$i$的子树只需要放一个人就可以“封锁”。

可以发现满足这个条件的点构成很多棵子树，而我们的答案就是子树的个数。

现在我们考虑怎么得到子树个数。

设$val_i=2-d_i$，其中$d_i$表示点$i$的度数。

我们可以发现，一棵子树的权值和正好等于$1$。

考虑为什么是这样。

设一棵子树中有$x$个点，那么有$x-1$条在子树内的边。所以贡献即为$2*x-2(x-1)=2$。因为我们求的是“子树”权值和，所以必有一条连出去的边。这样贡献即为$2-1=1$。

所以我们只要对于$dis_{i,j}\ge f_j$，将$ans_i$加上$2-d_j$即可。

这样复杂度是$O(n^2)$的。

考虑点分治。则对于$i$，满足条件的$j$满足$dis_i+dis_j\ge f_j$。

移项一下，得到$dis_i\ge f_j-dis_j$。后面那个东西用树状数组维护一下即可。

原题传送门：>Here< and >There<

我们首先考虑对给出的字符串建$AC$自动机。

考虑$AC$自动机上找子串的过程，我们发现一个点可以被达到当且仅当该点沿着$fail$向上走没有一个点是一个字符串的终点，且沿着$fa$向上走也没有。

我们把这些点挑出来，从$1$开始跑最长路。如果发现存在正环即必定有解，否则判断最长路是否$\ge L$。