数据范围容易想到利用矩阵进行计算。

考虑 f(k) = (A, B) ,其中 A 表示恰好等于 k 的路径条数, B 表示小于等于 k 的路径条数。则可以这样转移: (A, B) \times (C, D) = (A \times C, B + A \times D)

需要注意的是,对长度为 L 的路径对答案的贡献可以表示为一个二次多项式(即 f(L) = L ^ 2),转移时不能直接计算,而需要记录一次项和常数项系数。注意多项式乘法时需要乘上组合数。

READ MORE

P(S) 为钦点 S 中所有元素都在 1 之后挂掉的概率,显然:

P(s) = \frac{a_1}{sum(S) + a_1}

于是我们可以发现最后答案为:

ans = \sum\limits_{S \in [2, n]} P(S) (-1)^{|S|}

于是分治 + NTT 即可。

至此除斗地主外的所有 PKUWC 2018 题目已经订正完毕,祝也去参加 PKUWC 的读者和自己 RP = +\infty qwq!

READ MORE

考虑 Min-Max 容斥,\min(S) 表示至少一个从 s 走到至少一个属于集合 S 的点的期望时间。

f(i, S) 表示集合 Si 到任意 u \in S 的期望时间,则 \min(S) = f(s, S)

f(i, S) = \begin{cases} 0 &(i \in S) \\\\ \frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S) \end{cases}

可通过高斯消元求出,但复杂度过大不能接受。 考虑把原式化为 f(i) = k_i \times f(father_i) + b_i 的形式,推导过程略。 对于每个查询状压处理 \max(S) 不现实,需要处理出子集卷积即可 AC 。

READ MORE

Min-Max 容斥:

\max(S) = \sum\limits_{S' \subseteq S} \min(S') (-1)^{|S'| - 1}

可以用二项式反演证明:构造容斥函数 f(x) 使得

\max(S) = \sum\limits_{S' \subseteq S} \min(S') f(|S'|)

考虑每个 S' \subseteq S\min(S') = a_{x+1} 对答案的贡献为:

g(x) = [x = 0] = \sum\limits_{i=0}^x {x \choose i} f(i+1)

二项式反演得:

所以:

\begin{aligned} \max(S) &= \sum\limits_{S' \subseteq S} \min(S') f(|S'|) \\ &= \sum\limits_{S' \subseteq S} \min(S') (-1)^{|S'| - 1} \end{aligned}

READ MORE

之前特别喜欢那种动态博客,因为它能够提供一种更加简洁直观的编辑页面,而不是像 Hexo 一样,要从一堆 .md 文件中找出自己需要编辑的那个。

当然, Hexo 下这个问题也不是无解,所以这篇文章就来简单的介绍下在 Hexo 的文章管理插件。

首先先要明确一下自己的需求:

  1. 界面好看,颜值高

  2. 能通过文章标题来检索文章而不是 markdown 文件的文件名

  3. 能够快捷的调整文章的日期、标签等设置

在 Github 上搜索 hexo admin ,我找到了一下几款插件:

  • hexo-admin
    • 优点:功能齐全,一键部署
    • 缺点:界面难看,有些时候会有些卡顿?(个人感觉)
  • hexo-local-admin
    • 装不起来,略
  • hexo-hey
    • 优点:界面好看,响应速度快
    • 缺点:不支持 Latex (不过这个问题我们马上解决),不能一键部署?

综上,我选择了 Hexo Hey。

安装

参考官方文档的 README.md 即可,并不难。

不要忘记去配置 _config.yml

使用前小修改

虽说界面好看,但还是有些我个人觉得反人类的小问题,比如:

  • Markdown 源码编辑框不是等宽字体

  • toolbar 的文字没有居中对齐?

  • sidebar 宽度太小,有些文章的标题太长显示不下...

  • 右侧预览的 margin 太少,看起来十分拥挤

所以自己加了点 CSS ,利用 Stylus.

pre, code {
    font-family: Menlo !important;
}

md-toolbar span.ng-scope {
    display: none;
}

md-sidenav {
    width: 600px !important;
}

.markdown-body {
    margin: 60px !important;
}

MathJax 公式支持

your-hexo-path/node_modules/hexo-hey/www/index.html 下粘贴以下代码

<script type="text/x-mathjax-config">
MathJax.Hub.Config({
    tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    }
});

MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';
    }
});

function funcDemo(){
    window.setInterval("MathJax.Hub.Typeset()", 500);
}

window.onload = funcDemo;

</script>

<script async src="//cdn.bootcss.com/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML"></script>

由于不会检测 markdown 文件发生改变时渲染,所以默认是每隔 0.5s 重新渲染一次。

已知的小问题

分类和 tag 修改后无法保存...

↑ 好吧只是窝不会用...