May 5, 2023

LiberOJ #3723. 「SDOI / SXOI2022」子串统计

题意

很神奇的题。。。考虑暴力 dp。。不难有。。

FOR(i, 1, n) {
    REP(l, n-i) {
        int r = l + i;
        dp[l][r] = (dp[l+1][r] + dp[l][r-1]) * occ[l][r];
    }
}

只要用后缀数组预处理出 occ 即可，复杂度 O(n2)。

100

101

102

103

104

105

106

107

108

109

110

111

#include <lastweapon/bitwise>
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(5e3) + 9;
 
int C[N], key[N], t1[N], t2[N];
int n;
 
namespace SA {
    const int Z = 27;
    int a[3*N], sa[3*N], rk[N], h[N];
 
    inline void rs(int*x,int*y,int*sa,int n,int m){
        REP(i, n)key[i]=i[y][x];
        memset(C, 0,sizeof(C[0])*m);
        REP(i, n) ++C[key[i]];
        FOR(i, 1, m) C[i] += C[i-1];
        DWN(i, n, 0) sa[--C[key[i]]] = y[i];
    }
 
    void da(int*a,int*sa,int n,int m){
        int *x = t1, *y = t2;
        memset(C,0,sizeof(C[0])*m);
        REP(i, n)++C[x[i]=a[i]];
        FOR(i, 1, m)C[i]+=C[i-1];
        DWN(i, n, 0)sa[--C[x[i]]]=i;
        for(int l=1,p=1;p<n;l<<=1,m=p){
            p=0; FOR(i, n-l, n) y[p++]=i;
            REP(i, n) if (sa[i]>=l) y[p++]=sa[i]-l;
            rs(x,y,sa,n,m),swap(x,y),x[sa[0]]=p=0;FOR(i, 1, n)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+l]==y[sa[i-1]+l])?p:++p;
            ++p;
        }
    }
 
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int c0(int*r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int*r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
 else return r[a]<r[b]||r[a]==r[b]&&key[a+1]<key[b+1];}
 
void dc3(int*a,int*sa,int n,int m){
    int i, j, *an=a+n, *san=sa+n, ta=0, tb=(n+1)/3, tbc=0, p;
    a[n] = a[n+1] = 0; REP(i, n) if (i%3) t1[tbc++]=i;
 
    rs(a+2,t1,t2,tbc,m),rs(a+1,t2,t1,tbc,m),rs(a,t1,t2,tbc,m);
    p=0,an[F(t2[0])]=0;FOR(i, 1, tbc)
        an[F(t2[i])]=c0(a,t2[i-1],t2[i])?p:++p;
 
    if (++p < tbc) dc3(an,san,tbc,p);
    else REP(i, tbc) san[an[i]] = i;
 
    REP(i, tbc) if(san[i] < tb) t2[ta++] = san[i] * 3;
    if (n%3==1) t2[ta++] = n-1; rs(a,t2,t1,ta,m);
    REP(i, tbc) key[t2[i]=G(san[i])] = i;
 
    for(i=0,j=0,p=0; i<ta && j<tbc; p++)
        sa[p]=c12(t2[j]%3,a,t1[i],t2[j]) ? t1[i++] : t2[j++];
    for(;i<ta;p++) sa[p]=t1[i++]; for(;j<tbc;p++) sa[p]=t2[j++];
}
 
void get_h(){
    REP_1(i, n) rk[sa[i]] = i;
    int k=0;for(int i=0;i<n;h[rk[i++]]=k){
        if (k)--k;for(int j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
    }
}
 
void bd(){
    dc3(a,sa,n+1,Z),get_h();
}
 
} using namespace SA;
 
char s[N]; Int dp[N][N]; int occ[N][N];
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
 
    MOD = 998244353;
 
    n = strlen(RS(s)); REP(i, n) a[i] = s[i] - 'a' + 1; bd();
 
    REP(i, n) {
        int l = rk[i], r = l+1;
        DWN(j, n, i) {
            int len = j-i+1;
            while (h[l] >= len) --l;
            while (h[r] >= len) ++r;
            occ[i][j] = r-l;
        }
    }
 
    REP(i, n) dp[i][i] = occ[i][i];
 
    FOR(i, 1, n) {
        REP(l, n-i) {
            int r = l + i;
            dp[l][r] = (dp[l+1][r] + dp[l][r-1]) * occ[l][r];
        }
    }
 
    cout << dp[0][n-1] << endl;
 
    //Display(occ, n, n);
    //Display(dp, n, n);
}

进一步我们观察 occ 数组。发现它很有规律，于是可以使用分治 FFT。。。

Posted by xiaodao
Category: 日常

某岛

LiberOJ #3723. 「SDOI / SXOI2022」子串统计

题意

Archives

Blogroll

Links

Myself

Project