温州网站建设温州网站制作,福州网站制作维护服务,网站后台程序开发,外国优秀设计网站Description 详见OJ Solution 对于\(limit1,2\)就是使序列\(1~n\)的排列。 对于\(limit3\)#xff0c;我们可以将其看做是两个最长上升子序列正好覆盖整个序列#xff0c;证明显然。 我们可以做一个前缀\(max\)序列。这样对于\(max[i]\)#xff0c;保证\(max[i]i\)。 而… Description 详见OJ Solution 对于\(limit1,2\)就是使序列\(1~n\)的排列。 对于\(limit3\)我们可以将其看做是两个最长上升子序列正好覆盖整个序列证明显然。 我们可以做一个前缀\(max\)序列。这样对于\(max[i]\)保证\(max[i]i\)。 而且保证\(max[n]n\)。 如此我们可以将问题转化成图。 那么我们可以将问题变成 求从\((1,1)\)到\((x,y)\)再到\((n,n)\)的方案数途中不能触碰到\(yx-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\n, ans);}return 0;
} 转载于:https://www.cnblogs.com/jz929/p/11348921.html
