广州电信网站备案,建设银行网站登录,哪些网站可以做微信支付,宁波网站优化价格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
