考虑怎么算。在第 $i$ 位，使前面的 $s_1:s_{i-1}=t_1:t_{i-1}$，然后只要在剩下的自由 $s$ 里面选一个小于 $t_i$ 的放到当前位置 $s_i$ 上，后面 $s_{i+1}:s_n$ 随便排。有 $R(x)$ 个自由的 $s$ 元素小于 $x$，前面的 $s_1:s_{i-1}$ 匹配 $t$ 的方案数为 $p_i$，那么 $i$ 位的贡献就是 $p_i R(t_i)(n-i)!$。吗？

你会发现题面要求的是不同的序列数，排列会数重。于是最后把重复的部分除掉。显然 $s$ 中出现了 $C(x)$ 次 $x$ 就要把最终结果变为 $ans^\prime=\dfrac{ans}{C(x)}$。

如果在第 $i$ 位，没有自由 $s=t_i$，那 $s_1:s_i=t_1:t_i$ 和以后都满足不了直接退出循环即可。$R$ 用树状数组维护一下就是 $\mathcal O(n\log V)$，然后注意特判 $s$ 是 $t$ 前缀的情况。最终结果就是

$$\frac{\sum_i p_i R(t_i) (n-i)!}{\prod_x C(x)!}+[s\text{是} t \text{的前缀}]$$

Code

:::info[P13547]

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ir(i,a,b) for(int i=b;i>=a;i--)
#define db double
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define re return
#define len(str) (str.length())
#define inr(L,R,l,r) (l<=L and R<=r)
#define ofr(L,R,l,r) (L>r or l>R)
#define lowbit(x) (x&(-x))
#define tn2 tuple<node*,node*> 
#define tn3 tuple<node*,node*,node*>
#define mt make_tuple
#define np nullptr
#define ioo cin.tie(0)->sync_with_stdio(0);cout.tie(0)->sync_with_stdio(0);
#define popc __builtin_popcount
using namespace std;
const ll maxn=2e5+114,P=998244353;
ll n,m;
ll s[maxn],t[maxn];
ll c[maxn];
void add(ll a,ll b)
{
    while(a<=2e5) c[a]=(P+c[a]+b)%P,a+=lowbit(a);
}
ll sum(ll a)
{
    ll res=0;
    while(a) {res=(res+c[a])%P;a-=lowbit(a);}
    re res;
}
ll fac[maxn],inv[maxn],cnt[maxn],r[maxn];
int main()
{
    cin>>n>>m;
    rep(i,1,n) cin>>s[i];
    rep(i,1,m) cin>>t[i];
    rep(i,1,n) add(s[i],1),cnt[s[i]]++;
    fac[0]=1;
    rep(i,1,2e5) fac[i]=fac[i-1]*i%P;
    inv[0]=inv[1]=1;
    rep(i,2,2e5) inv[i]=(P-(P/i)*inv[P%i]%P)%P;
    rep(i,2,2e5) inv[i]=(inv[i-1]*inv[i]%P);
    ll ans=0,k=1,j=0;
    rep(i,1,min(n,m))
    {
        ans=(ans+k*sum(t[i]-1)%P*fac[n-i]%P)%P;
        if(sum(t[i])-sum(t[i]-1)) add(t[i],-1);
        else break;
        k=k*(sum(t[i])-sum(t[i]-1)+1)%P;
        j=i;
    } 
    if(j==n and n<m) ans=(ans+k)%P;
    rep(i,1,2e5) ans=ans*inv[cnt[i]]%P;
    
    cout<<ans<<endl;
}

:::