^ 比赛时间 ^ 比赛名称 ^ 当场过题数 ^ 至今过题数 ^ 总题数 ^ 排名 ^
|2020-07-12| [[牛客多校第一场]] |  3  |  -  |  10  |266/1116|

**本地写完就上传，你看到这句话就知道我还没写完。。。**

**签到题：F,J**

链接：https://ac.nowcoder.com/acm/contest/5666

===== A B-Suffix Array =====

  * 题意:
  * 题解:

===== B Infinite Tree =====

  * 题意:
  * 题解:

===== C Domino =====

  * 题意:
  * 题解:

===== D Quadratic Form =====

  * 题意:
  * 题解:

===== E Counting Spaning Trees =====

  * 题意:
  * 题解:

===== F Infinite String Comparison =====

   * 题意:给你一个字符串$x$,定义$x^\infty=xxx\ldots$,即重复字符串$x$无数遍，现有两个字符串$a$,$b$，让你比较$a^\infty$和$b^\infty$的字典序大小 其中$1 \leq |a|,|b| \leq 10^5$,输入总字符串长度不超过$2\times10^6$,输入字符串全为小写字母
   * 题解:遍历输入的字符串并比较大小即可，但遍历时为了达到目的，当目前的字符串遍历结束后再从头开始。即采用string_a[i % string_a.size()]的形式达到节省空间并且遍历多遍的目的，但是对遍历的长度有要求，我们组直接将长度暴力到$1\times10^5+13$就过了

===== G BaXiangGuoHai,GeXianShenTong =====

  * 题意:
  * 题解:

===== H Minimum-cost Flow =====

  * 题意:
  * 题解:

===== I 1 or 2 =====

  * 题意:
  * 题解:

===== J Easy Integration =====

   * 题意:给你一个$n$,并记积分$\int_{0}^{1}\left(x-x^{2}\right)^{n} \mathrm{d} x$值为$\frac{p}{q}$,求$\left(p \cdot q^{-1}\right) \bmod 998244353$的值
   * 题解:积分直接积出来发现 $\int_{0}^{1}\left(x-x^{2}\right)^{n} d x=\frac{\Gamma(n+1)^{2}}{\Gamma(2 n+2)}$ 而$\frac{\Gamma(n+1)^{2}}{\Gamma(2 n+2)} = \frac{2(n+1)(n !)^{2}}{(2(n+1)) !}$。。。说实话我们组是找规律找的，当时积分不会算。。。

^n                                                  ^1            ^2             ^3             ^4              ^5               ^
|$\int_{0}^{1}\left(x-x^{2}\right)^{n} \mathrm{d} x$|$\frac{1}{6}$|$\frac{1}{30}$|$\frac{1}{40}$|$\frac{1}{630}$|$\frac{1}{2772}$|

而知道规律后就简单了由下面这个公式 $(\frac{p}{q}) \bmod k = \left(p \cdot q^{-1}\right) \bmod k = p\cdot q^{k-2} \bmod k$ 就直接算就可以了，这题也算签到题