[CF1366E] Two Arrays

Description

给定一个长为 (n) 的序列 (a_i) 和一个长为 (m le n) 的严格上升序列 (b_i)，要求将 (a_i) 划分为 (m) 段，第 (i) 段的最小值恰好为 (b_i)，求划分方案数。

Solution

关键在于如何利用 (b_i) 严格上升这个条件。

考虑求出 (a_i) 序列的后缀最小值 (f_i)，那么对于任意位置 (i)，如果我们要让它作为第 (j) 段的首元素，那么必须要满足 (f_i=b_j)，因为 (b_j) 必须要在后面这些数中至少出现一次，并且必须是后面这些数中最小的数。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;
const int mod = 998244353;

int n,m,a[N],b[N];
map<int,int> mp;

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    
    for(int i=n-1;i>=1;i--) a[i]=min(a[i],a[i+1]);

    int ans=1;
    if(a[1]!=b[1]) ans=0;

    for(int i=1;i<=n;i++) mp[a[i]]++;
    for(int i=2;i<=m;i++) ans=(ans*mp[b[i]])%mod;

    cout<<ans<<endl;
}