over 1 year ago

BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡

给定一棵树和每个节点的颜色,求颜色序列不同的链的个数(AB和BA是不同的),其中叶子节点个数不超过20。

对于每条链一定存在一个叶子节点使得链上的点都是祖辈关系。
叶子节点这么少枚举每个叶子当根,多串建立后缀自动机就好了。

又被卡了数组,又被卡了int.QAQ.

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <cstring>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define fi first
#define se second
#define rep(x,s,t) for(register int t_=t,x=s;x<t_;x++)
#define per(x,s,t) for(register int s_=s,x=(t)-1;x>=s_;x--)
#define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define y1 asfkagn
#define y2 fansfk
#define rank gkalsfm
#define hash gafgalsf
#define inf (1<<30)
#define INF (1ll<<61)
#define showtime printf("%f",1.0*clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

const long double pi=acos(-1);

template<class T>void sc(T &x)
{
    int f=1;char c;x=0;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x)
{
    if(!x)return;
    nt(x/10);
    putchar('0'+x%10);
}
template<class T>void pt(T x)
{
    if(x<0)x=-x,putchar('-');
    if(!x)putchar('0');
    else nt(x);
}
template<class T>void pts(T x)
{
    pt(x);putchar(' ');
}
template<class T>void ptn(T x)
{
    pt(x);putchar('\n');
}

template<class T>inline void Max(T &x,T y){if(x<y)x=y;}
template<class T>inline void Min(T &x,T y){if(x>y)x=y;}

const int maxn=100005;
const int maxm=10;
const int NUM=20;
int n,m,col[maxn];

namespace G
{
    int last[maxn],deg[maxn],ecnt;
    struct Edge
    {
        int to,nxt;
    }e[maxn<<1];
    void ins(int u,int v)
    {
        e[++ecnt]=(Edge){v,last[u]};
        last[u]=ecnt;
    }
    void GetG()
    {
        rep(i,1,n)
        {
            int u,v;
            sc(u);sc(v);
            deg[u]++;deg[v]++;
            ins(u,v);
            ins(v,u);
        }
    }
}
namespace SAM
{
    int last,tot,pre[maxn*NUM],son[maxn*NUM][maxm],v[maxn*NUM];//2*10^6+2*10^6+2*10^7+2*10^6
 void Init()
    {
        rep(i,0,tot+1)memset(son[i],0,m+1<<2);
        last=tot=1;
    }
    int update(int p,int x)
    {
        int q=son[p][x],nq=++tot;
        v[nq]=v[p]+1;
        memcpy(son[nq],son[q],m<<2);
        pre[nq]=pre[q];
        pre[q]=nq;
        for(;son[p][x]==q;p=pre[p])son[p][x]=nq;
        return nq;
    }
    void ins(int x)
    {
        int p=last,np=++tot;
        v[np]=v[last]+1;
        for(;!son[p][x];p=pre[p])son[p][x]=np;
        if(!p)pre[np]=1;
        else
        {
            int q=son[p][x];
            if(v[q]!=v[p]+1)pre[np]=update(p,x);
            else pre[np]=q;
        }
        last=np;
    }
}
bool vis[maxn];
void dfs(int x)
{
    vis[x]=true;  
    using namespace SAM;
    
    int k=son[last][col[x]];
    if(!k)ins(col[x]);
    else if(v[last]+1!=v[k])last=update(last,col[x]);
    else last=k;

    int backup=last;
    for(int i=G::last[x];i;i=G::e[i].nxt)
    if(!vis[G::e[i].to])
    {
        last=backup;
        dfs(G::e[i].to);
    }
    vis[x]=false;
}
ll count()
{
    using namespace SAM;
    ll ans=0;
    rep(i,1,tot+1)
    ans+=v[i]-v[pre[i]];
    return ans;
}
int main()
{
// freopen("pro.in","r",stdin);
//  freopen("chk.out","w",stdout);
 sc(n);sc(m);
    rep(i,1,n+1)
    sc(col[i]);
    
    G::GetG();
    SAM::Init();
    
    rep(i,1,n+1)
    if(G::deg[i]==1)
    {
        SAM::last=1;
        dfs(i);
    }
    ptn(count());
    return 0;
}
 
