题解：P13547 [OOI 2022] Third grader's task

· · 题解

题目传送门

欢迎来博客园阅读！

题意简述

有 n 个字母和一个目标字符串 t，求有多少种排列方式能够使得这 n 个字母组成的字符串字典序小于 t。

思路

先只考虑排列数。

对于字典序，当一个地方的字母出现不同之后，就无所谓后面的字符是什么样子了。于是，对于每一个位置 i，考虑两种情况：

  1. 选出 s_i=t_i，则接下来继续考虑后面的情况；
  2. 选出 s_i<t_i，则后面的字符可以任意组合。

也就是说，当我们到达位置 i，前面的部分必然有 s_{1 \sim i-1} = t_{1 \sim i-1}，也就是说对于每一个点考虑的时候剩下的字符是确定的。记 x 为 s_{1 \sim i-1} = t_{1 \sim i-1} 的方案数，cnt_i 为 s 中剩余的 i 的个数，那么对于两种情况，操作分别是：

  1. 令 s_i=t_i，则 s 中不剩 t_i 了就结束，s 中还剩 t_i 则使用一个，更新 x \leftarrow x \times cnt_{t_i},cnt_{t_i} \leftarrow cnt_{t_i} - 1；

问题在于 \sum_{i = 1}^{t_i - 1} cnt_i 怎么求。注意到这是一个区间和的形式，并且第一种情况下有修改，于是想到了树状数组维护，支持单点修改和区间求和。

还有一种特殊情况：s 为 t 的前缀时，也可以满足题意，其条件是：

  1. n<m
  2. 不存在因为 s 中不剩 t_i 了而结束的情况

最后处理重复的部分：

先只考虑排列数。

显然重复的部分就是把排列数变成组合数，因为很多字符都是相同的。在输入的时候同时维护一个桶排数组 p_i 记录 i 的出现次数。记 s 中最大值为 s_{\max}，于是最后再将 ans 更新为：

ans \leftarrow \frac{ans}{\prod _{i = 1}^{s_{\max}}p_i}

于是本题完成。

代码

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define rloop(i,a,b) for(int i=(a);i>=(int)(b);i--)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;

const int N=2e5+5;
const int mod=998244353;

int n,m;
int s,t[N];
ll fac[N],inv[N];
int tr[N],p[N]; // p[i]：i 的出现次数

ll qmi(ll a,int k){
    ll res=1;
    while(k){
        if(k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

void init(){ // 预处理阶乘及其逆元
    fac[0]=1;
    loop(i,1,200000)fac[i]=fac[i-1]*i%mod;
    inv[200000]=qmi(fac[200000],mod-2);
    rloop(i,199999,0)inv[i]=inv[i+1]*(i+1)%mod;
    return;
}

// 树状数组部分
void add(int u,int d){
    while(u<=200000)tr[u]+=d,u+=lowbit(u);
    return;
}

int sum(int u){
    int res=0;
    while(u>0)res+=tr[u],u-=lowbit(u);
    return res;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    loop(i,1,n)cin>>s,add(s,1),p[s]++;
    loop(i,1,m)cin>>t[i];

    init();
    ll ans=0,x=1;
    bool flag=n<m; // flag = 1 : s 为 t 的前缀

    loop(i,1,min(n,m)){
        ans=(ans+x*sum(t[i]-1)%mod*fac[n-i]%mod)%mod;
        if(sum(t[i])-sum(t[i]-1)==0){
            flag=0;
            break;
        }
        x=x*(sum(t[i])-sum(t[i]-1))%mod;
        add(t[i],-1);
    }

    if(flag)ans=(ans+x)%mod;
    loop(i,1,200000)ans=ans*inv[p[i]]%mod;
    cout<<ans<<'\n';
    return 0;
}

完结撒花花！