_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

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

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

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

阅读全文 »

Description

给定小写字母组成的字符串 ss 及正整数 mm,求有多少小写字母组成的字符串 tt 满足 tt 的无穷重复中存在一个和 ss 长度相同但比 ss 字典序小的子串。

s,m2000|s|,m\leq2000
阅读全文 »

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

那么就会有很多问题,比如:

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

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

阅读全文 »

Description

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

  1. 给定 T1,T2T_1, T_2,求 yk(T1T2)y^{k(T_1\cap T_2)}
  2. 给定 T1T_1,求 T2yk(T1T2)\sum_{T_2}y^{k(T_1\cap T_2)}
  3. 给定 nn,求 T1T2yk(T1T2)\sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}

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

答案对 998244353998244353 取模。

阅读全文 »

Description

给定 nn 个长为 mm 的由 HT 组成的串(表示硬币的正反面)。

不停地丢一枚均匀的硬币直到硬币序列的最后 mm 位是 nn 个字符串之一为止。

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

阅读全文 »

Description

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

(k=0n(nk)f(k)xk(1x)nk)mod998244353\left(\sum_{k=0}^n\binom nkf(k)x^k(1-x)^{n-k}\right)\bmod998244353 n109,m2×104n\leqslant10^9,m\leqslant2\times10^4
阅读全文 »

Description

(1+2)n=en+fn2(1+\sqrt2)^n=e_n+f_n\sqrt2,其中 en,fne_n, f_n 都是整数。

再令 gn=lcmi=1nfig_n=\mathop{\rm lcm}_{i=1}^n f_i

给定 n,pn, p,求 (i=1nigi)modp\left(\sum_{i=1}^n ig_i\right)\bmod p

数据组数 T210,n106,2p109+7T\leqslant210,n\leqslant10^6,2\leqslant p\leqslant10^9+7pp 是质数,f1fnf_1\dots f_nmodp\bmod p 意义下不为 00

阅读全文 »

Description

有若干药瓶,第 ii 号药瓶里装着 gig_iii 号物质。

mm 次操作,第 ii 次会把 aia_i 号瓶子全部倒入 bib_i 号瓶子,之后 aia_i 号瓶子不会再用到。

一共 kk 对物质之间会反应生成沉淀(沉淀不再参与反应),1 克 cic_i 物质和 1 克 did_i 物质反应生成 2 克沉淀。

当有若干反应都可以进行的时候优先进行编号小的反应。求整个过程中一共生成了多少沉淀。

m<n2×105,k5×105m<n\leqslant2\times10^5,k\leqslant5\times10^5
阅读全文 »

Description

给出一棵 nn 个结点的树,要求给每个点一个正整数权值,使得相邻的结点的权值不相等,且最小化权值和。

n104n\leqslant10^4
阅读全文 »