hdoj 2243 대학원 진학 길이 막막 하 다 -- 단어 콤플렉스 [AC 자동 동기 + 구조 매트릭스]
Problem Description
단 어 를 외 우 는 것 은 시종 영 어 를 복습 하 는 중요 한 부분 이다.3 년 간 대학 생활 을 등한시 한 뒤 릴 도 드디어 단 어 를 외우 기 시작 했다.
어느 날, 릴 은 어떤 단어 책 에서 어근 에 따라 단 어 를 외 우 는 방법 을 보 았 다.예 를 들 어 'ab' 는 단어 앞 에 놓 으 면 '반대로 나 빠 지고 떠 나' 등 을 나타 낸다.
그래서 릴 은 N 개의 어근 을 외 웠 다 면 이 어근 들 이 단어 에 나 오지 않 았 을 까 하 는 생각 이 들 었 다.더 정확 한 설명 은 길이 가 L 을 초과 하지 않 고 소문 자로 만 구성 되 어 있 으 며 적어도 하나의 어근 을 포함 하 는 단 어 는 모두 몇 개 일 수 있 습 니까?여기 서 는 단어 가 실제 적 인 의미 가 있 는 지 없 는 지 를 고려 하지 않 는 다.
예 를 들 어 모두 2 개의 어근 aa 와 ab 가 있 으 면 104 개의 길이 가 3 을 초과 하지 않 는 단어 가 존재 할 수 있 습 니 다. 각각
(2 개) aa, ab,
(26 개) aaa, aab, aac... aaz,
(26 개) aba, abb, abc... abz,
(25 개) baa, caa, daa... zaa,
(25 개) bab, cab, dab... zab.
이것 은 아주 작은 상황 일 뿐이다.다른 복잡 한 상황 에 대해 서 는 릴 이 셀 수 없 으 니 지금 도와 주세요.
Input
이 문 제 는 여러 그룹의 데 이 터 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.
각 조 의 데이터 가 두 줄 을 차지한다.
첫 줄 에는 두 개의 정수 N 과 L 이 있다.(0
Output
각 그룹의 데이터 에 대해 서 는 한 줄 에 가능 한 단어 수 를 출력 하 십시오.
결과 가 매우 클 수 있 기 때문에 단어 총수 모드 2 ^ 64 의 값 만 출력 해 야 합 니 다.
Sample Input
2 3
aa ab
1 2
a
Sample Output
104
52
사고: 우 리 는 모든 방안 수 ans = 26 ^ 1 + 26 ^ 2 + 26 ^ 3 + 26 ^ 4 +... + 26 ^ L 을 구 합 니 다.그리고 패턴 문자열 이 없 는 프로젝트 수 temp = sum (1) + sum (2) + sum (3) +... + sum (L) 을 구 합 니 다.그 중에서 sum (i) 은 길이 가 i 인 문자열 에 패턴 문자열 이 없 는 방안 수 를 나타 낸다.
ans = 26 ^ 1 + 26 ^ 2 + 26 ^ 3 +... + 26 ^ L.
령 F [L] = 26 ^ 0 + 26 ^ 1 +... 26 ^ L, 공식 F [L] = 26 * F [L - 1] + 1 을 얻 을 수 있 습 니 다.
이렇게 하면 2 차원 행렬 을 구성 하여 행렬 의 빠 른 속도 로 ans = F [L] - 1 을 구 할 수 있다.
temp = sum (1) +... + sum (L).우선 trie 트 리 의 상태 전 이 를 구축 하여 초기 행렬 ori. a 를 얻 습 니 다.
sum (L) = res. a [0] [0] +... res. a [0] [Node - 1] 을 알 고 있 습 니 다. 그 중에서 res. a 는 ori. a 의 L 차 멱 이 고 Node 는 trie 노드 수 입 니 다.
이렇게 하면 행렬 의 성질 을 이용 하여 행렬 ori. a 를 바탕 으로 한 줄 한 열 을 추가 하고 Node 열 을 모두 1 로 만 들 수 있다.
oria 의 L 차 멱 res. a 를 구하 고 마지막 으로 res. a [0] [0] +... + res. a [0] [Node] - 1 이 우리 가 요구 하 는 temp 입 니 다.
이 문 제 는 unsigned long long 저장 소 2 ^ 64 를 사용 해 야 합 니 다.
AC 코드:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 50
#define LL unsigned long long
using namespace std;
struct Matrix{
LL a[MAXN][MAXN];
LL N;
};
Matrix ori, res;
Matrix multi(Matrix x, Matrix y)
{
Matrix z;
memset(z.a, 0, sizeof(z.a));
z.N = x.N;
for(int i = 0; i < x.N; i++)
{
for(int k = 0; k < y.N; k++)
{
if(x.a[i][k] == 0) continue;
for(int j = 0; j < x.N; j++)
z.a[i][j] += x.a[i][k] * y.a[k][j];
}
}
return z;
}
Matrix M_op(LL n)
{
while(n)
{
if(n & 1)
res = multi(ori, res);
ori = multi(ori, ori);
n >>= 1;
}
}
LL sum(LL n)
{
memset(ori.a, 0, sizeof(ori.a));
memset(res.a, 0, sizeof(res.a));
ori.N = res.N = 2;
for(int i = 0; i < 2; i++)
res.a[i][i] = 1;
ori.a[0][0] = ori.a[0][1] = 1;// ， bug
ori.a[1][1] = 26;
if(n == 1)
return 27;
M_op(n-1);
return 27 * res.a[1][1] + res.a[0][1];
}
struct Trie
{
int next[MAXN][30], fail[MAXN], End[MAXN];
int L, root;
int newnode()
{
for(int i = 0; i < 26; i++)
next[L][i] = -1;
End[L++] = 0;
return L-1;
}
void init()
{
L = 0;
root = newnode();
}
void Insert(char *s)
{
int len = strlen(s);
int now = root;
for(int i = 0; i < len; i++)
{
if(next[now][s[i]-'a'] == -1)
next[now][s[i]-'a'] = newnode();
now = next[now][s[i]-'a'];
}
End[now] = 1;
}
void Build()
{
queue<int> Q;
fail[root] = root;
for(int i = 0; i < 26; i++)
{
if(next[root][i] == -1)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
if(End[fail[now]])//
End[now] = 1;//
for(int i = 0; i < 26; i++)
{
if(next[now][i] == -1)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
void getMatrix()
{
for(int i = 0; i < L; i++)
if(End[i] == 0)
for(int j = 0; j < 26; j++)
if(End[next[i][j]] == 0)
ori.a[i][next[i][j]]++;
for(int i = 0; i < L+1; i++)
ori.a[i][L] = 1;
}
};
Trie ac;
void init_M(int NN)
{
memset(ori.a, 0, sizeof(ori.a));
memset(res.a, 0, sizeof(res.a));
ori.N = res.N = NN;
for(int i = 0; i < NN; i++)
res.a[i][i] = 1;
}
LL solve(LL n)
{
M_op(n);
LL ans = 0;
for(int i = 0; i < res.N; i++)
ans += res.a[0][i];
return ans;
}
char str[100];
int main()
{
int N;
LL L;
while(scanf("%d%llu", &N, &L) != EOF)
{
LL ans = sum(L) - 1;//
ac.init();
for(int i = 0; i < N; i++)
scanf("%s", str), ac.Insert(str);
ac.Build();
init_M(ac.L+1); ac.getMatrix();
LL temp = solve(L) - 1;//
printf("%llu
", ans - temp);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
