CF1648C Tyler and Strings 题解
jiangtaizhe001
·
·
题解
可能更好的阅读体验
题目传送门
题目大意
给定一个长度为 n 的序列 a 和长度为 m 的序列 b。现在你需要将序列 a 进行重排列，求字典序小于 b 的不同种类。对 998244353 取余。
不同种类的定义为至少存在一位不同。
### 题目解析
不难想到我们可以枚举 $k$，计算 $\forall j\in [1,k-1],a_j=b_j$ 并且 $a_k<b_k$ 的种类。
显然发现从 $i+2$ 开始就是没有限制的了。
考虑当前有 $n$ 个数字，开个桶，令数字 $i$ 有 $t_i$ 个。
令总方案数为
$$now=\frac{n!}{\prod t_i!}$$
这时如果去掉一个数字 $k$，那么这时的方案数量为
$$now'=\frac{(n-1)!}{\prod_{i\not=k}t_i! \times (t_k-1)!}$$
也就是说
$$now'=now\times\frac{t_k}{n}$$
然后我们考虑计算 $\forall j\in [1,k-1],a_j=b_j$ 并且 $a_k<b_k$ 的种类。
这也就是相当于去掉数字 $1,2,\dots,b_k$ 的答案和。
新增的答案等于
$$\sum_{i=1}^{b_k-1} now \times \frac{t_i}{n}$$
也就是
$$now\times\frac{\sum\limits_{i-1}^{b_k-1}}{n}$$
这样开个树状数组维护一下 $t_i$ 的前缀和即可。
注意以上的做法没有考虑到当 $n<m$ 并且存在一种方法使得 $\forall i \in [1,n],a_i=b_i$ 的方法。
核心代码：
```cpp
int n,m,a[maxn],b[maxn],c[maxn],t[maxn];
#define lowbit(x) (x&-x)
void add(int x,int y){ while(x<=N) c[x]+=y,x+=lowbit(x); return; }
int find(int x){ int sum=0; while(x) sum+=c[x],x-=lowbit(x); return sum; }
ll fpow(ll x,ll y){
ll res=1,tmp=x%MOD; while(y){ if(y&1) res=res*tmp%MOD; y>>=1; tmp=tmp*tmp%MOD; } return res;
}
ll fact[maxn],inv[maxn],now,ans,tmp;
void init(){
int i; fact[0]=inv[0]=1; for(i=1;i<=N;i++) fact[i]=fact[i-1]*i%MOD; inv[N]=fpow(fact[N],MOD-2);
for(i=N-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%MOD; now=fact[n];
for(i=1;i<=n;i++) t[a[i]]++; for(i=1;i<=N;i++) add(i,t[i]),now=now*inv[t[i]]%MOD; return;
}
int main(){
n=read(); m=read(); int i; for(i=1;i<=n;i++) a[i]=read(); for(i=1;i<=m;i++) b[i]=read(); init();
for(i=1;i<=n;i++){
if(i>m) break; if(i==n&&n<m&&t[b[i]]) ans++;
tmp=fpow(n-i+1,MOD-2); ans+=now*tmp%MOD*find(b[i]-1)%MOD; ans%=MOD;
if(t[b[i]]){ now=now*tmp%MOD*t[b[i]]%MOD; t[b[i]]--; add(b[i],-1); } else break;
} print(ans%MOD); return 0;
}
```