775 Div.1 C. Tyler and strings combinatorial mathematics

C
Combinatorial mathematics ,1900, Array of numbers

The question

give $s,t$ Two sequences , The lengths are $n,m$, ask $s$ How many sorting methods meet $s$ The dictionary order of $t$ Small . $1\le n,m\le 2e5$

Ideas

Because it is compared in dictionary order , So if $s_1<t_1$ After that, you can row at will , So before considering enumeration $i-1$ The bits are the same and $s_i<t_i$ The sorting methods of are $cn{t}_i$ Kind of , The final answer is ${\sum }_{i=1}^{i=n}cn{t}_i$ .

So how to ask $cn{t}_i$ Well ？ If repeatable arrangement is not considered , that $cn{t}_i=now\times (n-i)!$ , namely To the first i Bit current Satisfaction is less than $t_i$ Multiply the number of by the total arrangement of the following numbers （ because $i$ The following numbers can be taken at will ）.$now$ You can directly use the number array to maintain the prefix and （ Because of the former $i-1$ The two bit sequences are the same , So you can directly reduce that number 1）. So the key problem is how to add repeatable permutation .

First, the repeatable arrangement should be in $n!$ Divided by the factorial of the number of occurrences of each element . That is, when we traverse to $i$ When a , To be in $(n-i)!$ Divided by $$cn{t}_1!\times cn{t}_2!\times cn{t}_i!....\times cn{t}_n!$$
among $cn{t}_1$ yes Before subtraction $i-1$ Digit number The number of corresponding numbers after . Then we can preprocess out $i=0$ The above formula of tense is recorded as fenzi, from
$$\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$$, After each iteration, you just need to fenzi *= cnt[t[i]] And update the cnt[t[i]] that will do .

ps. Don't forget to consider $s$ It may happen to be $t$ Prefix of , Began to forget , Fortunately, there are examples 1

Code

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;
}