jzoj 6302. 提高组

Description

详见OJ

Solution

对于(limit1,2)就是使序列(1~n)的排列。
对于(limit3)，我们可以将其看做是两个最长上升子序列正好覆盖整个序列，证明显然。
我们可以做一个前缀(max)序列。这样对于(max[i])，保证(max[i]>=i)。
而且保证(max[n]=n)。
如此，我们可以将问题转化成图。
那么我们可以将问题变成：
求从((1,1))到((x,y))再到((n,n))的方案数，途中不能触碰到(y=x-1)的直线（不能使(max[i]<i)）。
对于触碰到的方案数用题解说的翻折法即可。
预处理阶乘和逆元(O(n))，询问(O(1))。时间可过。

Code

#include <cstdio>
#define maxn 20000000
#define ll long long
#define mo 1000000007
#define mem(x, a) memset(x, a, sizeof x)
#define fo(x, a, b) for (int x = a; x <= b; x++)
#define fd(x, a, b) for (int x = a; x >= b; x--)
using namespace std;
int T, n;
ll x, y, jc[maxn + 10], ny[maxn + 10], ans = 0;

inline int read()
{
	int x = 0; char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x;
}

inline void swap(ll &x, ll &y) {ll t = x; x = y; y = t;}

ll ksm(ll x, int y)
{
	ll s = 1;
	while (y)
	{
		if (y & 1) s = s * x % mo;
		x = x * x % mo; y >>= 1;
	}
	return s;
}

ll C(ll x, ll y) {return x > y ? 0 : jc[y] * ny[x] % mo * ny[y - x] % mo;}

int main()
{
	freopen("tg.in", "r", stdin);
	freopen("tg.out", "w", stdout);
	T = read();
	ny[0] = jc[0] = jc[1] = 1;
	fo(i, 2, maxn) jc[i] = jc[i - 1] * i % mo;
	ny[maxn] = ksm(jc[maxn], mo - 2);
	fd(i, maxn - 1, 1) ny[i] = ny[i + 1] * (i + 1) % mo;
	while (T--)
	{
		n = read(), x = read() - 1, y = read() - 1;
		if (x > y) swap(x, y);
		ans = (C(x, x + y) - C(y + 1, x + y) + mo) % mo;
		x++, y++;
		ans = ans * ((C(n - x, n + n - x - y) - C(n - y - 1, n + n - x - y) + mo) % mo) % mo;
		printf("%lld
", ans);
	}
	return 0;
}