M_sea

TJOI2018简要题解
数学计算因为模数不是质数,所以并不能直接乘个逆元还原回去。事实上维护一棵线段树,每个位置表示该时间乘的值,每次修改...
扫描右侧二维码阅读全文
28
2019/06

TJOI2018简要题解

数学计算

因为模数不是质数,所以并不能直接乘个逆元还原回去。

事实上维护一棵线段树,每个位置表示该时间乘的值,每次修改直接修改对应位置上的数,查询就输出所有数的乘积即可。

代码

智力竞赛

读进来的时候先把 $n$ 加个 $1$ 。

那么就相当于可以用至多 $n$ 条链覆盖 DAG,求未被覆盖的点的点权最小值的最大值。

先考虑判 AK 的情况,发现我们要求一个 DAG 可重点最小路径覆盖。

这是一个经典的题目:先 Floyd 传递闭包,然后二分图最大匹配即可。

于是可以先直接判掉 AK 的情况。

剩下的就很简单了:二分答案,然后把点权 $<mid$ 的点拿出来二分图匹配,判断路径数是否 $\leq n$ 即可。

代码

游园会

戳这里

碱基序列

先把整个蛋白质建 SAM ,这样子就可以方便地求出每个子串的出现次数即匹配数。

考虑 DP 。设 $f[i][j]$ 表示前 $i$ 个氨基酸,匹配到了节点 $j$ 的方案数。

转移直接枚举可能的碱基序列即可。

最后答案就是 $\displaystyle\sum_{i=2}^{cnt}f[k][i]\times sz[i]$ 。

代码

异或

维护两棵可持久化 01 Trie,第一棵从 dfs 序的前一个转移,第二棵从父节点转移。

第一种查询直接在第一棵 01 Trie 上查询子树区间,第二种查询直接在第二棵 01 Trie 上查询 $u$ 到 $lca$ 、$v$ 到 $lca$ ,然后取 $\max$ 即可。

代码

教科书般的亵渎

设 $\displaystyle S(x)=\sum_{i=1}^xi^{m+1}$ ,那么要求的就是 $\displaystyle\sum_{i=0}^m\sum_{j=i+1}^{m+1}S(a_j-a_i-1)-S(a_{j-1}-a_i)$ 。为了方便我们定义 $a_{m+1}=n+1$ 。

把后面那个 $S$ 代进去,式子变成 $\displaystyle\sum_{i=0}^m\left(S(n-a_i)-\sum_{j=i+1}^m(a_j-a_i)^{m+1}\right)$ 。

$n-a_i$ 特别大,直接求显然是不行的。

注意到这是一个自然数幂和的形式,于是可以考虑斯特林数 于是可以考虑拉格朗日插值。

可以证明 $S(x)$ 是一个 $m+3$ 项式,那么直接求出前 $m+3$ 项然后 $O(m)$ 拉格朗日插值即可。

代码

最后修改:2019 年 08 月 14 日 08 : 17 AM

6 条评论

  1. yzhang

    根据数据范围来看a_i要开ll(

    1. M_sea
      @yzhang

      哪有 $a_i$ 的范围啊

  2. yzhang

    还有第一行j的上限应该是m+1吧

    1. M_sea
      @yzhang

      打错了

  3. yzhang

    教科书般的亵渎那题插值是O(m)吧,O(n)不早就炸了吗(

    1. M_sea
      @yzhang

      您说的是

发表评论