把之前编的一道好玩的题重新发一下：
一条直线上存在 0 到 （n-1） 总计 n 个点。某时刻一个粒子停在 k 处，在下一时刻，它以 1/4 的概率向左移动到 （k-1），以1/4的概率向右移动到（k+1），以1/2的概率直接跳到0 （如果移动会导致粒子超出边界则不进行移动）。 科学家发现，存在这样一个概率分布 m， 如果按照m（i）的概率将粒子放在i处，那么在下一时刻粒子出现的位置的分布仍符合m。给定n和p，求 m(p)/m(n - 1). （提示 m(x)/m(n - 1) 是整数，O(log(n - p))可以求出）。
粒子位置变化符合马尔可夫链。根据Markov Chain Tree Theorem 见 https://en.wikipedia.org/wiki/Markov_chain_tree_theorem
我们可以建立这样一个图：如果i可以在一步内转移到j，则在两者之间建立一条有向边，边权为概率乘4（这样全是整数），那么在稳定分布下，出现在某个点处的概率正比于所有根为该点的有向生成树的边权乘积之和。找规律可知，这个数列符合f(n) = 4f(n - 1) - f(n - 2). 转化为矩阵快速幂即可在对数时间上界内求出。
一条直线上存在 0 到 （n-1） 总计 n 个点。某时刻一个粒子停在 k 处，在下一时刻，它以 1/4 的概率向左移动到 （k-1），以1/4的概率向右移动到（k+1），以1/2的概率直接跳到0 （如果移动会导致粒子超出边界则不进行移动）。 科学家发现，存在这样一个概率分布 m， 如果按照m（i）的概率将粒子放在i处，那么在下一时刻粒子出现的位置的分布仍符合m。给定n和p，求 m(p)/m(n - 1). （提示 m(x)/m(n - 1) 是整数，O(log(n - p))可以求出）。
粒子位置变化符合马尔可夫链。根据Markov Chain Tree Theorem 见 https://en.wikipedia.org/wiki/Markov_chain_tree_theorem
我们可以建立这样一个图：如果i可以在一步内转移到j，则在两者之间建立一条有向边，边权为概率乘4（这样全是整数），那么在稳定分布下，出现在某个点处的概率正比于所有根为该点的有向生成树的边权乘积之和。找规律可知，这个数列符合f(n) = 4f(n - 1) - f(n - 2). 转化为矩阵快速幂即可在对数时间上界内求出。