NOIP 2014 8 교 연합 시험 3 차 1 차 시험 10.4] 히 비 라 시스템 계속 저항 (regex)

Description
비록 한 과 의 반항 행동 은 실 패 했 지만 그 행동 은 히 비 라 시스템 에 반항 하 는 관념 을 사람들의 마음속 에 깊이 파고 들 었 고 분석 관 인 당신 도 시스템 의 어 딘 가 에 구멍 을 찾 았 습 니 다. 기 회 는 여전히 존재 합 니 다. 당신 은 다음 반항 을 위해 준 비 를 해 야 합 니 다.전자기 펄스 파괴 시스템 을 직접 사용 하 는 것 은 지난번 에 불가능 하 다 는 것 이 증명 되 었 으 나, 지금 은 시스템 에 침투 하여 돌파 구 를 찾 으 려 고 시도 할 수 밖 에 없다.당신 은 이제 구멍 에서 중추 의 각 단원 의 뇌 간 통신 을 감청 하고 그 중에서 특정한 규칙 에 부합 되 는 일 부 를 선별 하여 더욱 깊이 분석 할 수 있 습 니 다.규칙 은 특수 한 정규 표현 식 으로 설명 할 수 있 습 니 다. 다음 과 같은 재 귀적 정의 가 있 습 니 다. 요소: = "[" + 문자 집합 + "] 은 문자 집합 과 일치 하 는 임의의 문 자 를 표시 합 니 다.문자 가 집 중 된 문 자 는 모두 소문 자 이다."+" 는 문자열 의 연결 을 표시 합 니 다.표현 식: = 요소 나 표현 식 + 표현 식 또는 "(" + 표현 식 + ")" + "+".연 결 된 표현 식 은 연속 문자 와 일치 합 니 다.'+' 는 앞의 괄호 안의 내용 이 한 번 또는 여러 번 나타 나 는 것 을 나타 낸다.예 를 들 어 표현 식 [a] [b] 이 ab 와 일치 합 니 다.표현 식 [ab] [c] 이 ac 또는 bc 와 일치 합 니 다.표현 식 ([a] [b]) + ([c]) + "abc", "ababc", "ababccc" 등 문자열 과 일치 할 수 있 습 니 다.당신 의 동 료 는 대형 컴퓨터 를 사용 하여 요구 에 부합 되 는 모든 긴 문자열 (통신) 을 끝까지 들 고 그 성질 을 분석 하기 로 결 정 했 습 니 다.당신 은 이런 방법 에 대해 회의 적 인 태 도 를 가지 고 있 습 니 다. 비교적 긴 연산 시간 과 중추 보다 더 많은 전력 소비량 은 반드시 체계 적 인 의심 을 불 러 일 으 킬 것 입 니 다.요 구 를 만족 시 키 는 문자열 이 얼마나 있 는 지 계산 하 는 데 걸 리 는 시간 을 계산 해 야 합 니 다. 정규 표현 식 을 분석 하 는 것 이 분석 관 으로서 필요 한 기능 이 라 고 믿 습 니 다.
Solution
이 문 제 는 길 고 번 거 로 워 서 보면 풀 고 싶 지 않다.하지만 문 제 를 풀 어 보 니 기지 가 넘 쳤 다.방법 은 자동 기 를 만 드 는 것 이다.먼저 '[]' 입 니 다. 이것 은 하나의 요소 입 니 다. 두 개의 점 을 열 고 하나의 s 와 하나의 t 를 연 다음 에 앞의 요소 의 t 는 뒤의 요소 의 s (무색 의 변 을 연결 합 니 다) 를 연결 한 다음 에 s 는 t 에 여러 개의 괄호 안의 색 의 변 을 연결 합 니 다.그러면 '()' 에 대해 마지막 색 의 t 를 맨 앞 에 있 는 요소 의 s 로 연결 하면 순환 을 실현 할 수 있 습 니 다.그리고 f [i] [j] 를 설정 하여 i 번 째 문 자 를 만 들 고 j 번 째 그룹 (자신의 요소 가 밖으로 연결 되 지 않 음) 으로 가면 a [i] [j] 를 처리 할 수 있 습 니 다.그럼 그냥 행렬 곱셈 으로 최적화 하면 돼.
Code

#include
#include
#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef unsigned int ui;
typedef long long ll;
const int maxn=1007;
int i,j,k,l,t,n,num,r,tot;
int a[11][11][27],c[10000],er[21],b[maxn*10];
ui ans,f[maxn][maxn],x[maxn][maxn],p[maxn][maxn],q[maxn][maxn],z[maxn][maxn];
ll mo;
int m;
char s[maxn];
void qsm(int xx)
{
    int i,j,k;
    if(xx==1)return;
    qsm(xx/2);
    fo(i,1,tot)fo(j,1,tot){
        z[i][j]=0;
        fo(k,1,tot)z[i][j]+=x[i][k]*x[k][j];
    }
    fo(i,1,tot)fo(j,1,tot)x[i][j]=z[i][j];
    if(xx%2){
        fo(i,1,tot)fo(j,1,tot){
            z[i][j]=0;
            fo(k,1,tot)z[i][j]+=x[i][k]*p[k][j];
        }
        fo(i,1,tot)fo(j,1,tot)x[i][j]=z[i][j];
    }
}
void dfs(int x,int &y){
    int i;
    y|=er[x-1];
    fo(i,1,num)if(a[x][i][26])dfs(i,y);
}
int main(){
//  freopen("fan.in","r",stdin);
    er[0]=1;fo(i,1,20)er[i]=er[i-1]*2;
    mo=4294967296;
    scanf("%s",s+1);n=strlen(s+1);
    scanf("%d",&m);
    fo(i,1,n){
        if(s[i]=='['){
            if(num)a[num][num+1][26]=1;
            fo(j,i+1,n){

                if(s[j]==']'){c[j]=num/2+1;break;}
                a[num+1][num+2][s[j]-'a']=1;
            }
            num+=2;
        }
    }
    fo(i,1,n){
        if(s[i]!='+')continue;
        r=-1;l=100;k=0;
        fod(j,i-1,1){
            if(c[j])l=min(l,c[j]),r=max(r,c[j]);
            if(s[j]=='(')k++;if(s[j]==')')k--;
            if(!k)break;
        }
        a[2*r][2*l-1][26]=1;
    }
    fo(i,1,num)dfs(i,b[i]);
    memset(c,0,sizeof(c));
    fo(i,0,er[num]-1){
        k=0;
        fo(j,1,num)if(er[j-1]&i)k|=b[j];
        if(i==k)c[i]=++tot;
    }
    fo(i,0,25){
        fo(j,0,er[num]-1){
            if(!c[j])continue;t=0;
            fo(k,1,num){
                if(!(er[k-1]&j))continue;
                fo(l,1,num){
                    if(a[k][l][i])t|=b[l];
                }
            }
            f[c[j]][c[t]]++;
        }
    }
    fo(i,1,tot)fo(j,1,tot)x[i][j]=p[i][j]=f[i][j];
    qsm(m);
    fo(i,0,er[num]-1)if((i&er[num-1])&&c[i])ans=(ans+z[c[b[1]]][c[i]])%mo;
    printf("%lld
",ans);
}