CSP2019 题解

代码早晚会有的。

这篇 Blog 里我会继续介绍 Typed Lambda Calculus 相关，包括 Denpendent Type 和 Lambda Cube 等，会稍微提一下 PTS；之后解释 Lambda-Cube 在 CH 同构意义下对应什么样的逻辑系统。

大概从这篇 Blog 开始会写一系列学习笔记，以 Type Theory 为中心写一些学习时的问题和得到的解答，也可能会作为半科普or入门读物。术语的中文翻译基本上都是从 Software-Foundation 那里看来的。

在此感谢 千里冰封 耐心解答我的问题。

作为第 0 篇 Blog，这里是科普文章。求 dalao 轻喷。

最近两天，有感而发，遂书“杂记（贰）”以记录脑海中 OI 之片段，抒发心中所想。

从不知道什么时候开始就没有写过游记，回忆什么的；来到 thu 预科，这两天也闲了起来，又受 LCA 建议（LCA 说要了解一下 OIer 们），于是决定写一篇杂记，记录一下我还能回想起来的一些东西，以及随便写点东西。

虽然这篇文章叫做 “ 杂记（壹）”，但我也不知道以后会不会有“（贰）”或者更往后的东西了——或许我会逐渐把以前 OI 时的想法忘掉，或者也可能会咕咕咕了。

也不知道该写什么，想到什么写些什么算了。感觉也组织不起目录结构，就当作文写吧。我甚至连一些事情发生的前后关系都不记得了，写这篇文章的时候还查了好几次日期。另外这篇文章中可能提到了一些之前不想说的东西，就当我公开出柜了吧。反正也不是什么秘密了，应该已经有很多人知道了吧。

Description

给定小写字母组成的字符串 \(s\) 及正整数 \(m\)，求有多少小写字母组成的字符串 \(t\) 满足 \(t\) 的无穷重复中存在一个和 \(s\) 长度相同但比 \(s\) 字典序小的子串。

\(|s|,m\leq2000\)。

在 OI 中会用到很多生成函数运算…比如求逆（本文中均指乘法逆，而非复合逆）、\(\exp\)、\(\ln\)、牛顿迭代、微积分、拉格朗日反演等。

那么就会有很多问题，比如：

1. 求逆（指乘法逆），\(\ln,\exp\) 等生成函数运算在什么时候有定义？
2. 这些运算为什么满足我们所期待的性质，如 \(\ln\exp A=A,\exp(A+B)=\exp A\cdot\exp B\)？
3. 如果你了解过一些（分析意义上的）级数，你可能还会疑惑为什么会存在 \(\sum_n n!x^n\) 这种东西（因为它只在 \(x=0\) 时收敛）…

归根结底，我们所疑惑的关键在于：为什么可以对这些东西做这些运算？

Description

对于两棵树 \(T_1, T_2\)，定义它们的交 \(T_1\cap T_2\) 是它们的边集的交形成的森林，\(k(T_1\cap T_2)\) 表示这个森林的连通块个数，求下列三种问题之一：

1. 给定 \(T_1, T_2\)，求 \(y^{k(T_1\cap T_2)}\)；
2. 给定 \(T_1\)，求 \(\sum_{T_2}y^{k(T_1\cap T_2)}\)；
3. 给定 \(n\)，求 \(\sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}\)

其中 \(n\leqslant 10^5\)，上面的 \(\sum\) 都是对所有可能的 \(n^{n-2}\) 种树求和。

答案对 \(998244353\) 取模。

Description

给定 \(n\) 个长为 \(m\) 的由 H 和 T 组成的串（表示硬币的正反面）。

不停地丢一枚均匀的硬币直到硬币序列的最后 \(m\) 位是 \(n\) 个字符串之一为止。

对每个串求最后以它结尾的概率。\(n,m\leqslant300\)。

Description

已知 \(m\) 次多项式函数 \(f\) 在 \(0,1\dots,m\) 处的取值 \(f(0),f(1),\dots,f(m)\)，给定 \(n,x\)，求

\[\left(\sum_{k=0}^n\binom nkf(k)x^k(1-x)^{n-k}\right)\bmod998244353\]

\(n\leqslant10^9,m\leqslant2\times10^4\)。