先来一波胡测（未完）

Round 0

T1 po姐的送温暖题，但是我为啥就没去想 >.<

统计从左上到右下两条路径不相交的方案数。

如果只有一条路这是普及组。

记 $f(i,j,k,l)$ 为从 $(i,j)$到$(k,l)$的方案数。

如果我们没有相交，显然有

$$ans = f(2,1,n,m-1) cdot f(1,2,n-1,m)$$

接下来考虑只统计相交的路径。

神思路：

找到最后一个交点，转一下变为$(2,1)$走到$(n-1,m)$的路径和一条从$(1,2)$走到$(n,m-1)$的路径

然后我们惊讶地发现原先每种不合法的方案对应一个反转后的方案。

所以相交的对数为

$$f(1,2,n,m-1) cdot f(2,1,n-1,m)$$

思路很神，但是代码就没什么意思了。。。

T2 zrt的题，HEOI Day2 T3加强版

在一个子序列自动机和一个后缀自动机上dfs记忆化，有$O(n)$的边，$O(n^2)$的状态。

然后就没有然后了。。。

#include <cstdio>
#include <cstring>

#define N 4010
#define LL long long
#define mod 1000000007

using namespace std;

struct node{
    node *ch[26],*fa;
    int len,id;
    LL v;
};

struct SAM{
    node *root,spT[N<<1],*now;

    int tot;

    void addin(char c){
        int t=c-'a';
        node *np=&spT[++tot],*p=now;
        np->id=tot;
        np->len=p->len+1;
        now=np;
        for(;p&&!p->ch[t];p=p->fa) p->ch[t]=np;
        if(!p) np->fa=root;
        else{
            if(p->ch[t]->len==p->len+1) np->fa=p->ch[t];
            else{
                node *nq=&spT[++tot],*q=p->ch[t];
                *nq=*q;
                nq->len=p->len+1;
                nq->id=tot;
                q->fa=np->fa=nq;
                for(;p&&p->ch[t]==q;p=p->fa) p->ch[t]=nq;
            }
        }
    }
    
    void dfs(node *p){
        p->v=1;
        for(int i=0;i<26;i++)
            if(p->ch[i]){
                if(!p->ch[i]->v) dfs(p->ch[i]);
                (p->v+=p->ch[i]->v)%=mod;
            }
    }
    
    void build(char *S){
        now=root=&spT[tot=1];
        int len=strlen(S);
        for(int i=0;i<len;i++) addin(S[i]);
        dfs(root);
    }
}A1,A2;

struct SBM{
    node spT[N],*root,*a[26];
    int tot;
    
    void build(char *S){
        root=&spT[tot=1];
        root->id=tot;
        for(int i=0;i<26;i++) a[i]=NULL;
        for(int i=strlen(S)-1;~i;i--){
            node *p=&spT[++tot];
            p->id=tot;
            p->v=1;
            memcpy(p->ch,a,sizeof(a));
            for(int t=0;t<26;t++)
                if(p->ch[t]) (p->v+=p->ch[t]->v)%=mod;
            int t=S[i]-'a'; a[t]=p;
        }
        memcpy(root->ch,a,sizeof(a));
        for(int i=0;i<26;i++)
            if(root->ch[i]) root->v+=root->ch[i]->v;
    }
}B1,B2;

char S1[N],S2[N];
LL f[N][N];

LL dfs(node *a,node *b){
    if(!b) return a->v;
    if(f[a->id][b->id]!=-1) return f[a->id][b->id];
    LL ans=0;
    for(int t=0;t<26;t++)
        if(a->ch[t]) (ans+=dfs(a->ch[t],b->ch[t]))%=mod;
    return f[a->id][b->id]=ans;
}

int main(){
    scanf("%s%s",S1,S2);
    A1.build(S1);
    A2.build(S2);
    B1.build(S1);
    B2.build(S2);
    memset(f,-1,sizeof(f));
    printf("%lld
",dfs(A1.root,A2.root));
    memset(f,-1,sizeof(f));
    printf("%lld
",dfs(A1.root,B2.root));
    memset(f,-1,sizeof(f));
    printf("%lld
",dfs(B1.root,A2.root));
    memset(f,-1,sizeof(f));
    printf("%lld
",dfs(B1.root,B2.root));
    return 0;
}

View Code

ioi：“这种做法虽然在修改上多了一个log，但是由于常熟十分小，期望分数还是100分的”

相关推荐