比赛地址：http://jzoj.net/senior/#contest/home/2827

Forging

题面

考场

本来可以第一次考场上 $A$ 题，结果卡空间！我开了 $ll$ 就炸了！ $int$ 就过了！而且他还卡常数。。（我用 $cout$ 他最后一个点就 $T$ 了。）//终于可以考场正解一起写了。

首先理解一下题意，就是两个相邻级别的剑合在一起，有 $p$ 的概率成功合成更高一级的剑，有 $1 - p$ 的概率变成较低级别的剑，就相当于较高的剑没了。发现这个东西 $DP$ 是搞不定的，因为他有后效性而且还要有一个无穷的极限。这个就好像就要推式子。？

先看看部分分吧：

特殊性质？ $p = 1$ ？

那概率不就是 $1$ ？好了 $40pt.$ 到手，直接递推 $f_i = f_{i - 1} + f_{i - 2}.$

$n = 0$ ？

那不就是 $a$ 吗。

$n=1$ ？

好像就必须推式子了。先试试吧。

$f_0=a+(1-p)a+(1-p)^2a+(a-p)^3a…$ //解释一下就是直接到自己，失败一次回到自己，失败两次….直到无穷。

$<=> f_0 = \sum_{i = 0}^{\infin}(1-p)^ia$

$<=> f_0 = \frac{a}{p}$

这个就很好看了。

然后同样的考虑 $f_1=a+\frac{a}{p}$ 因为有 $1-p$ 的概率要损失一个所以类似上面的一个求和可以得到这个式子。那这个部分分就好了。

$n\leq1e7$ ？

这个由上面的推导就容易了。可以类似的发现这个式子： $f_i=f_{i - 2}+\frac{f_{i - 1}}{p}.$ 因为损失的是上一个。

然后就可以递推了。但是 $1e7$ ？逆元要线性推了。

但是：

出分： $0pt…MLE…$ 空间！不能开 $long long!$ 不能开 $long long!$ 不能开 $long long!$ 开了就炸了！

其实时间也要卡一卡不过还好。//比下一题好多了。。

$code:$ https://paste.ubuntu.com/p/4Rr2YVXMZS/

Division

题面

考场

看完题发现看数据范围可能可以分一个一个质因数来做，但是怎么合起来呢？岂不是要求一个并？？不知道。先看看部分分吧。

前四个点好像可以直接暴力。（其实第三个点数据太多了 $A$ 不掉，而且第二个点也没过。）

第五个点？ $n==2$ ？手动因式分解发现只可能有两个，然后手动讨论情况。然后 $WA$ 了。。

出分： $20pt.$

正解

没错！就是一个一个做再合起来。这里考虑一下一个叫中国剩余定理的东西来看怎么合。

中国剩余定理说的是：如果有若干个互质的数为模的同余方程的话，他们的通解可以表示每个同余方程的解乘上其他所有的数除自己模数外的模数之积和其逆元，再加上若干倍的所有模数之积。

代数表示如下：

对于 $c$ 个同余方程：

$\Large (S)= \begin{cases} x\equiv a_1(\mod p_1)\\ x\equiv a_2(\mod p_2)\ \quad.\\\quad.\\\quad.\\x\equiv a_c(\mod p_c)\\ \end{cases}$

满足 $gcd(p_1, p_2,…,p_n)=1$ 则有：

记 $P=\prod p, \quad P_i=\frac{P}{p_i},\quad inv_i\times P_i\equiv 1(\mod p_i)$ 则：

通解为： $X=\sum_{i = 1}^{c} a_iP_iinv_i+kP$

为什么呢？可以考虑上面的 $X$ 的每一项 $i.$ 把包含 $a_i$ 的一项分离出来的话，其他项里面是有一个 $P_j$ 的，它里面一定包含了 $p_i$ 所以被 $p_i$ 整除。而 $a_i$ 这一项本身是余 $a_i$ 的，因为 $P_iinv_i$ 再模 $p_i$ 意义下是 $1$ 所以方程就成立了。

这个有什么用吗？当然。考虑用我们的每个方程替换上面的方程，那么解就一定能够用下面的通式表示。每一个解都可以去表示，而我们每一个方程可以算出来有 $cnt_i$ 个解，那么乘法原理答案就是 $\prod cnt$ 了。好了！解决了！

那么就一个一个暴力试吧。还有一个问题，因为数据有 $50$ 组并且每组复杂度 $5e5$ 总的就是 $2.5e7$ 但是我们还要求一个 $x^m$ 呢？快速幂就直接 $T$ 了啊。。怎么解决？

一个新的神奇的东西：线性（欧拉）筛。

这个东西可以解决几乎所有积性函数的线性求前 $k$ 项的值。怎么做的呢？

类似很久以前学的筛素数的欧拉筛，就是每个数再最小质因子的地方被标记。那这个的意思呢？就是每个数对应的积性函数值再最小质因子的地方被计算！这样就只需要再所有质数的地方计算一次值，其他地方直接用之前的和最小质因子更新就好了。

具体实现很简单：

for (int j = 2; j < val; ++j)
{
    if (!book[j])
        pr[++cnt] = j, f[j] = cal(j);//在质数的地方计算一下。
    for (int k = 1; k <= cnt && j * pr[k] <= val; ++k)
    {
        f[j * pr[k]] = f[j] * f[pr[k]];//其他地方直接乘起来，因为是积性函数。
        if (j % pr[k] == 0)
            break;
    }
}
复制

然后还是要卡常。往死里卡。再加 $O2,O3$ 优化。然后经过 $12$ 次的卡常 $+$ 调试终于 $A$ 了。

$code:$ https://paste.ubuntu.com/p/3fqt7SGcQn/

Money

题面

考场

一看。哎呀不是 $LCT$ 吗？哎呀没学过。看部分分。

$10pt.$ 直接暴力。

$30pt.$ 直接暴力 $+$ 倍增。

后面就不会了。

然后倍增没调出来。

出分： $10pt.$

正解

没错就是 $LCT.$ // $log^2$ 的

但是其实还有倍增的做法可以 $A$ 掉。//还能一个 $log$ ！？

咕。

Forging

题面

考场

特殊性质？p=1p = 1？

n=0n = 0？

n=1n=1？

n≤1e7n\leq1e7？