网站首页 站内搜索

搜索结果

查询Tags标签: TJOI2016,共有 5条记录
  • [HEOI2016/TJOI2016]字符串 题解

    SA+二分+主席树 Statement \(q\) 次询问 \(s[a\dots b]\) 的所有子串和 \(s[c\dots d]\) 的最长公共前缀最大值 \(n,q\le 10^5\) Solution 其实感觉算不上黑题 看到 LCP,容易想到 SA,管都不管,先套一个 SA SA 套路二分答案,然后把 height 数组分组 设 \(l=\min\{i|hei…

    2022/4/4 23:19:40 人评论 次浏览
  • [HEOI2016/TJOI2016]求和

    题意 :设 \(S\) 是第二类斯特林数, 求 \(\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}S(i,j) \times 2^j \times j!\) 因为有 \(m^n =\sum\limits_{i=0}^{m}\dbinom m i i! \times S(n, i)\) 设 \(f(x) = x^n\), \(g(x) = x! \times S(n, x)\), 根据二项式反演 : \(f…

    2021/12/29 23:07:25 人评论 次浏览
  • [HEOI2016/TJOI2016]求和

    题意 :设 \(S\) 是第二类斯特林数, 求 \(\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}S(i,j) \times 2^j \times j!\) 因为有 \(m^n =\sum\limits_{i=0}^{m}\dbinom m i i! \times S(n, i)\) 设 \(f(x) = x^n\), \(g(x) = x! \times S(n, x)\), 根据二项式反演 : \(f…

    2021/12/29 23:07:25 人评论 次浏览
  • [HEOI2016/TJOI2016]字符串

    好神。 考虑到我们二分答案。 那么我们要做的是这样一个事情:判定s[c,d - l]在s[a,b]是否以子串形式出现过。那这是一个\(SAM\)的很套路的题目: 我们考虑到我们维护每个endpos集合的出现的子串,这个我们在\(link\)树上做线段树合并即可。 我们从表示\(s[1,b]\)的SAM节点…

    2021/8/30 23:09:35 人评论 次浏览
  • [HEOI2016/TJOI2016]字符串

    好神。 考虑到我们二分答案。 那么我们要做的是这样一个事情:判定s[c,d - l]在s[a,b]是否以子串形式出现过。那这是一个\(SAM\)的很套路的题目: 我们考虑到我们维护每个endpos集合的出现的子串,这个我们在\(link\)树上做线段树合并即可。 我们从表示\(s[1,b]\)的SAM节点…

    2021/8/30 23:09:35 人评论 次浏览
扫一扫关注最新编程教程