Codeforces1648C. Tyler and Strings

传送门

题目大意

给定一个长为 \(n(1\leq n\leq 2\times10^5)\) 的整数序列 \(s(1\leq s_{i}\leq2\times10^5)\) ，以及一个长为 \(m(1\leq m\leq 2\times10^5)\) 的整数序列 \(t(1\leq t_{i}\leq2\times10^5)\) ，求有多少种 \(s\) 的排列，其字典序小于 \(t\) ，答案对 \(998244353\) 取模。

思路

如果字典序要小于 \(t\) ，那么要与 \(t\) 有一个相同的前缀，我们可以枚举这个相同前缀的长度。当长度为 \(i-1\) 时，第 \(i\) 个数字可以是 \(s\) 中剩下的小于 \(t_{i}\) 的所有数字，然后再乘以后面部分的全排列，设 \(s\) 总共有 \(k\) 种不同的数字，每种数字 \(j\) 在相同前缀长度为 \(i-1\) 时剩余个数为 \(cnt_j\) ，对于第 \(i\) 为每个合法的数字种类 \(j\) ，其贡献就为 \(\frac{(n-i)!}{cnt_1!cnt_2!...(cnt_j-1)!...cnt_k!}=\frac{(n-i)!}{cnt_1!cnt_2!...cnt_k!}cnt_j\) ，于是我们可以记所有在第 \(i\) 个数字处可以枚举的数字个数和为 \(now\) ，于是长度为 \(i-1\) 的相同长度的总贡献为 \(\frac{(n-i)!}{cnt_1!cnt_2!...cnt_k!}now\) ， \(now\) 我们可以用树状数组维护 \(cnt\) 来求得，一开使可以先预处理出分母，之后的都可以推出。此外还需要特判 \(s\) 整体已经是 \(t\) 前缀的这一个可能答案，最后将贡献相加即可。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 100000000;
const LL mod = 998244353;
const int maxn = 200010;

LL N, M, S[maxn], T[maxn], cnt[maxn], fact[maxn], invfact[maxn], dat[maxn], n;

void add(LL i, LL x)
{
	while (i <= n)
	{
		dat[i] += x;
		i += i & (-i);
	}
}

LL sum(LL i)
{
	LL ans = 0;
	while (i)
	{
		ans += dat[i];
		i -= i & (-i);
	}

	return ans;
}

LL qpow(LL a, LL x, LL m)
{
	LL ans = 1;
	while (x)
	{
		if (x & 1)
			ans = ans * a % m;
		a = a * a % m;
		x >>= 1;
	}

	return ans;
}

void fact_init(LL n, LL m)
{
	fact[0] = fact[1] = 1;
	for (LL i = 2; i <= n; i++)
		fact[i] = fact[i - 1] * i % m;
	invfact[n] = qpow(fact[n], m - 2, m);;
	for (LL i = n; i > 0; i--)
		invfact[i - 1] = invfact[i] * i % m;
}

void solve()
{
	LL ans = 0, exans = 1;
	LL allInv = 1;
	for (LL i = 1; i <= 200000; i++)
	{
		if (cnt[i])
			allInv = allInv * invfact[cnt[i]] % mod;
	}
	LL mi = min(N, M);
	if (N >= M)
		exans = 0;
	for (LL i = 1; i <= mi; i++)
	{
		LL now = sum(T[i] - 1);
		ans = (ans + now * fact[N - i] % mod * allInv % mod) % mod;
		if (!cnt[T[i]])
		{
			exans = 0;
			break;
		}
		allInv = (allInv * cnt[T[i]]) % mod;
		cnt[T[i]]--;
		add(T[i], -1);
	}
	cout << (ans + exans) % mod << endl;
}

int main()
{
	IOS;
	n = 200000;
	fact_init(200005, mod);
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		cin >> S[i];
		cnt[S[i]]++;
		add(S[i], 1);
	}
	for (int i = 1; i <= M; i++)
		cin >> T[i];
	solve();

	return 0;
}