over 1 year ago

BZOJ 3676: [Apio2014]回文串

给一个串求回文串 长度×出现次数 的最大值
|S|≤300000.

该出现的早已出现╰( ̄▽ ̄)╭。
统计次数的方式和SAM如出一辙。

参考文献:

有关回文自动机PAM的探讨-PHX
Palindromic Tree——回文树【处理一类回文串问题的强力工具】-poursoul

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <cstring>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define fi first
#define se second
#define rep(x,s,t) for(register int t_=t,x=s;x<t_;x++)
#define per(x,s,t) for(register int s_=s,x=(t)-1;x>=s_;x--)
#define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define y1 asfkagn
#define y2 fansfk
#define rank gkalsfm
#define hash gafgalsf
#define inf (1<<30)
#define INF (1ll<<61)
#define showtime printf("%f",1.0*clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

const long double pi=acos(-1);

template<class T>void sc(T &x)
{
    int f=1;char c;x=0;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x)
{
    if(!x)return;
    nt(x/10);
    putchar('0'+x%10);
}
template<class T>void pt(T x)
{
    if(x<0)x=-x,putchar('-');
    if(!x)putchar('0');
    else nt(x);
}
template<class T>void pts(T x)
{
    pt(x);putchar(' ');
}
template<class T>void ptn(T x)
{
    pt(x);putchar('\n');
}

template<class T>inline void Max(T &x,T y){if(x<y)x=y;}
template<class T>inline void Min(T &x,T y){if(x>y)x=y;}

const int maxn=300010;
ll ans;
char str[maxn];
namespace PAM
{
    int pre[maxn],v[maxn],c[maxn],son[maxn][26],tot,last;
    void Init()
    {
        rep(i,0,tot+1)
        {
            v[i]=c[i]=0;
            memset(son[i],0,sizeof son[i]);
        }
        last=0;tot=1;
        v[1]=-1;pre[0]=1;
    }
    void ins(char ch,int n)
    {
        int x=ch-'a';
        while(str[n]!=str[n-v[last]-1])last=pre[last];
        if(!son[last][x])
        {
            ++tot;
            v[tot]=v[last]+2;
            int k=pre[last];
            while(str[n]!=str[n-v[k]-1])k=pre[k];
            pre[tot]=son[k][x];
            son[last][x]=tot;
        }
        last=son[last][x];
        ++c[last];
    }
}
int Solve()
{
    using namespace PAM;
    per(i,1,tot+1)
    {
        Max(ans,1ll*c[i]*v[i]);
        c[pre[i]]+=c[i];
    }
}
int main()
{
// freopen("pro.in","r",stdin);
//  freopen("chk.out","w",stdout);
 scanf("%s",str+1);
    ans=-1;
    PAM::Init();
    for(int i=1;str[i];i++)PAM::ins(str[i],i);
    Solve();
    ptn(ans);
    return 0;
}
 
over 1 year ago

POJ 3415 Common Substrings

给出两个串,问这两个串的所有的子串中(重复出现的,只要是位置不同就算两个子串),长度大于等于k的公共子串有多少个。
注意含大小写字母。

参考文献

后缀自动机回忆录-ShinFeb

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <cstring>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define fi first
#define se second
#define rep(x,s,t) for(register int t_=t,x=s;x<t_;x++)
#define per(x,s,t) for(register int s_=s,x=(t)-1;x>=s_;x--)
#define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define y1 asfkagn
#define y2 fansfk
#define rank gkalsfm
#define hash gafgalsf
#define inf (1<<30)
#define INF (1ll<<61)
#define showtime printf("%f",1.0*clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

const long double pi=acos(-1);

