2018年全国多校算法寒假训练营练习比赛(第五场) C KMP-Next数组

Next数组

自己写的卡在%95.00的代码

我自己写的代码,至今想不通漏了什么情况,被卡在%95.00…

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001000;
int Next[maxn],len;
char str[maxn];

map<int,int> ex;

void getNext(){
    Next[0]=-1;
    int k=-1;
    int j=0;
    while(j<len){
        if(k==-1 || str[j]==str[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void print(){
    for(int i=1;i<=len;++i){
        printf("%d ",Next[i]);
    }
}

void solve(){
    ex.clear();
    getNext();
    //print();
    int bef=Next[len],now,max_len=0;
    if(bef==0){
        printf("Just a legend\n");
        return;
    }
    while(bef!=0){
        now=bef;
        bef=Next[bef];
    }

    for(int i=1;i<=len;++i){
        if(Next[i] && Next[i]%now==0){
            int k=Next[i]/now;
            for(int j=1;j<=k;++j){
                ex[j*now]++;
            }
        }
    }
    map<int,int>::iterator it;
    for(it=ex.begin();it!=ex.end();it++){
        if(it->second>1) max_len=max(max_len,it->first);
    }
    if(max_len){
        max_len=min(max_len,Next[len]);
        for(int i=0;i<max_len;++i){
            printf("%c",str[i]);
        }
    }else printf("Just a legend");
    printf("\n");
}

int main(){
    while(cin>>str){
        len=strlen(str);
        solve();
    }
    return 0;
}

AC代码

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001000;
int Next[maxn],len;
char str[maxn];

int exist[maxn];

void getNext(){
    Next[0]=-1;
    int k=-1;
    int j=0;
    while(j<len){
        if(k==-1 || str[j]==str[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void solve(){
    memset(exist,0,sizeof(exist));
    getNext();
    int bef=Next[len];
    if(bef==0){
        printf("Just a legend\n");
        return;
    }
    //忽略第一个和最后一个
    for(int i=2;i<len;++i){
        exist[Next[i]]++;
    }

    while(bef>0){
        if(exist[bef]){
            for(int i=0;i<bef;++i){
                printf("%c",str[i]);
            }
            printf("\n");
            return;
        }
        bef=Next[bef];
    }
    printf("Just a legend\n");
}

int main(){
    while(cin>>str){
        len=strlen(str);
        solve();
    }
    return 0;
}

当然,还有一种方法是比较特别的(比较直观),把每个可能子串KMP一下,如果匹配成功了,就直接输出就好了

#include<cstdio>
#include<cstring>
char a[1000005],b[1000005];
int next[1000006];
void getnext(char *c)
{
    next[0]=next[1]=0;
    int i,j,len=strlen(c);
    for(i=1,j=0;i<len;i++)
    {
        while(c[i]!=c[j]&&j!=0)
            j=next[j];
        if(c[i]==c[j])j++;
        next[i+1]=j;
    }
}
int kmp(char *o,char *f)
{
    int cont=0;
    int i,j,len1=strlen(o),len2=strlen(f);
    for(i=0,j=0;i<len1;i++)
    {
        while(o[i]!=f[j]&&j!=0)
            j=next[j];
        if(o[i]==f[j])j++;
        if(j==len2)
        {
            cont++;
            j=next[j];
        }
    }
    return cont;
}
int main()
{
    int i;
    scanf("%s",a);
    getnext(a);
    int len=next[strlen(a)];
    if(len==0)
    {
        printf("Just a legend\n");
        return 0;
    }
    for(i=0;i<len;i++)
        b[i]=a[i];
    b[i]='\0';
    int cont=kmp(a,b);
    while(cont<3)
    {
        len=next[len];
        if(len==0)break;
        for(i=0;i<len;i++)
            b[i]=a[i];
        b[i]='\0';
        cont=kmp(a,b);
    }
    if(cont>=3&&len)printf("%s\n",b);
    else printf("Just a legend\n");
    return 0;
}

1

2

技巧论 QAQ

凡事要讲究技巧,无技不成巧,先将遇到的技巧记录下来..

对的…这特么就是一个远古巨坑

中途相遇法(又称折半枚举,双向搜索)

思想论

如果纬度特别高时,比如数据量为N,总情况数为N^4,全部遍历一遍是肯定不可以的,不过可以将它们折半成AB和CD再考虑,就可以快速解决了.

从两个数列中考虑的话,就只剩下N^2种情况了,因此对两半枚举完以后排一下序,就可以用二分搜索了.

例题:山东第一届省赛 D

右侧标签云中找一下第一节山东省塞即可

爬梯法

尺取法

思想:

规定那个两个点,先固定左端点,如果小于答案,则右端点向右走,否则左端点向左走
POJ 3061

分块法

51nod 1225

倍增算法

康托展开

山东省第一届省赛

A: 可水可Trie,Trie解法

数据不大,因为题目没有给出字符串的大小,害怕暴力超时,所以用Trie写的.

#include<bits/stdc++.h>
using namespace std;
const int CHARSET=10,BASE='0',MAX_NODE=10100;
struct Trie{
    int tot,root,child[MAX_NODE][CHARSET];
    bool flag[MAX_NODE];
    bool has_prefix;
    bool is_root[MAX_NODE][CHARSET];
    Trie(){
        //printf("New Trie\n");
        memset(child[1],0,sizeof(child[1]));
        memset(is_root,false,sizeof(is_root));
        flag[1]=false;
        has_prefix=false;
        root=tot=1;
    }
    void insert(const char *str){
        int *cur=&root;
        char last_char;
        for(const char *p=str;*p;++p){
            cur=&child[*cur][*p-BASE];
            last_char=*p;
            if(is_root[*cur][last_char])has_prefix=true;
            if(*cur==0){
                *cur=++tot;
                memset(child[tot],0,sizeof(child[tot]));
                flag[tot]=false;
            }
        }
        flag[*cur]=true;
        is_root[*cur][last_char]=true;
    }

};
int main(){
    int n;
    while(~scanf("%d",&n) && n){
        Trie te;
        char str[10000];
        for(int i=0;i<n;++i){
            scanf("%s",str);
            if(!te.has_prefix){
                te.insert(str);
            }
        }
        if(te.has_prefix){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    return 0;
}

B:思路比较清晰,就是写的时间长,我写了两份代码

单树(map)套结构体Point重载<+二分: 内存小,时间长

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
struct Point{
    int x,y;
    bool operator < (const Point& a)const{
        if(x<a.x) return true;
        else if(x==a.x && y<a.y) return true;
        return false;
    }
    bool operator == (const Point& a)const{
        if(x==a.x && y==a.y) return true;
        return false;
    }

};
int N,kase=1;

int xx,yy;
char opt[10];

map<Point,bool> G;//x点集0,true为未删除,false为删除
map<Point,bool>::iterator it;

void init(){
    G.clear();
}

bool cmp(Point a,Point b){
    if(a.x<b.x && a.y<b.y)
        return true;
    return false;
}

void add(){
    G[(Point){xx,yy}]=true;
}

void find_(int a,int b){
    it=G.upper_bound((Point){a,b});
    if(it==G.end()){
        printf("-1\n");
        return;
    }
    Point nw=it->first;
    if(it->second && nw.x>xx && nw.y>yy){
        printf("%d %d\n",nw.x,nw.y);
    }else{
        do{
            it++;
            if(it==G.end()){printf("-1\n");return;}
            if(it->second && (it->first).x>xx && (it->first).y>yy){
                printf("%d %d\n",(it->first).x, (it->first).y);
                return;
            }
        }while(1);
    }
}

void remove_(){
    G[(Point){xx,yy}]=false;
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        printf("Case %d:\n",kase++);
        for(int i=0;i<N;++i){
            scanf("%s %d %d",opt,&xx,&yy);
            if(opt[0]=='a'){
                add();
            }else if(opt[0]=='f'){
                find_(xx,yy);
            }else{
                remove_();
            }
        }
        printf("\n");
    }
    return 0;
}

/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 904ms
Take Memory: 5752KB
Submit time: 2018-02-27 17:08:24
****************************************************/

树(map)+二分套树(map)+二分,代码少,时间短,内存大

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;

int N,kase=1;

int xx,yy;
char opt[10];

map<int,map<int,bool> > G;//x点集0,true为未删除,false为删除
map<int,bool>::iterator ity;
map<int,map<int,bool> >::iterator itx;

void init(){
    G.clear();
}

void add(){
    (G[xx])[yy]=true;
}

void find_(){
    itx=G.upper_bound(xx);
    while(1){
        if(itx!=G.end()){
            ity=(itx->second).upper_bound(yy);
            if(ity!=(itx->second).end() && ity->second){
                printf("%d %d\n",itx->first,ity->first);
                return;
            }
            if(ity!=(itx->second).end()){
                for(ity++;ity!=(itx->second).end();ity++){
                    if(ity->second){
                        printf("%d %d\n",itx->first,ity->first);
                        return;
                    }
                }
            }
        }else break;
        itx++;
    }
    printf("-1\n");
}

void remove_(){
    (G[xx])[yy]=false;
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        printf("Case %d:\n",kase++);
        for(int i=0;i<N;++i){
            scanf("%s %d %d",opt,&xx,&yy);
            if(opt[0]=='a'){
                add();
            }else if(opt[0]=='f'){
                find_();
            }else{
                remove_();
            }
        }
        printf("\n");
    }
    return 0;
}


/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 516ms
Take Memory: 12712KB
Submit time: 2018-02-27 17:24:44
****************************************************/

然后我百度一下原题,发现set直接删除就好…还是STL不太熟,内存小,用时也少,不过没第二份少

    #include <iostream>  
    #include <stdio.h>  
    #include <algorithm>  
    #include <set>  
    #include <string>  
    using namespace std;  

    int main()  
    {  
        pair<int,int>p;  
        int n;char str[10];  
        int c=1;  
        while(cin>>n&&n)  
        {  
            cout<<"Case "<<c++<<":"<<endl;  
            set< pair<int,int> >s;  
            while(n--)  
            {  
                scanf("%s",str);  
                scanf("%d%d",&p.first,&p.second);  
                if(str[0]=='a')  
                    s.insert(p);  
                else if(str[0]=='r')  
                    s.erase(p);  
                else if(str[0]=='f')  
                {  
                    set< pair<int,int> >::iterator it;  
                    it=s.lower_bound(p);//找到set中第一个比p大的元素的位置,找不到则为s.end()  
                    for(;it!=s.end();it++)  
                    {  
                        if(it->first>p.first&&it->second>p.second)//都大于才符合题意  
                        {  
                            cout<<it->first<<" "<<it->second<<endl;  
                            break;  
                        }  
                    }  
                    if(it==s.end())//找不到  
                        cout<<-1<<endl;  
                }  
            }  
            cout<<endl;  
        }  
        return 0;  
    }  

貌似还可以用线段树优化..

F**k

C:排序水过,别问我为啥写的那么麻烦…因为我半截才想到,懒得改了

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
struct Query{
    int s,t;
};
int N,kase=1;
int main(){
    while(~scanf("%d",&N) && N){
        priority_queue<int,vector<int>,greater<int> > G[maxn];
        priority_queue<int,vector<int>,greater<int> > it;
        vector<Query> Q;
        for(int i=1;i<=N;++i){
            int s,t;
            scanf("%d%d",&s,&t);
            G[s].push(t);
            Q.push_back((Query){s,t});
        }
        printf("Case %d:\n",kase++);
        for(int i=0;i<Q.size();++i){
            int s=Q[i].s,t=Q[i].t;
            bool has_ans=false;
            for(int j=s+1;j<=309 && !has_ans;++j){
                it=G[j];
                while(!it.empty()){
                    int nw=it.top();it.pop();
                    if(nw>t){
                        has_ans=true;
                        printf("%d %d\n",j,nw);
                        break;
                    }
                }
            }
            if(!has_ans){
                printf("-1 -1\n");
            }
        }
        printf("\n");
    }
    return 0;
}

D:中途相遇法+负值二分

因为内置的lower_bound只能查找第一个大于等于的,而我们需要的是小于等于的,所以将所有的值变成负数插入到vector中即可.

这道题N^4肯定是不可行的.所以我们考虑用中途相遇法,

即先处理出任意两个值的和,然后遍历和数组,在原数组中查找是否存在一个值和当前和相加<=M,如果等于M,break即可.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int maxn=2000;
int N,M,KASE=1;
int arr[maxn];
vector<int> first;
int main(){
    while(~scanf("%d%d",&N,&M) && N+M){
        first.clear();
        int ans=0;
        for(int i=0;i<N;++i) scanf("%d",&arr[i]);
        for(int i=0;i<N;++i){
            for(int j=i;j<N;++j){
                first.push_back(-(arr[i]+arr[j]));
            }
        }
        sort(first.begin(),first.end());
        for(int i=0;i<first.size();++i){
            int need=M+first[i];
            if(need<=0) continue;
            else{
                int id=lower_bound(first.begin(),first.end(),-need)-first.begin();
                int nw=-(first[i]+first[id]);
                if(nw<=M) ans=max(ans,nw);
            }
            if(ans==M)break;
        }
        printf("Case %d: %d\n\n",KASE++,ans);
    }
    return 0;
}

G:排序水过

一开始没读懂题意时最难受的

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100100;
int Dist[maxn],N;
int main(){
    while(~scanf("%d",&N) && N){
        for(int i=0;i<N;++i){
            scanf("%d",&Dist[i]);
        }
        sort(Dist,Dist+N);
        LL ans=0ll;
        for(int i=1;i<N;++i){
            ans+=((Dist[i]-Dist[i-1])<<1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

I:分别进行两个dfs即可,四方向和八方向

#include<bits/stdc++.h>
using namespace std;

int move1[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int move2[8][2]={{0,-1},{0,1},{-1,0},{1,0},
                 {1,-1},{1,1},{-1,-1},{-1,1}};
char mp[110][110];
int N,kase=1;
int vis1[110][110],vis2[110][110];

void init(){
    memset(vis1,0,sizeof(vis1));
    memset(vis2,0,sizeof(vis2));
}

bool check(int x,int y){
    if(x>=N || y>=N || x<0 || y<0 || mp[x][y]=='0')
        return false;
    return true;
}

void dfs4(int x,int y){
    if(!check(x,y) || vis1[x][y]) return;
    vis1[x][y]=1;
    for(int i=0;i<4;++i){
        int nx=x+move1[i][0],ny=y+move1[i][1];
        dfs4(nx,ny);
    }
}

void dfs8(int x,int y){
    if(!check(x,y) || vis2[x][y]) return;
    vis2[x][y]=1;
    for(int i=0;i<8;++i){
        int nx=x+move2[i][0],ny=y+move2[i][1];
        dfs8(nx,ny);
    }
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        for(int i=0;i<N;++i){
            scanf("%s",mp[i]);
        }
        int ans4=0,ans8=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                if(mp[i][j]=='1' && !vis1[i][j]){
                    ans4++,dfs4(i,j);
                }
                if(mp[i][j]=='1' && !vis2[i][j]){
                    ans8++,dfs8(i,j);
                }
            }
        }
        printf("Case %d: %d %d\n\n",kase++,ans4,ans8);
    }
    return 0;
}

E:大模拟

大模拟

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;
const int maxn=35;
int N,kase=1;
char mp[maxn][maxn];
int vis[maxn][maxn][maxn][maxn][5];
///EWSN东西南北
int dis[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
///saya更喜欢EWNS
int nt[4][2]={{0,1},{0,-1},{-1,0},{1,0}};

bool check(int x,int y){
    if(x<0||y<0||x>=N||y>=N)return false;
    return true;
}
///返回当前的朝向在,数组为dis
int now_dir(int x,int y,int t){
    char str=mp[x][y];
    int in=0;
    if(str=='E') in=0;
    else if(str=='W') in=1;
    else if(str=='S') in=2;
    else in=3;
    in+=t;
    return in%4;
}

int dist(int x,int y,int tx,int ty){
    return (x-tx)*(x-tx)+(y-ty)*(y-ty);
}

int query_dir(int x,int y,int tx,int ty){
    int mind=INF,dir_=-1;
    for(int i=0;i<4;++i){
        int xx=x+nt[i][0],yy=y+nt[i][1];
        if(!check(xx,yy)) continue;
        int d=dist(xx,yy,tx,ty);
        if(mind>d){
            mind=d;
            dir_=i;
        }
    }
    ///返回第一个想走的方向
    return dir_;
}

int main(){
    while(scanf("%d",&N)!=EOF && N!=0){
        memset(vis,0,sizeof(vis));
        for(int i=0;i<N;++i){
            scanf("%s",&mp[i]);
        }
        int x=0,y=0,tx=N-1,ty=N-1,step=0;
        int xx,yy,txx,tyy;
        printf("Case %d:\n",kase++);
        while(1){
            if(step>=100){
                printf("Not sure.\n");
                break;
            }
            if(tx==x&&ty==y){
                printf("Get the treasure! At step %d.\n",step);
                break;
            }
            ///saya第一步
            int saya=now_dir(x,y,step);
            xx=x+dis[saya][0],yy=y+dis[saya][1];
            if(check(xx,yy)){
                x=xx,y=yy;
            }
            ///saya第二步
            if(!(x==tx&&y==ty)){
                int goal=query_dir(x,y,tx,ty);
                xx=x+nt[goal][0],yy=y+nt[goal][1];
                if(check(xx,yy)){
                    x=xx,y=yy;
                }
            }
            ///宝藏走
            int tres=now_dir(tx,ty,step);
            txx=tx+dis[tres][0],tyy=ty+dis[tres][1];
            if(check(txx,tyy)){
                tx=txx,ty=tyy;
            }

            if(vis[x][y][tx][ty][step%4]){
                printf("Impossible. At step %d.\n",step);
                break;
            }else{
                vis[x][y][tx][ty][step%4]=1;
            }
            step+=1;
        }
        printf("\n");
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛(第五场) G 斐波那契博弈

斐波那契博弈模板题,我凑…

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
set<int> st;
int FB[maxn];
int n;
inline void init(){
    FB[1]=1ll;FB[0]=1ll;
    int i;
    for(i=2;FB[i-1]<=1e9+7;++i){
        FB[i]=FB[i-1]+FB[i-2];
        st.insert(FB[i]);
    }
}

int main(){
    init();
    while(~scanf("%d",&n)){
        if(st.find(n)!=st.end()){
            cout<<"Sha"<<endl;
        }else{
            cout<<"Xian"<<endl;
        }
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛(第五场) H,F,B

H,和B是树状数组.F是水题,其实前两个也算水(模板)了.

需要提的是,H用的是树状数组的区间更新和区间查询.

H

#include<bits/stdc++.h>

#define lowbit(i) (i & (-i))

using namespace std;
typedef long long LL;
const int Nmax = 100100;
int N,Q;
LL delta[Nmax];//delta的前缀和
LL deltai[Nmax];//delta*i的前缀和
LL sum[Nmax];//原始前缀和

LL query(LL *arr,int pos){
    LL temp=0ll;
    while(pos>0){
        temp+=arr[pos];
        pos-=lowbit(pos);
    }
    return temp;
}

void update(LL *arr,int pos,int x){
    while(pos<=N){
        arr[pos]+=x;
        pos+=lowbit(pos);
    }
}

int main(){
    scanf("%d%d",&N,&Q);
    LL nw;
    char opt;
    for(int i=1;i<=N;++i){
        scanf("%lld",&nw);
        sum[i]=sum[i-1]+nw;
    }
    while(Q--){
        getchar();
        scanf("%c",&opt);
        if(opt=='C'){
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            update(delta, l, x);
            update(delta, r+1, -x);
            update(deltai, l, x * l);
            update(deltai, r+1, -x * (r+1));
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            LL suml = sum[l - 1] + l * query(delta, l - 1) - query(deltai, l - 1);
            LL sumr = sum[r] + (r + 1) * query(delta, r) - query(deltai, r);
            printf("%lld\n", sumr - suml);
        }
    }
    return 0;
}

B

#include<bits/stdc++.h>
#define lowbit(i) (i&(-i))
using namespace std;
typedef long long LL;
const int maxn=100100;
LL Tree[maxn];

void add(int x,int value){
    for(int i=x;i<=maxn;i+=lowbit(i)){
        Tree[i]+=value;
    }
}

LL get(int x){
    LL sum=0ll;
    for(int i=x;i;i-=lowbit(i)){
        sum+=Tree[i];
    }
    return sum;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        LL q;
        scanf("%lld",&q);
        add(i,q);
    }
    for(int i=0;i<m;++i){
        int ck;
        scanf("%d",&ck);
        if(ck==1){
            int x,k;
            scanf("%d%d",&x,&k);
            add(x,k);
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",get(r)-get(l-1));
        }
    }
    return 0;
}

F

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    while(cin>>n){
        while(n/10){
            int nn=0;
            while(n>0){
                nn+=(n%10);
                n/=10;
            }
            n=nn;
        }
        cout<<n<<endl;
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛(第五场) A 逆序数

链接:https://www.nowcoder.com/acm/contest/77/A
来源:牛客网

题目描述

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2, 那么这个序列的逆序数为7,逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

输入描述:

第一行有一个整数n(1 <= n <= 100000), 然后第二行跟着n个整数,对于第i个数a[i],(0 <= a[i] <= 100000)。

输出描述:

输出这个序列中的逆序数

示例1

输入

5
4 5 1 3 2

输出

7

两种方法求逆序数

归并排序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100010;

int seq[maxn],N;
int temp[maxn];
LL cnt;
//归并排序求逆序数
void merge_sort(int arr[],int l,int r){
    if(l==r)return;
    int mid=((l+r)>>1);
    merge_sort(arr,l,mid);
    merge_sort(arr,mid+1,r);
    int i=l,j=mid+1;
    for(int k=l;k<=r;++k){
        if(j>r || (i<=mid && arr[i]<arr[j]))temp[k]=arr[i++];
        else temp[k]=arr[j++],cnt+=mid-i+1;
        //如果a[i]>a[j]则逆序数加上mid+1-i,即剩下的前面个数
    }
    for(i=l;i<=r;++i)arr[i]=temp[i];
}

int main(){
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>seq[i];
    }
    cnt=0;
    merge_sort(seq,0,N-1);
    cout<<cnt<<endl;
    return 0;
}

树状数组

POJ 1961

Link

https://vjudge.net/problem/UVALive-3026

Type: KMP-Next数组

题意

给你一个字符串,输出这个字符串中所有的周期子串最后一个字符的下标和周期长度

题解

前置

关于Next数组

(1) Next数组记录的是如果当前字符不匹配,跳到哪个字符进行再次匹配.

(2) j=Next[k]表示第 j 个字符和第 k 个字符一样.

(3) j=Next[k]表示前 j 个字符和后 j 个字符一样

即 1~j-1 和 k-j+1~k 这两个子串相等

正文

即我们求出该字符串的Next数组后我们可以判断当前 (i-Next[i]) 是否能被 i 整除.

即 i%(i-Next[i]) 是否等于0.

i-Next[i]为该子串的长度,如果可以整除则证明该子串为循环节,循环节长度为 i-Next[i] ,循环次数为 i/(i-Next[i]).

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
char ts[maxn];
int n,kase=1;
int Next[maxn];
void getNext(){
    int j=0,k=-1;
    Next[0]=-1;
    while(j<n){
        if(k==-1 || ts[j]==ts[k]) Next[++j]=++k;
        else k=Next[k];
    }
}
void print(){
    for(int i=1;i<=n;++i){
        cout<<Next[i]<<" ";
    }
    cout<<endl;
}

int main(){
    while(~scanf("%d",&n)){
        if(!n)break;
        scanf("%s",ts);
        getNext();
        //print();
        printf("Test case #%d\n",kase++);
        for(int i=2;i<=n;++i){
            if(Next[i]<=0) continue;
            if(i%(i-Next[i])==0){
                printf("%d %d\n",i,i/(i-Next[i]));
            }
        }
        printf("\n");
        getchar();
    }
    return 0;
}

字符串算法

Trie

这个…不想写了

KMP

朴素的对比字符串算法复杂度是O(mn)的.这样一来对两串比较长的字符串就显得略微低效了.

KMP算法的时间复杂度也不过O(m+n)

Next数组

对于KMP而言最重要的莫过于这个Next数组了.

Next数组最大的作用在于当匹配失败时,需要跳转到哪个下标.

构造方法:

Next[i]=max{j | j\<i 且N[1..j]=N[i-j+1..i]}

即Next[i]球的试串P[1..i]的一个最长的前缀P[1..j],这个前缀同时也是他的后缀。当这个前缀找不到的时候,Next[i]=0

例如:

模式串 P = ababc

则Next[4]=2,因为ab不仅是abab的前缀,也是他的后缀.

而Next[5]=0,因为无法找到ababc(P[1..5])的一个前缀同时又是他的后缀.

附上一张图

匹配时逻辑

KMP 在匹配时同时维护两个下标 i 和 j ,表示当前模式串 P 的前 j 个字符与主串 T 在位置 i 前的 j 个字符匹配,即 P[1..j]=T[i-j..i-1]。

当算法尝试对 T[i] 和 P[j+1] 匹配中遇到不相同的字符,就会通过Next数组进行跳跃。

算法实现

Next数组

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+7;
int Next[maxn];
string S,T;//S主串,T子串

void getNext(){
    int k=-1,len=T.length();
    int j=0;
    Next[0]=-1;
    while(j<len){
        //如果有相同前缀
        if(k==-1 || T[j]==T[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void print(){
    for(int i=0;i<T.length();++i){
        cout<<Next[i]<<" ";
    }
    cout<<endl;
}

int main(){
    while(cin>>T){
        getNext();
        print();
    }
    return 0;
}

几组数据

ababc
Next: -1 0 0 1 2

abcdef
Next: -1 0 0 0 0 0

abcdabce
Next: -1 0 0 0 0 1 2 3

abcabcabc
Next: -1 0 0 0 1 2 3 4 5

abcdabcabcd
Next: -1 0 0 0 0 1 2 3 1 2 3

KMP – 返回第一个匹配的下标

主程

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+7;
int Next[maxn];
string S,T;//S主串,T子串

void getNext(){
    int k=-1,len=T.length();
    int j=0;
    Next[0]=-1;
    while(j<len){
        //如果有相同前缀
        if(k==-1 || T[j]==T[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void print(){
    for(int i=0;i<T.length();++i){
        cout<<Next[i]<<" ";
    }
    cout<<endl;
}

int KMP_index(){
    int i=0,j=0,slen=S.length(),tlen=T.length();
    getNext();
    while(i<slen && j<tlen){
        if(j==-1 || S[i]==T[j]){
            i++;
            j++;
        }else j=Next[j];
    }
    if(j==tlen) return i-tlen;
    else return -1;
}

int main(){
    while(cin>>S>>T){
        int ans=KMP_index();
        if(ans==-1) cout<<"Failed!"<<endl;
        else cout<<"Succesed!String T was matched in index "<<ans<<"."<<endl;
        print();
    }
    return 0;
}

两组数据

IN[0]: jashdjashdjabababcabcsdas
IN[1]: abcabc
OUT[0]: Succesed!String T was matched in index 15.
OUT[1]: -1 0 0 0 1 2
IN[2]: jashdjashdjabababcabcsdas
IN[3]: abcabcd
OUT[2]: Failed!
OUT[3]: -1 0 0 0 1 2 3

AC-Corasick 自动机

思想是KMP+Trie,在Trie上建立失配指针.

常用于主串匹配多个字符串

尾节点记录字符串下标的AC自动机

优点是可以直接输出字符串.

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[10010][60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    ///Trie树
    int ch[maxn][sigma_size];
    ///后缀相关数组
    int f[maxn],last[maxn];
    ///个数信息,尾节点记录信息
    int cnt[maxn],val[maxn];
    ///总节点个数
    int siz;

    int all_su;///记录总共有多少不可重复子串

    void init(){
        siz=all_su=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s,int v){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=++siz;
            u=ch[u][c];
       }
       ///尾节点记录字符串在str数组的下标
       val[u]=v;
    }

    //Fail树
    void getFail(){
        queue<int> Q;
        f[0]=0;
        ///遍历取出第一个节点所有的前向字符
        for(int c=0;c<sigma_size;++c){
            int u=ch[0][c];
            if(u){
                f[u]=last[u]=0;
                Q.push(u);
            }
        }
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                int u=ch[k][c];
                if(!u) continue;
                Q.push(u);
                int v=f[k];
                while(v && !ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

    ///统计
    void add(int u){
        for(;u;u=last[u]){
            if(!cnt[val[u]]) all_su++;
            printf("\n%s\n",str[val[u]-1]);
            cnt[val[u]]++;
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            if(val[u]) add(u);
            else if(last[u]) add(last[u]);
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i],i+1);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.all_su);
    }
    return 0;
}

尾节点记录可重复子串在总串中出现次数

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[10010][60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    int ch[maxn][sigma_size];
    int f[maxn],last[maxn];
    int cnt[maxn],val[maxn];
    int siz;

    int ans;

    void init(){
        siz=ans=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=++siz;
            u=ch[u][c];
       }
       ///表示以第u棵节点为字符串最后一个字符节点的个数
       ///如果想存储该节点代表的是哪个字符串.即存储该字符串的下标
       ///val[u]=v;(v是下标)
       ///但是这样存储就会出现无法统计之前有多少个重复字符串
       ///比如这道题如果输入
       ///3
       ///sha
       ///sha
       ///sha
       ///shashasha
       ///则用第一种方法最后结果是3
       ///但用第二种方法只能匹配一次sha
       val[u]++;
    }
    //Fail树
    void getFail(){
        queue<int> Q;
        f[0]=0;
        ///遍历取出第一个节点所有的前向字符
        for(int c=0;c<sigma_size;++c){
            int u=ch[0][c];
            if(u){
                f[u]=last[u]=0;
                Q.push(u);
            }
        }
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                int u=ch[k][c];
                if(!u) continue;
                Q.push(u);
                int v=f[k];
                while(v && !ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

    ///统计
    void add(int u){
        if(u){
            if(!cnt[u]) ans+=val[u],cnt[u]=1;
            add(last[u]);
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            if(val[u]) add(u);
            else if(last[u]) add(last[u]);
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i]);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.ans);
    }
    return 0;
}

失配函数优化

接下来都基于第一个代码进行优化,可以复刻到第二个代码上

即将失配记录转变成 一条确定的边连到Trie中(这样应该就不能被称之为树了)

if(!u) continue; =>

if(!u) {ch[k][c]=ch[f[k]][c];continue;}
删掉适配函数BFS中的 while()

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[10010][60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    ///Trie树
    int ch[maxn][sigma_size];
    ///后缀相关数组
    int f[maxn],last[maxn];
    ///个数信息,尾节点记录信息
    int cnt[maxn],val[maxn];
    ///总节点个数
    int siz;

    int all_su;///记录总共有多少不可重复子串

    void init(){
        siz=all_su=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s,int v){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=++siz;
            u=ch[u][c];
       }
       ///尾节点记录字符串在str数组的下标
       val[u]=v;
    }

    //Fail树
    void getFail(){
        queue<int> Q;
        f[0]=0;
        ///遍历取出第一个节点所有的前向字符
        for(int c=0;c<sigma_size;++c){
            int u=ch[0][c];
            if(u){
                f[u]=last[u]=0;
                Q.push(u);
            }
        }
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                int u=ch[k][c];
                if(!u) {ch[k][c]=ch[f[k]][c];continue;}
                Q.push(u);
                int v=f[k];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

    ///统计
    void add(int u){
        for(;u;u=last[u]){
            if(!cnt[val[u]]) all_su++;
            printf("\n%s\n",str[val[u]-1]);
            cnt[val[u]]++;
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            if(val[u]) add(u);
            else if(last[u]) add(last[u]);
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i],i+1);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.all_su);
    }
    return 0;
}

MLE和TLE优化–内存优化

听说之前网络赛的时候就有道AC自动机的题,然后普通的模板总是MLE.
少了一半的时间,一半的内存

意在每次不全初始化,每多一个节点初始化一次

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    ///Trie树
    int ch[maxn][sigma_size];
    ///后缀相关数组fail,last
    int f[maxn];
    ///个数信息,尾节点记录信息
    int cnt[maxn],val[maxn];
    ///总节点个数,根节点编号
    int siz,root;

    int ans;

    int newNode(){
        memset(ch[siz],0,sizeof(ch[siz]));
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        ans=0;siz=0;root=newNode();
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]++;
    }

    //Fail树,build
    void getFail(){
        queue<int> Q;
        Q.push(root);

        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            u=ch[u][c];
            int p=u;
            while(p && val[p]){
                ans+=val[p];
                val[p]=0;
                p=f[p];
            }
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str);
            aho.insert(str);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.ans);
    }
    return 0;
}

但是以上自动机识别形如a,ab,abc,abcd这类子串会出问题,在刷题时发现的,下面重新用新的方法来解决这个问题,建议用下面的AC自动机

HDU 2222,上面的那些题,修改

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000000+6;

int T,N,tot_len;
char str[maxn],len[maxn];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cle[maxn],val[maxn];

    int siz,root,ans;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        for(int i=0;i<maxn;++i) val[i]=0;
        ans=0;
        siz=0;root=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]++;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void add(int u,int i){
        while(u){
            if(val[u]){
                int t=len[val[u]];
                for(int r=0;r<t;++r){
                    cle[i-r]=1;
                }
                return;
            }
            u=f[u];
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<tot_len;++i) cle[i]=0;
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            int p=u;
            while(p && val[p]){
                ans+=val[p];
                val[p]=0;
                p=f[p];
            }
        }
    }

}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str);
            aho.insert(str);
            len[i+1]=strlen(str);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        gets(str);
        tot_len=strlen(str);
        aho.Find(str);
        printf("%d\n",aho.ans);
    }
    return 0;
}

HDU 5880,青岛区域赛网赛

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000000+6;

int T,N,tot_len;
char str[maxn],len[maxn];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cle[maxn],val[maxn];

    int siz,root;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        for(int i=0;i<maxn;++i) val[i]=0;

        siz=0;root=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s,int v){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]=v;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void add(int u,int i){
        while(u){
            if(val[u]){
                int t=len[val[u]];
                for(int r=0;r<t;++r){
                    cle[i-r]=1;
                }
                return;
            }
            u=f[u];
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<tot_len;++i) cle[i]=0;
        for(int i=0;i<n;++i){
            if(!isalpha(s[i])){
                u=0;
                continue;
            }
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            /*
            int p=u;
            //cout<<i<<"  "<<u<<": "<<c<<endl;
            ///while是用来判断子串的.这道题不需要加
            while(p && val[p]){
                p=f[p];
            }
            */
            add(u,i);
        }
    }

    void print(){
        for(int i=0;i<tot_len;++i){
            if(cle[i]) putchar('*');
            else putchar(str[i]);
        }
        printf("\n");
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str);
            aho.insert(str,i+1);
            len[i+1]=strlen(str);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        //scanf("%[^\n]",str);
        gets(str);
        tot_len=strlen(str);
        //cout<<tot_len<<endl;
        aho.Find(str);
        aho.print();
    }
    return 0;
}

后缀数组

后缀自动机

山东省第八届ACM省赛 fireworks

迟来的祝福,新年快乐.

Link

要登录

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3895.html

Type: 杨辉三角<-组合数学,逆元

题意

假设x位置有一个烟花,则每秒烟花都会分裂到x+1与x-1这两个位置.

给你n个烟花的初始位置xi和个数ci,问你T秒后,位置w上的烟花个数有多少个.

题解

画一下样例的图会发现很像杨辉三角,我们可以将每个初始点分开计算,最后的结果就是所有初始点分裂后落在目标点的烟花个数和.
但我们发现它们的初始值大小与杨辉三角不同,并且比杨辉三角多了许多0, 然后我们考虑如何解决这两个情况.

(1) 初始值ci,因为只有一个初始点,这点和杨辉三角一样.所以答案是

ans(原杨辉三角在该位置的结果)*ci

(2) 中间有0,这点好想,我们只需要通过推导公式将实际坐标转换为逻辑坐标即可.

然后我们分情况讨论,我们在图上可以发现

(1) 当 分裂次数目标位置和原位置的距离差 同奇偶时该位置结果为0.
(2) 当距离大于T+1时(即杨辉三角第T行值的个数),永远不可能分裂到.

因为只需要考虑最后一次分裂的结果,所以只需要计算杨辉三角第T行即可,即 C(T,0~T)
预处理组合公式我们用 组合数学 性质4那个公式.
所以我们需要预处理一下1~1e5的逆元,将除法转换为乘法.
最后答案就是

ans=Sigma(i=1~n,c*C[实际位置] | 根据情况忽略i)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int maxn = 1e5+7;

LL C[maxn];
///逆元
LL inv[maxn];
void init_(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(MOD-MOD/i)*1ll*inv[MOD%i]%MOD;
    }
}

///快速幂模求逆元,调动方式quick_mod(i,MOD-2)
//这里我们用预处理.
LL quick_mod(LL x, int n){
    LL ret = 1;
    while(n){
        if(n & 1) ret = ret * x % MOD;
        x = x * x %MOD;
        n >>= 1;
    }
    return ret;
}

void init(int t){
    C[0]=1;
    for(int i=1;i<=t;++i){
        C[i]=C[i-1]*(t-i+1)*1ll%MOD*inv[i]%MOD;
        //printf("Num: %d %lld, INV: %lld\n",i,C[i],inv[i]);
    }
}
//判断是否同奇同偶
bool same(int x,int y){
    if((x&1)^(y&1)) return false;
    return true;
}

int query(int t,int d){
    if(t&1){
        return t/2-d/2;
    }
    return t/2+(d-1)/2;
}

int main(){
    init_();
    int n,T,w;
    while(~scanf("%d%d%d",&n,&T,&w)){
        init(T);
        LL ans=0;
        for(int i=1;i<=n;++i){
            int x,c;
            scanf("%d%d",&x,&c);
            int dist=abs(x-w);
            if(!same(T+1,dist) && dist<T+1){
                ans=(ans+c*C[query(T+1,dist)]%MOD)%MOD;
            }
        }
        printf("%lld\n",ans);
    }

    return 0;
}