JOISC 2018 D 修行 (Asceticism)

标签: joimath

题意

给定 ,求有多少个 1-n 的排列 使得恰好存在 个不同的位置 满足

即是 Eulerian Number 单点求值。

解析

求一个这种排列的数量可以转化为求出现概率。而某种长度为 的排列的出现概率其实是可以转化为有 个取值为 的连续随机变量的,为两个连续随机变量相等的概率为 0,排列中两个值相等的概率也是 0,每一组随机变量的偏序关系都可以对应成一个排列。

要求刚好有 个满足 的不好解决,考虑求至多有 个,即令 表示小于 个位置满足 的概率,要求的答案就是

假设我们随机的序列叫作 ,令:

这个 是一一对应的,可以想象成有一个环,则这个 就是在环上 的步长。同时, 的值域和 一样,都是 。容易发现,如果 不超过 个位置满足那个条件,则有 。换句话说,我们要求的就是 就是找 的概率。

如何求 的概率呢?参考某一道叫作 Hyperrectangle 的题目。考虑一个 维坐标系,这个问题就转化为,有一个超立方体,从 ,与一个 的超平面,问这个超立方体被这个超平面切割后的体积与原体积(即 1)之比。如图:

hyperrenctangle

接下来考虑求这个被切割的体积。首先考虑没有这个超立方体的限制,令 表示在 维中 的体积。

当然还有一种比较感性的理解方法。我们要求 维中 的体积。令 ,即 的前缀和, 是一一对应的。由于和不超过 ,所以 可以取 的所有值,体积为 。同时,由于 ,故 是单调递增的,所以需要再除以 ,即

然后对于这个超立方体的限制,可以容斥。令 表示有 个坐标在 中, 个坐标在 中,满足 的体积。实际上,加上这个限制可以当作有 个坐标轴平移了 1 个单位,可以得到 。所以总的体积(概率)就是:

时间复杂度 ,这个 是快速幂。

实现

#include <iostream>
#include <vector>
#include <algorithm>

const int M = 1'000'000'007;

int pow_mod(int x, int y)
{
	int r = 1;
	while (y) {
		if (y & 1) r = (long long)r * x % M;
		x = (long long)x * x % M;
		y >>= 1;
	}
	return r;
}

int get_inv(int x)
{
	return pow_mod(x, M - 2);
}

int main()
{
	int n, k;
	std::cin >> n >> k;

	std::vector<int> fac(n * 2 + 1), ifac(n * 2 + 1);
	fac[0] = 1;
	for (int i = 1; i <= n * 2; i++) fac[i] = (long long)fac[i - 1] * i % M;
	ifac.back() = get_inv(fac.back());
	for (int i = n * 2; i > 0; i--) ifac[i - 1] = (long long)ifac[i] * i % M;
	auto binom = [&fac, &ifac](int n, int m)
	{
		return (long long)fac[n] * ifac[m] % M * ifac[n - m] % M;
	};

	auto f = [&fac, &ifac, &binom](int n, int k)
	{
		int res = 0;
		for (int i = 0; i <= k; i++) {
			int t = (long long)pow_mod(k - i, n) * ifac[n] % M * binom(n, i) % M;
			if (i % 2 == 1) res = (res + M - t) % M;
			else res = (res + t) % M;
		}
		return res;
	};

	k--;
	int p = (f(n, k + 1) + M - f(n, k)) % M;
	std::cout << (long long)p * fac[n] % M << std::endl;
}