loj 2719 「NOI2018」冒泡排序

题目传送门

　　传送门

题目大意

　　（相信大家都知道）

　　显然要考虑一个排列$p$合法的充要条件。

　　考虑这样一个构造$p$的过程。设排列$p^{-1}_{i}$满足$p_{p^{-1}_i} = i$。

初始令$q = (1, 2, \cdots, n)$。
依次考虑$i = 1, 2, \cdots, n$。
- 设$x = p_i$，如果$q^{-1}_x > i$，那么交换$q_x, q_{x - 1}$。

　　上述算法每次交换的时候会使逆序对增加1。

　　考虑给出的下界，假设交换的是$i$和$i + 1$。

　　不难用归纳法证明$p_i \leqslant i$。

　　那么考虑$ \Delta = (i + 1 - p_i + |p_{i + 1} - i|) - (i - p_i + |p_{i + 1} - i - 1|)$。

如果$p_{i + 1} \geqslant i + 1$，那么有$ \Delta = (i + 1 - p_i + p_{i + 1} - i) - (i - p_i + p_{i + 1} - i - 1) =2$
如果$p_{i + 1} \leqslant i$，那么有$\Delta = (i + 1 - p_i + i - p_{i + 1}) - (i - p_i + i + 1 - p_{i + 1}) = 0$

　　每次改变量要么为0，要么为2，如果某一次为0，那么将永远达不到下界。

　　因此序列合法当仅当上述算法中，每次交换满足$q_x \geqslant x$。

　　上述算法中，未确定的数并且可以向前移动的是一段后缀，并且满足$q_x = x$。

　　假如某次将$y$向前移动，那么如果一个$z < y$，并且$z$未确定，那么你不能将$z$向前移动。

　　然后考虑一下没有字典序限制怎么做，显然这个问题不会更难。

　　设$f_{i, j}$表示考虑到排列的前$i$个数，其中最大值为$j$。

　　转移考虑最大值有没有发生改变。

　　$(i, j)$是平面上的一个点，考虑把这个问题转化到平面上。

　　最大值改变等于可以向上走若干步，不变相当于向右走一步。

　　另外还需要满足$i \geqslant j$。

　　用折线法可以轻松计算出方案数。

　　然后我们来考虑原问题。

　　字典序严格大于似乎有点烦？考虑小于等于。（其实是我今天想的时候把题意记错了，写完发现过不了样例）

　　仍然考虑枚举一个长度为$i - 1$的前缀，然后计算在$i$脱离限制后的方案数。

　　下面只考虑长度为$i - 1$的前缀是合法的情况。

如果$a_{i}$是一个前缀最大值，那么考虑$i - 1$的前缀最大值是$mx$，答案加上从$(i, mx), (i, mx + 1), \cdots, (i, a_i - 1)$开始的方案数。
如果$a_i$不是前缀最大值
- 如果比不是前缀最大值的最小值还大，那么此时前缀$i$不合法，答案加上从$(i, mx)$开始的方案书。
- 否则对答案没有贡献。

Code

/**

 * loj

 * Problem#2719

 * Accepted

 * Time: 652ms

 * Memory: 10236k

 */

#include <bits/stdc++.h>

using namespace std;

typedef bool boolean;

#define ll long long

void exgcd(int a, int b, int& x, int& y) {

	if (!b) {

		x = 1, y = 0;

	} else {

		exgcd(b, a % b, y, x);

		y -= (a / b) * x;

	}

}

int inv(int a, int n) {

	int x, y;

	exgcd(a, n, x, y);

	return (x < 0) ? (x + n) : (x);

}

const int Mod = 998244353;

template <const int Mod = :: Mod>

class Z {

	public:

		int v;

		Z() : v(0) {	}

		Z(int x) : v(x){	}

		Z(ll x) : v(x % Mod) {	}

		friend Z operator + (const Z& a, const Z& b) {

			int x;

			return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));

		}

		friend Z operator - (const Z& a, const Z& b) {

			int x;

			return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));

		}

		friend Z operator * (const Z& a, const Z& b) {

			return Z(a.v * 1ll * b.v);

		}

		friend Z operator ~(const Z& a) {

			return inv(a.v, Mod);

		}

		friend Z operator - (const Z& a) {

			return Z(0) - a;

		}

		Z& operator += (Z b) {

			return *this = *this + b;

		}

		Z& operator -= (Z b) {

			return *this = *this - b;

		}

		Z& operator *= (Z b) {

			return *this = *this * b;

		}

		friend boolean operator == (const Z& a, const Z& b) {

			return a.v == b.v;

		}

};

