CF1526E Oolimry and Suffix Array 组合数学

标签：Oolimry Suffix ifac ll equ CF1526E ans mod rk

看起来是后缀数组，但是看到求方案数就是dp，计数啥的了

问满足后缀数组的字符串方案有多少

观察样例，发现rk相邻的所在位置，字母要么是相等，要么是比其大

大的话条件直接满足了，相等的话还取决于rk[i]+1,和rk[i]+1

如果rk[i]+1<rk[i+1]+1，则我们可以取等号，否则不满足限制

则我们可以求出有多少取等号的地方

问题可以转化成：在 p1 <（=） p2 <（=） p3 <（=） p4 <（=） p5.. 链中

有若干个可以取等号的地方，记为equ，求放等号的方案数

一种朴素的想法是枚举放i个，答案为:

 

 但观察上式，强制把每个等号位置后面的数都加1，就把等号转化为小于号，取值上限变成k+equ，从中选出n个填入必能满足条件(因为减掉加上的就还原了），所以答案是：C(k+equ，n)

听说是组合数学里常见的trick:)

 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400005;
const ll mod=998244353;
ll fac[N],ifac[N];
ll n,k,sa[N],rk[N];
ll quickp(ll x,ll p){
    ll ans=1,base=x;
    while(p){
        if(p&1) ans=ans*base%mod;
        base=base*base%mod;
        p>>=1;
    }
    return ans;
}
ll C(ll a,ll b){
    if(a<0||b<0||b>a) return 0;
    return fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
int main(){
    
    //freopen("lys.in","r",stdin);
    
    cin>>n>>k;
    ll cnm=n;
    for(ll i=1;i<=n;i++){
        cin>>sa[i];sa[i]++;rk[sa[i]]=i;
    }
    ll equ=0;
    for(ll i=1;i<n;i++){
        if(rk[sa[i]+1]<rk[sa[i+1]+1]) equ++;
    }

    fac[0]=1;
    for(ll i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
    
    ifac[N-1]=quickp(fac[N-1],mod-2);
    for(ll i=N-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;

    cout<<C(k+equ,cnm);
}

 

标签：Oolimry,Suffix,ifac,ll,equ,CF1526E,ans,mod,rk
From： https://www.cnblogs.com/liyishui2003/p/16739663.html