SP10419 POLISH - Polish Language

lzyqwq · 2023-08-23 09:58:23 · 题解

cnblogs

串串真可爱。

题目链接

• 给出字符串 s，记 suf_i 为以 i 为开头的后缀，求有多少个序列 a 满足：

  • \forall i\in[1,|a|],1\le a_i\le |s|
  • \forall i\in(1,|a|],suf_{a_i}>suf_{a_{i-1}}
  • \forall i\in (1,|a|],|suf_{a_i}|>|suf_{a_{i-1}}|

  数量对 10^9+7 取模。其中字符串的比较均基于字典序大小。

• 多组数据，|s|\le 10^5。

看到后缀之间的字典序比较，先想到后缀数组。处理完之后，考虑一个一个解决限制条件。

典型二位偏序，考虑 dp。设 f_i 表示 a_{|a|}=i 的符合条件的序列数量，显然有 f_i=\sum\limits_{i<j\le n\land rk_i>rk_j}f_j+1。简单来说就是考虑第 i 位接上怎样的序列，+1 表示单独成为一个序列。

倒序枚举维护 i<j，用树状数组维护 rk_i>rk_j 即可。

设数据组数为 T，时间复杂度为 \mathcal{O}(T|s|\log |s|)，空间复杂度为 \mathcal{O}(|s|)。

评测记录

#include<bits/stdc++.h>
#define int long long
#define lb(x) ((x)&-(x))
#define mp make_pair 
#define fi first 
#define se second
using namespace std;
const int N=1e5+5,mod=1e9+7;
string s,t;
int n,rk[N],cnt[N],bit[N],ans,ok[100];
struct node{
    int a[2];
    bool operator!=(const node&o)const{
        return a[0]!=o.a[0]||a[1]!=o.a[1];
    }
};
pair<node,int>p[N],tmp[N];
void modify(int x,int k){
    for(int i=x;i<=n;i+=lb(i)){
        bit[i]=(bit[i]+k)%mod;
    }
}
int query(int x){
    int ret=0;
    for(int i=x;i>=1;i-=lb(i)){
        ret=(ret+bit[i])%mod;
    }
    return ret;
}
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    while(cin>>s){
        n=s.size();
        s=' '+s;
        memset(bit,0,sizeof bit);
        memset(ok,0,sizeof ok);
        ans=0;
        for(int i=1;i<=n;++i){
            ok[s[i]]=1;
        }
        for(int i=1;i<=100;++i){
            ok[i]+=ok[i-1];
        }
        for(int i=1;i<=n;++i){
            rk[i]=ok[s[i]];
        }
        for(int len=1,id;len<=n;len<<=1){
            for(int i=1;i<=n;++i){
                node k;
                k.a[0]=rk[i];
                k.a[1]=(i+len>n?0:rk[i+len]);
                p[i]=mp(k,i);
            }
            for(int qwq=1;qwq>=0;--qwq){
                memset(cnt,0,sizeof cnt);
                for(int i=1;i<=n;++i){
                    ++cnt[p[i].fi.a[qwq]];
                }
                for(int i=1;i<=n;++i){
                    cnt[i]+=cnt[i-1];
                }
                for(int i=n;i>=1;--i){
                    tmp[cnt[p[i].fi.a[qwq]]--]=p[i];
                }
                for(int i=1;i<=n;++i){
                    p[i]=tmp[i];
                }
            }
            id=0;
            for(int i=1;i<=n;++i){
                if(i==1||p[i].fi!=p[i-1].fi){
                    ++id;
                }
                rk[p[i].se]=id;
            }
            if(id==n){
                break;
            }
        }
        for(int i=n,x;i>=1;--i){
            x=query(rk[i]-1)+1;
            ans=(ans+x)%mod;
            modify(rk[i],x);
        }
        cout<<ans<<'\n';
    }
    return 0;
}