C. Tyler and Strings（组合数学,树状数组维护前缀和）(Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad i)

对我来说比较困难的一题了,尝试着自己写了一下,调不出来遂放弃.
Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics)
https://codeforces.com/contest/1648/problem/C
C.Tyler and Strings
题意:给你字符串$s,t$,你可以对$s$任意排序,问你有多少种方案使得$s$重排后字典序会比$t$小.
思路:枚举每次在哪里断掉.比如说在$i$的位置,令$s_j<t_j$,那么合法的方案就是任意排序了.
比如说$$s=1,2,3,4,t=4,3,2,1$$,第一个位置选择1,剩下的$2,3,4$任意排列都是合法方案.
这种情况下就是$A(3,3)=6$.
可以预见,后面$对于t来说,后续元素[i+1,n]$包含重复元素的全排列就是当前令$si<ti$的合法方案.
为什么是重复元素,因为你一个数字后面可能出现多次.
因为我们还可以选择不同的字符在当前位置$j$,令$si<ti$.令所有的$字符i,s_i<t_i$组成一个集合.我们每次都要统计这个集合对答案的贡献.(枚举到$t_i$)的时候.
包含重复元素的全排列数目的计算公式是:$$\frac{n!}{cn{t}_1!\ast cn{t}_2!\ast ...cn{t}_k!}$$
其中$n$为总数目,k有多少种类,$cn{t}_k$为不同种类的数目.
那么每一个$s_i<t_i$对应的贡献记为$ad{d}_i$(注意这里的n是指题目来说,实际上是$n-i-1$)
$$ad{d}_i=\frac{(n-i)!}{cn{t}_1!\ast cn{t}_2!\ast ....\ast (cn{t}_i-1)!\ast ..\ast cn{t}_k!}$$
显然,每次统计答案的时候,我们还需要求add数组的前缀和.而且add数组也会因为$i$的推进不断更改值,因为推进的时候,你是让$s_{i-1}==t_{i-1}$,保证了前i-1位是一个前缀,才能考虑第i位.
我们需要一种数据结构,支持单点改值,区间求和,使用树状数组/线段树.
但这并没有完结.不难发现,每次在i位使得$s_i==t_i$后,对应的$cn{t}_{si}会减少1$,造成整个$add数组都会发生变化$.如果每次都要去更改一遍,无论是哪种数据结构都是难以接受的.
我们考虑写出每种元素$i$,对应$ad{d}_i发生的变化,寻求共同改变的地方以降低复杂度$
对于不被删去的元素我们称为$j$.
删去元素$i$后
$$ad{d}_j=\frac{(n-i-1)!}{cn{t}_1!\ast cn{t}_2!\ast ....\ast (cn{t}_i-1)!\ast ..\ast cn{t}_k!}$$
$$ad{d}_i=\frac{(n-i-1)!}{cn{t}_1!\ast cn{t}_2!\ast ....\ast (cn{t}_i-2)!\ast ..\ast cn{t}_k!}$$
等等,这不是几乎一模一样吗,只要我们在一开始给$ad{d}_i$数组赋值的时候,给自己赋值为$(cn{t}_i-1)!不就好了$
那么每次修改数组,就相当于$add数组整体乘上一个变量,称为var$.
$var=\frac{cn{t}_i}{(n-i+1)}$其中分子代表把$ad{d}_i分母上的（cn{t}_i）!变为(cn{t}_i-1)!$,分母代表$把(n-i)!变为(n-i-1)!$.
接下来,统计答案就是挨个扫描$t_i$,令$x=t_i$,查询$[1,x-1]的add前缀和,加到ans上即可$.
题解的思想到这结束,然而我们会发现这些写很容易写错…我至少发现是这样的.
我们考虑继续优化$add$数组.我们发现对于区间$[1,x-1]$写出他们$add$的求和形式.
$$sum1i=\frac{(n-i)!}{(cn{t}_1-1)!\ast cn{t}_2!\ast ....!\ast ..\ast cn{t}_k!}+\frac{(n-i)!}{(cn{t}_1)!\ast (cn{t}_2-1)!\ast ....\ast ..\ast cn{t}_k!}+\frac{(n-i)!}{(cn{t}_1)!\ast (cn{t}_2)!\ast ....\ast (cn{t}_{x-1}-1)!\ast ..\ast cn{t}_k!}$$
我们再观察以下形式.
$$sum2i=\frac{(n-i)!}{(cn{t}_1)!\ast cn{t}_2!\ast ....!\ast ..\ast cn{t}_k!}+\frac{(n-i)!}{(cn{t}_1)!\ast cn{t}_2!\ast ....!\ast ..\ast cn{t}_k!}+\frac{(n-i)!}{(cn{t}_1)!\ast cn{t}_2!\ast ....!\ast ..\ast cn{t}_k!}$$
对于第一项需要乘以$cn{t}_1,第二项需要cn{t}_2...第x-1项需要乘以cn{t}_x$
那么提取公因式(实际上$sum2i每一项都一样$)
$sum2i\ast {\sum }_{j=1}^{x-1}cn{t}_j=sum1i$
也就是说,我们不再需要维护$ad{d}_i$数组,而是去维护$cn{t}_i$数组即可
题解好像是去维护的$add$,我搞半天搞不出来…

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int INF = 1e9+7;
const ll mod =  998244353;
typedef pair<int,int> pii;
ll f_pow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b&1) ans = (ans*a)%mod;
		a=(a*a)%mod;b>>=1;
	}
	return ans;
}
ll inv_fac[maxn];
ll inv[maxn];
ll fac[maxn];
void inv_table(ll n){
	inv_fac[0]=1;
	inv[1]=1;fac[1]=1;
	for(int i=2;i<=n;i++){
		inv[i] = (mod-mod/i)*inv[mod%i]%mod;
		fac[i] = (fac[i-1]*i)%mod;
	}
	inv_fac[n] = f_pow(fac[n],mod-2);
	for(ll i=n-1;i>=1;i--){
		inv_fac[i] = (inv_fac[i+1] *(i+1)) %mod;
	}
}
ll tree[maxn];
void add(int x,int val){
	while(x<=maxn-5){
		tree[x]=(tree[x]+val)%mod;
		x+=(x&-x);
	}
}
ll query(int x){
	ll ans = 0;
	while(x){
		ans +=tree[x];
		x-=(x&-x);
	}
	return ans;
}
int cnt[maxn];
int main(){
//    freopen("1.txt","r",stdin);
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	inv_table(200000);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		cnt[x]++;
		add(x,1);
	}
	ll var =fac[n];
	for(int i=1;i<=maxn-5;i++){
		var = var*inv_fac[cnt[i]]%mod;
	}
	ll ans = 0;
	for(int i=1;i<=m;i++){
		int x;cin>>x;
		ll sum = query(x-1);
		ans=(inv[n-i+1]*sum%mod*var%mod+ans)%mod;
		if(cnt[x]==0) break;
		var = var*cnt[x]%mod*inv[n-i+1]%mod;
		cnt[x]--;
		add(x,-1);
		if(i==n&&i<m){
			ans=(ans+1)%mod;
			break;
			//s用完了,t没用完,且s是t的前缀.
		}
	}
	cout<<ans<<"\n";
}