这里是牛客多校Day1的补题
赛场回顾
一共就过了FJ两题……丢人.jpg
F
题意
题目大意是给出两个字符串$A$和$B$,都可以进行无限循环拓展成$AAA…$和$BBB…$,求他们字典序大小比较。
做法
一开始猜想是最坏情况到$lcm(a,b)$这一位才会出现不同($a = |A|$,$b = |B|$),但是这个想法是错的,根据 Periodicity Lemma 也就是 周期引理,若在第一个$a+b-gcd(a,b)$中所有字母都相同,那么这两个字符串相同。
这样就直接暴力了
代码
1 | void solve(){ |
J
题意
对于给定的$n$,要求出 $ \int_{0}^{1} (x-x^2) \; dx \; \% \; 998244353$
做法
这题的做法嘛,说出来有点丢人。当时手推这个公式找规律发现是
这里要学一波反演
然后就没有然后了,默默算几项然后oeis找终极公式
然后就是简单的阶乘打表,求逆元。
对于数学好的人可以分部积分得出以下过程(我推不动)
究极公式有了,就简单了
代码
1 | ll frac[2*N+5]={0}; |
从现在开始这里叫做辰寿补题广场
不行叉姐的题目太难了补不动补不动溜了