template<class T>void sc(T &x)
{
    int f=1;char c;x=0;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x)
{
    if(!x)return;
    nt(x/10);
    putchar('0'+x%10);
}
template<class T>void pt(T x)
{
    if(x<0)x=-x,putchar('-');
    if(!x)putchar('0');
    else nt(x);
}
template<class T>void pts(T x)
{
    pt(x);putchar(' ');
}
template<class T>void ptn(T x)
{
    pt(x);putchar('\n');
}
template<class T>inline void Max(T &x,T y){if(x<y)x=y;}
template<class T>inline void Min(T &x,T y){if(x>y)x=y;}

const int maxn=200005;//2 times
int K;
char A[maxn],B[maxn];
int na,nb;
int wa[maxn],wb[maxn];//sort
int such(char c)
{
    if(c>='a')return c-'a'+26;
    return c-'A';
}
namespace SAM
{
    int last,tot;
    int son[maxn][52],pre[maxn],v[maxn];
    void Init()
    {
        rep(i,1,tot+1)
        {
            memset(son[i],0,sizeof son[i]);
            pre[i]=0;
        }
        last=tot=1;
    }
    void update(char ch)
    {
        int p=last,np=++tot,x=such(ch);
        v[np]=v[p]+1;
        for(;!son[p][x];p=pre[p])son[p][x]=np;
        if(!p)pre[np]=1;
        else
        {
            int q=son[p][x];
            if(v[p]+1!=v[q])
            {
                int nq=++tot;
                v[nq]=v[p]+1;
                memcpy(son[nq],son[q],sizeof son[q]);
                pre[nq]=pre[q];
                pre[q]=pre[np]=nq;
                for(;son[p][x]==q;p=pre[p])son[p][x]=nq;
            }
            else pre[np]=q;
        }
        last=np;
    }
    void Print()
    {
        rep(i,1,tot+1)
        {
            prt(i);prtn(pre[i]);
            rep(j,0,26)if(son[i][j])
            putchar(j+'a'),putchar(':'),ptn(son[i][j]);
        }
    }
}
int c[maxn],d[maxn],f[maxn];
void Solve()
{
    using namespace SAM;
    rep(i,0,na+1)wa[i]=0;
    rep(i,1,tot+1)wa[v[i]]++;
    rep(i,1,na+1)wa[i]+=wa[i-1];
    rep(i,1,tot+1)wb[wa[v[i]]--]=i;
    
    rep(i,1,tot+1)c[i]=d[i]=0;
    int k=1;
    rep(i,0,na)
    {
        k=son[k][such(A[i])];
        c[k]++;
    }
    per(i,1,tot+1)c[pre[wb[i]]]+=c[wb[i]];

    ll ans=0;
    
    k=1;
    int lcs=0;
    rep(i,0,nb)
    {
        int x=such(B[i]);
        for(;k>1&&!son[k][x];k=pre[k],lcs=v[k]);
        if(!son[k][x])continue;
        k=son[k][x];lcs++;
        if(lcs<K)continue;
        ans+=1ll*c[k]*(lcs-max(K-1,v[pre[k]]));
        d[pre[k]]++;
    }
    per(i,1,tot+1)d[pre[wb[i]]]+=d[wb[i]];
    
    rep(i,2,tot+1)
    {
        k=v[i]-max(K-1,v[pre[i]]);
        if(k<=0)continue;
        ans+=1ll*c[i]*d[i]*k;
    }
    ptn(ans);
}
int main()
{
// freopen("pro.in","r",stdin);
//  freopen("chk.out","w",stdout);
 while(~scanf("%d",&K),K)
    {
        scanf("%s%s",A,B);
        na=strlen(A);
        nb=strlen(B);
        if(K>na||K>nb)
        {
            puts("0");
            continue;
        }
        SAM::Init();
        rep(i,0,na)SAM::update(A[i]);
//     SAM::Print();
     Solve();
    }
    return 0;
}
 
over 1 year ago

