#775 Div.1 C. Tyler and Strings 组合数学

C
组合数学，1900，数状数组

题意

给出 $s,t$ 两个序列，长度分别为 $n,m$，问 $s$ 有多少种排序方式满足 $s$ 的字典序比 $t$ 小。 $1\le n,m\le 2e5$

思路

因为是按字典序比较，所以如果 $s_1<t_1$ 之后的就可以随便排了，所以考虑枚举前 $i-1$ 位相同且 $s_i<t_i$ 的排序方式有 $cn{t}_i$ 种，最后的答案就是 ${\sum }_{i=1}^{i=n}cn{t}_i$ 。

那么如何求 $cn{t}_i$ 呢？如果不考虑可重复排列，那么 $cn{t}_i=now\times (n-i)!$ ，即到第 i 位当前满足小于 $t_i$ 的个数乘上之后数的全排列（因为 $i$ 后面的数可以随便取了）。$now$ 可以直接用数状数组维护前缀和（因为前 $i-1$ 位两序列相同，所以可以直接将那个数字数量减1）。于是问题重点在于加上可重复排列后怎么做。

首先可重复排列要在 $n!$ 的基础上除以每个元素出现数量的阶乘。即当我们遍历到第 $i$ 位时，要在 $(n-i)!$ 的基础上除以 $$cn{t}_1!\times cn{t}_2!\times cn{t}_i!....\times cn{t}_n!$$
其中 $cn{t}_1$ 是减去前 $i-1$ 位数字后的对应数字的数量。然后我们就可以先预处理出 $i=0$ 时的上式记为 fenzi，由
$$\frac{1}{cn{t}_1!\times cn{t}_2!\times (cn{t}_i-1)!....\times cn{t}_n!}=\frac{1}{cn{t}_1!\times cn{t}_2!\times cn{t}_i!....\times cn{t}_n!}\times cn{t}_i$$，只需每次遍历后将 fenzi *= cnt[t[i]] 并更新 cnt[t[i]] 即可。

ps.不要忘记考虑 $s$ 可能恰好为 $t$ 的前缀的情况，开始忘了，还好有样例1

代码

void solve() {
   cin >> n >> m;
   fac[0] = 1;
   for(int i = 1; i <= n; i++) {
   	fac[i] = (fac[i-1] * i) % P;
   }
   for(int i = 1; i <= n; i++) {
   	cin >> s[i];
   	update(s[i], 1);
   	cnt[s[i]]++;
   }
   for(int i = 1; i <= m; i++) {
   	cin >> t[i];
   }
   int ans = 0;
   int mi = min(n, m);
   int fz = 1;
   for(int i = 1; i <= 2e5; i++) {
   	if(cnt[i]) {
   		fz = fz * fac[cnt[i]] % P;
   	}
   }
   fz = power(fz, P - 2);
   int flag = 1;
   if(n >= m) {
   	flag = 0;
   }
   for(int i = 1; i <= mi; i++) {
   	int p = ask(t[i] - 1);
   	ans = (ans + p * fac[n-i] % P * fz % P) % P;
   	if(!cnt[t[i]]) {
   		flag = 0;
   		break;
   	}
   	fz = fz * cnt[t[i]] % P;
   	cnt[t[i]]--;
   	update(t[i], -1);
   }
   ans += flag;
   ans %= P;
   cout << ans << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42