poj1625 Censored! 고정밀+ac기+dp

Language: Default
Censored!
Time Limit: 5000MS

Memory Limit: 10000K
Total Submissions: 7712

Accepted: 2095
Description
The alphabet of Freeland consists of exactly N letters. Each sentence of Freeland language (also known as Freish) consists of exactly M letters without word breaks. So, there exist exactly N^M different Freish sentences.
But after recent election of Mr. Grass Jr. as Freeland president some words offending him were declared unprintable and all sentences containing at least one of them were forbidden. The sentence S contains a word W if W is a substring of S i.e. exists such k >= 1 that S[k] = W[1], S[k+1] = W[2], ...,S[k+len(W)-1] = W[len(W)], where k+len(W)-1 <= M and len(W) denotes length of W. Everyone who uses a forbidden sentence is to be put to jail for 10 years.
Find out how many different sentences can be used now by freelanders without risk to be put to jail for using it.
Input
The first line of the input file contains three integer numbers: N -- the number of letters in Freish alphabet, M -- the length of all Freish sentences and P -- the number of forbidden words (1 <= N <= 50, 1 <= M <= 50, 0 <= P <= 10).
The second line contains exactly N different characters -- the letters of the Freish alphabet (all with ASCII code greater than 32).
The following P lines contain forbidden words, each not longer than min(M, 10) characters, all containing only letters of Freish alphabet.
Output
Output the only integer number -- the number of different sentences freelanders can safely use.
Sample Input

2 3 1
ab
bb

Sample Output

Source
Northeastern Europe 2001, Northern Subregion
제목: n개의 서로 다른 문자와 p개의 불법 문자열을 정하고 m의 길이가 불법 문자열을 포함하지 않는 서열 개수를 구합니다.
사고방식: 불법 직렬로 ac기를 구축하고 dp[i][j]를 길이로 i로 설정하여 ac기의 j노드 위치에 도달하는 합법적인 방안수.
j->next[k]->id=next를 설정하면 상태 이동 방정식 dp[i+1][next]+=dp[i][j]를 설정하여 j,next 노드의 위치가 모두 합법적임을 보증합니다.두 가지 주의 사항이 있습니다.
(1) 공백이 생길 수 있으므로 gets로 문자열을 읽어야 합니다.
(2) 제목에 모범이 없으면 답안은 높은 정밀도가 필요하다.
상세 코드:

#include
#include
#include
#include
using namespace std;
const int MAXN=10000+10;
const int N=100;
const int sigma_size=128;
int n,m,p,head,tail,sz;
char s[MAXN];
mapQ;
struct BigInt
{
    const static int mod=10000;
    const static int Dlen=4;
    int a[150],len;
    BigInt()
    {
        memset(a,0,sizeof(a));
        len=1;
    }
    BigInt(int x)
    {
        memset(a,0,sizeof(a));
        len=0;
        do
        {
            a[len++]=x%mod;
            x/=mod;
        }while(x);
    }
    BigInt(const char *str)
    {
        memset(a,0,sizeof(a));
        int l=strlen(str),index=0;
        len=(l+Dlen-1)/Dlen;
        for(int i=l-1;i>=0;i-=Dlen)
        {
            int x=0;
            int k=i-Dlen+1;
            if(k<0) k=0;
            for(int j=k;j<=i;j++)
                x=x*10+(str[j]-'0');
            a[index++]=x;
        }
    }
    BigInt operator +(const BigInt &rhs) const
    {
        BigInt res;
        res.len=max(len,rhs.len);
        for(int i=0;i0)
            res.len++;
        return res;
    }
    BigInt operator*(const BigInt &rhs) const
    {
        BigInt res;
        for(int i=0;i=0) res.len--;
        return res;
    } 
    void output()
    {
        printf("%d",a[len-1]);
        for(int i=len-2;i>=0;i--)
            printf("%04d",a[i]);
        printf("
");
    }
}dp[N][N];
struct node
{
    int cnt,id;
    node *next[sigma_size],*fail;
}trie[MAXN],*root,*que[MAXN];
struct AC
{
    node *createnode()
    {
        for(int k=0;knext[k]==NULL)
                p->next[k]=createnode();
            p=p->next[k];
        }
        p->cnt=1;
    }
    void get_fail()
    {
        que[tail++]=root;
        while(headnext[k])
                {
                    if(p==root)
                        p->next[k]->fail=root;
                    else
                        p->next[k]->fail=p->fail->next[k];
                    if(p->next[k]->fail->cnt)
                        p->next[k]->cnt=1;
                    que[tail++]=p->next[k];
                }
                else
                {
                    if(p==root)
                        p->next[k]=root;
                    else
                        p->next[k]=p->fail->next[k];
                }
        }
    }
    void query(int m)
    {
        for(int i=0;i<=m;i++)
            for(int j=0;jid;
                    if(trie[p].cnt)
                        continue;
                    dp[i+1][p]=dp[i+1][p]+dp[i][j];
                }
            }
        BigInt ans=BigInt(0);
        for(int i=0;i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

51Nod-1057-N의 등급

N을 입력하여 N의 계승에 대한 정확한 값을 구하십시오.Input 입력 N(1 <= N <= 10000)Output 출력 N의 곱하기 Input 예시 5 Output 예시 120 이 문제를 만난 것도 나의 운이다. ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

poj1625 Censored! 고정밀+ac기+dp

좋은 웹페이지 즐겨찾기