By ShinFeb

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <cstring>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define rep(x,s,t) for(register int t_=t,x=s;x<t_;x++)
#define per(x,s,t) for(register int s_=s,x=(t)-1;x>=s_;x--)
#define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define y1 asfkagn
#define y2 fansfk
#define rank gkalsfm
#define hash gafgalsf
#define inf (1<<30)
#define INF (1ll<<61)
#define showtime printf("%f",1.0*clock()/CLOCKS_PER_SEC)
typedef long long ll;
typedef double db;
typedef pair<int,int> ii;
const long double pi=acos(-1);
template<class T>void sc(T &x)
{
    int f=1;char c;x=0;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x)
{
    if(!x)return;
    nt(x/10);
    putchar('0'+x%10);
}
template<class T>void pt(T x)
{
    if(x<0)x=-x,putchar('-');
    if(!x)putchar('0');
    else nt(x);
}
template<class T>void pts(T x)
{
    pt(x);putchar(' ');
}
template<class T>void ptn(T x)
{
    pt(x);putchar('\n');
}
template<class T>inline void Max(T &x,T y){if(x<y)x=y;}
template<class T>inline void Min(T &x,T y){if(x>y)x=y;}

const int mod=998244353;
const int maxn=262144;

int a[maxn],b[maxn];
int qpow(int a,int b,int mod=::mod)
{
    int c=1;
    for(;b;b>>=1,a=(ll)a*a%mod)
        if(b&1)c=(ll)a*c%mod;
    return c;
}
namespace FFT{
    const int maxb=25;
    const int g=3,ng=332748118;
    //mod=998244353
 
    int n,L,rev[maxn];
    int G[maxb],nG[maxb],fra;
    
    void dft(int *a,int f)
    {
        rep(i,0,n)if(rev[i]<i)swap(a[i],a[rev[i]]);
        for(int m=1,now=1;m<n;m<<=1,now++)
        {
            int w=f==1?G[now]:nG[now];
            for(int i=0;i<n;i+=m<<1)
            {
                int cur=1;
                for(int j=0;j<m;j++)
                {
                    int x=a[i+j],y=1ll*a[i+j+m]*cur%mod;
                    a[i+j]=(x+y)%mod;
                    a[i+j+m]=(x-y+mod)%mod;
                    cur=1ll*cur*w%mod;
                }
            }
        }
        if(f==-1)rep(i,0,n)a[i]=1ll*a[i]*fra%mod;
    }
    void InitN(int nn)
    {
        for(n=1,L=0;n<nn;n<<=1)L++;
        rep(i,1,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<L-1);
        fra=qpow(n,mod-2);
    }
    void InitG()
    {
        int tmp=mod-1,t=0;
        do{
            tmp>>=1;
            G[++t]=qpow(g,tmp);
            nG[t]=qpow(ng,tmp);
        }while(~tmp&1);
    }
    void fft(int *a,int *b,int *c,int na,int nb,int &nc)
    {
        int nn=na+nb-1;
        InitN(nn);
        rep(i,na,n)a[i]=0;
        rep(i,nb,n)b[i]=0;
        dft(a,1);dft(b,1);
        rep(i,0,n)c[i]=(ll)a[i]*b[i]%mod;
        dft(c,-1);
        nc=nn;
    }
}

int main()
{
// freopen("pro.in","r",stdin);
//  freopen("chk.out","w",stdout);
 int na,nb;
    sc(na);sc(nb);++na;++nb;
    rep(i,0,na)sc(a[i]);
    rep(i,0,nb)sc(b[i]);
    
    FFT::InitG();
    FFT::fft(a,b,a,na,nb,na);
    rep(i,0,na)pt(a[i]),putchar(" \n"[i==na-1]);
    return 0;
}
 
over 1 year ago

Hi, This a demo post of Logdown.

Logdown use Markdown as main syntax, you can find more example by reading this document on Wikipedia

Logdown also support drag & drop image uploading. The picture syntax is like this:

Bloging with code snippet:

inline code

Plain Code

puts "Hello World!"

Code with Language

puts "Hello World!"

Code with Title

hello_world.rb
puts "Hello World!"

MathJax Example

Mathjax

Inline Mathjax

The answser is .

Table Example

Tables Are Cool
col 1 Hello $1600
col 2 Hello $12
col 3 Hello $1