E. Tyler and Strings（組合計數 + 樹狀數組/線段樹）（帶重複元素的全排列）

題目連結

主要思路還是比較好想的，一些細節公式預處理比較難搞…

參考題解

分析

從前往後周遊，如果s[]剩下的數中，s[i] < t[i]則對答案是有貢獻的；

貢獻就是後面位置[i+1 ~ n]的數字可以随便排，也就是帶重複數字的全排列（公式看題解）；

到這裡就知道了要搞一個桶來維護一下每個數字的個數，而且要維護字首和。

計算完第i位，向後周遊時，我們的s[i]就要=t[i]了，是以每次剩下的數字中cnt[s[i]]要–；

是以動态修改查詢我們可以用樹狀數組或線段樹維護這個桶。

關鍵是你每次修改了cnt的話，你後面的全排列計算公式也是不一樣的，這個咋搞？

我們可以一開始可以先求出公式中的分母部分(記得逆元)mu；

對于每次修改，在修改前我們先把mu除掉cnt[s[i]]，cnt[s[i]]–，然後mu再乘上cnt[s[i]]就行了；

注意最後我們還要特判s[]是t[]的字首的情況，此時ans += 1；

題解中是從0開始的，是以是 fac[n-i-1]；

我是從1開始的，是以fac[n-i]，這個注意一下就行。

代碼

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include <unordered_map>
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 2e5 + 7;
const int N = 2e6 + 7;
const int M = 4e6 + 7;
const int mod = 998244353;
//const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

int s[maxn],t[maxn];
int cnt[maxn];	//s[]中每種數的個數
ll fac[maxn],infac[maxn];	//階乘，階乘逆元
int n,m;

struct node
{
	int l,r;
	ll v;
}tr[maxn*4];

void pushup(int u)
{
	tr[u].v = tr[u<<1].v + tr[u<<1|1].v;
//	tr[u].v = max(tr[u<<1].v, tr[u<<1|1].v);
}

void build(int u,int l,int r)
{
	tr[u] = {l,r};
	
	if(l == r) return;

	int mid = l + r >> 1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	pushup(u);
}

void update(int u,int idx,int x)	//單點修改
{
	if(tr[u].l == idx && tr[u].r == idx)
	{
		tr[u].v += x;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	if(idx <= mid) update(u<<1, idx, x);
	else update(u<<1|1, idx, x);
	
	pushup(u);
}

int query(int u,int l,int r)
{
	if(l <= tr[u].l && r >= tr[u].r) return tr[u].v;
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	int ans = 0;
	if(l <= mid) ans += query(u<<1, l, r);
	if(r > mid) ans += query(u<<1|1, l, r);
	
	return ans;
}

void init()	//處理階乘和階乘逆元
{
	fac[0] = infac[0] = 1;
	for(int i=1;i<maxn;i++)
	{
		fac[i] = fac[i-1] * i % mod;
		infac[i] = infac[i-1] * qmi(i,mod-2,mod) % mod;
	}
}

void solve()
{
	init();
	
	iire(n,m);
	
	build(1,1,maxn-1);	//注意這裡是maxn-1，不是n
	
	for(int i=1;i<=n;i++)
	{
		ire(s[i]);
		cnt[s[i]]++;
		
		update(1,s[i],1);
	}
	
	for(int i=1;i<=m;i++) ire(t[i]);
	
// 	cout<<query(1,3,3)<<'\n';
	
	ll mu = 1;	//先把分母算好
	for(int i=1;i<maxn;i++) mu = mu * infac[cnt[i]] % mod;
	
	//下面計算貢獻值
	ll ans = 0;
	int f = 1;
	for(int i=1;i<=min(n,m);i++)
	{
		ll num = query(1,1,t[i]-1);	//求出s[]剩下數字中<t[i]的數的個數
		ans = (ans + num*fac[n-i] % mod * mu % mod) % mod;
		
		if(cnt[t[i]])
		{
			mu = mu * fac[cnt[t[i]]] % mod;	//先除去cnt[t[i]]
			cnt[t[i]] --;
			mu = mu * infac[cnt[t[i]]] % mod;	//先乘上cnt[t[i]]
			
			update(1,t[i],-1);
		}
		else
		{
			f = 0;
			break;
		}
	}
	
	if(f && n < m) ans = (ans + 1) % mod;	//s是t的字首
	
	cout<<ans<<'\n';
}

int main()
{
	int T;
//	ire(T);
	T = 1;
	while(T--)
	{
		solve();
	}
	
	return 0;
}