Z<> qpow(Z<> a, int p) {

	Z<> rt = Z<>(1), pa = a;

	for ( ; p; p >>= 1, pa = pa * pa) {

		if (p & 1) {

			rt = rt * pa;

		}

	}

	return rt;

}

typedef Z<> Zi;

typedef class Input {

	protected:

		const static int limit = 65536;

		FILE* file; 

		int ss, st;

		char buf[limit];

	public:

		Input():file(NULL)	{	};

		Input(FILE* file):file(file) {	}

		void open(FILE *file) {

			this->file = file;

		}

		void open(const char* filename) {

			file = fopen(filename, "r");

		}

		char pick() {

			if (ss == st)

				st = fread(buf, 1, limit, file), ss = 0;//, cerr << "str: " << buf << "ed " << st << endl;

			return buf[ss++];

		}

} Input;

#define digit(_x) ((_x) >= '0' && (_x) <= '9')

Input& operator >> (Input& in, unsigned& u) {

	char x;

	while (~(x = in.pick()) && !digit(x));

	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');

	return in;

}

Input& operator >> (Input& in, unsigned long long& u) {

	char x;

	while (~(x = in.pick()) && !digit(x));

	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');

	return in;

}

Input& operator >> (Input& in, int& u) {

	char x;

	while (~(x = in.pick()) && !digit(x) && x != '-');

	int aflag = ((x == '-') ? (x = in.pick(), -1) : (1));

	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');

	u *= aflag;

	return in;

}

Input& operator >> (Input& in, long long& u) {

	char x;

	while (~(x = in.pick()) && !digit(x) && x != '-');

	int aflag = ((x == '-') ? (x = in.pick(), -1) : (1));

	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');

	u *= aflag;

	return in;

}

Input in (stdin);

const int N = 6e5 + 5;

const int N2 = N << 1;

int T, n;

Zi fac[N2], _fac[N2];

void init_fac(int l, int r) {

	for (int i = l; i <= r; i++) {

		fac[i] = fac[i - 1] * i;

	}

	_fac[r] = ~fac[r];

	for (int i = r; i > l; i--) {

		_fac[i - 1] = _fac[i] * i;

	}

}

void init_fac(int n) {

	static int old = 0;

	fac[0] = 1, _fac[0] = 1;

	if (n > old) {

		init_fac(old + 1, n);

		old = n;

	}

}

Zi comb(int n, int m) {

	return (n < m) ? (0) : (fac[n] * _fac[m] * _fac[n - m]);

}

Zi C(int x, int y) {

	return comb(x + y, x);

}

Zi S(int x, int y) {

	if (y + 1 <= x)

		return 0;

	return (y == n) ? (1) : (C(n - x, n - y) - C(n + 1 - x, n - 1 - y));

}

boolean vis[N];

int main() {

	freopen("inverse.in", "r", stdin);

	freopen("inverse.out", "w", stdout);

	in >> T;

	while (T--) {

		in >> n;

		if (!n) {

			puts("0");

			continue;

		}

		init_fac(n << 1);

		memset(vis, false, n + 2);

		int mx = 0, sc = 1, i = 1, a;

		Zi ans = 0;

		for (i = 1; i < n; i++) {

			in >> a;

			if (a > mx) {

				for (int j = mx; j < a; j++) {

					ans += S(i, j);

				}

				mx = a;

			} else {

				while (vis[sc]) sc++;

				if (sc ^ a) {

					ans += S(i, mx);

					break;

				}

			}

			vis[a] = true;

		}

		if (i == n) {

			in >> a;

			ans += 1;

		} else {

			while (++i <= n)

				in >> a;

		}

		ans = S(0, 0) - ans;

		printf("%d\n", ans.v);

	}

	return 0;

}

巴特西

loj 2719 「NOI2018」冒泡排序 - 组合数学

Code

最新文章

热门文章