2015年4月17日 星期五

2015/04/17 Codeforces 535D. Tavas and Malekas

// http://codeforces.com/problemset/problem/535/D
/*
    哈哈 我還是一樣廢
    選擇用Hash 來逃避其他字串處理 OAO"
*/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

#define p1 (ll)(509)
#define p2 (ll)(1e8+7)
#define MOD (ll)(1e9+7)

int Ans = 1;
int N, M;

char p[2000000]; int pn;
char s[2000000];
int H[2000000];
int y[2000000];

ll sh[2000000];

ll pwd(int x)
{
    if( x == 0 ) return 1;
    ll p = pwd(x/2);

    if( x&1 ) return p*p%MOD*26%MOD;
    else return p*p%MOD;
}

int ask(int l, int r)
{
    if( l == 0 ) return H[r];

    int re = (H[r]-H[l-1]*sh[r-l+1])%p2;
    re = (re+p2)%p2;

    return re;
}

int main()
{
    scanf("%d %d", &N, &M);

    scanf("%s", p);
    pn = strlen(p);

    int now = -1;
    sh[0] = 1;

    for(int Ni = 0; Ni < N; Ni++)
    {
        s[Ni] = ' ';
        if( Ni ) sh[Ni] = sh[Ni-1]*p1%p2;
    }

    for(int Mi = 0; Mi < M; Mi++)
    {
        scanf("%d", &y[Mi]);
        y[Mi]--;

        now = max(now, y[Mi]);
        while( now != y[Mi]+pn )
        {
            s[now] = p[now-y[Mi] ];
            now++;
        }
    }

    H[0] = s[0]-' ';

    for(int Ni = 1; Ni < N; Ni++)
        H[Ni] = (H[Ni-1]*p1+s[Ni]-' ')%p2;

    for(int Mi = 1; Mi < M; Mi++)
        if( ask(y[0], y[0]+pn-1) != ask(y[Mi], y[Mi]+pn-1) ) Ans = 0;

    int cnt = 0;

    for(int Ni = 0; Ni < N; Ni++)
        if( s[Ni] == ' ' ) cnt++;

    Ans = Ans*pwd(cnt)%MOD;

    printf("%d\n", Ans);
}

沒有留言:

張貼留言