Problems	States
#6376. 卢卡斯定理	AC
#18403. 序列统计	AC
#4126. 吉夫特	AC
#18737. 组合数问题	IP
#240. Combination	AC
#3910. 超能粒子炮・改	AC
#16111. Perm 排列计数	AC

Problem. 1 Junior - Wasted

Template.

Problem. 2 Junior - Formula

$$\begin{aligned} \mathrm{ANS} &\equiv\sum_{i=1}^{n}{i+r-l\choose r-l} \\ &\equiv{n+r-l+1\choose r-l+1}-1 \end{aligned} \space(\operatorname{mod} p)$$

Problem. 3 Senior - Formula & Thinking

$$\begin{aligned} &\ \ \ \ \prod_{i=2}^{k}{a_{b_{i}-1}\choose a_{b_{i}}} \\ &\equiv\prod_{i=2}^{k}{\lfloor\frac{a_{b_{i}-1}}{2}\rfloor\choose\lfloor\frac{a_{b_{i}}}{2}\rfloor}\times{a_{b_{i}-1}\bmod2\choose a_{b_{i}}\bmod2} \end{aligned} (\operatorname{mod} 2)$$

式子后面的 $\dbinom{a_{b_{i}-1}\bmod2}{a_{b_{i}\bmod2}}$ 一共有四种情况，其中只有 $\dbinom{0}{1}=0$。其他都为 $1$。

意味着只要出现 $a_{b_{i}-1}\equiv0\bmod2$ 且 $a_{b_{i}}\equiv1\bmod1$ 的情况，整个式子就为零了。

结论：$\dbinom{n}{m}\equiv0\space(\operatorname{mod}2)$ 当且仅当 $n\operatorname{bitand}m=m$。

证明（也许不是特别严谨）：我们可以知道：

$${n\choose m}={\lfloor\frac{n}{2}\rfloor\choose\lfloor\frac{m}{2}\rfloor}\times{n\bmod 2\choose m\bmod2}={\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor\choose\lfloor\frac{\lfloor\frac{m}{2}\rfloor}{2}\rfloor}\times {\lfloor\frac{n}{2}\rfloor\bmod2\choose\lfloor\frac{m}{2}\rfloor\bmod2}\times{n\bmod 2\choose m\bmod2}=\cdots$$

我们发现：

$${\lfloor\frac{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor}{\cdots}\rfloor\choose\lfloor\frac{\lfloor\frac{\lfloor\frac{m}{2}\rfloor}{2}\rfloor}{\cdots}\rfloor}$$

这一坨，就是在一直进行二进制移位，$\operatorname{shr}1$。

那么我们可以得出一个结论：如果对于我们记 $(n)_{k}$ 表示 $n$ 在二进制意义下的第 $k$ 位。$(n)_{k}\in[0,1]$

那么对于 $\forall i$，有 $(n)_{i}=0$ 且 $(m)_{i}=1$，那么 $\dbinom{n}{m}\equiv0\space(\operatorname{mod} 2)$。

所以 $n\operatorname{bitand}m=m$，证毕。

我们题目要求的是最后算出来是个奇数，那么就不能存在 $a_{b_{i}-1}\operatorname{bitand}a_{b_{i}}=a_{b_{i}}$。

也就是 $a_{b_{i}}$ 为 $a_{b_{i}-1}$ 的子集。

接下来我们可以设计一个 DP，我们设 $f_{i}$ 为以 $a_{i}$ 为开头的答案。

那么转移就是加法原理：

$$f_{i}=f_{i}+f_{j},j\in a_{i}\wedge t_{j}>i$$

其中 $t_{i}$ 表示 $i$ 在序列中的位置。

时间复杂度由二项式定理可知是 $\Theta(3^{\log_{2}\max\{a_{i}\}})$。

Problem. 4 Senior - Formula

$$p=10^{9}+7 \\ \begin{aligned} &\ \ \ \ \sum_{i=0}^{n}\sum_{j=0}^{\min\{i,m\}}[k\mid{i\choose j}] \\ &=\sum_{i=0}^{n}\sum_{j=0}^{\min\{i,m\}}[k\mid{i\choose j}] \end{aligned}$$

Problem. 5 Junior - Wasted

Template.

Problem. 6 Junior / Senior - Formula

$$p=2333 \\ \begin{aligned}f(n,k)&\equiv\sum_{i=0}^{k}{n\choose i} \\ &\equiv\sum_{i=0}^{k}{\lfloor\frac{n}{p}\rfloor\choose\lfloor\frac{i}{p}\rfloor}\times{n\bmod p\choose i\bmod p} \\ &\equiv\sum_{i=1}^{p-1}\left({n\bmod p\choose i}\times\sum_{j=0}^{k}{\lfloor\frac{n}{p}\rfloor\choose\lfloor\frac{i}{p}\rfloor}[j\bmod p=i]\right) \\ &\equiv\sum_{i=1}^{p-1}\left({n\bmod p\choose i}\times\sum_{j=0}^{\lfloor\frac{k-i}{p}\rfloor}{\lfloor\frac{n}{p}\rfloor\choose i}\right) \\ &\equiv\sum_{i=1}^{p-1}\left({n\bmod p\choose i}\times f(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{k-i}{p}\rfloor)\right) \\ \end{aligned} \space(\operatorname{mod}p)$$

Problem. 7 Senior - Thinking

是个堆，于是 $f_{i}=f_{2i}\times f_{2i+1}\times{S_{i}-1\choose S_{2i}}$。