ZOJ 3494 BCD 코드(AC 로봇 + 디지털 DP)
19399 단어 AC 로봇
Time Limit: 5 Seconds
Memory Limit: 65536 KB
Binary-coded decimal (BCD) is an encoding for decimal numbers in which each digit is represented by its own binary sequence. To encode a decimal number using the common BCD encoding, each decimal digit is stored in a 4-bit nibble:
Decimal: 0 1 2 3 4 5 6 7 8 9
BCD: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001
Thus, the BCD encoding for the number 127 would be:
0001 0010 0111
We are going to transfer all the integers from A to B, both inclusive, with BCD codes. But we find that some continuous bits, named forbidden code, may lead to errors. If the encoding of some integer contains these forbidden codes, the integer can not be transferred correctly. Now we need your help to calculate how many integers can be transferred correctly.
Input
There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.
The first line of each test case contains one integer N, the number of forbidden codes ( 0 ≤ N ≤ 100). Then N lines follow, each of which contains a 0-1 string whose length is no more than 20. The next line contains two positive integers A and B. Neither A or B contains leading zeros and 0 < A ≤ B < 10200.
Output
For each test case, output the number of integers between A and B whose codes do not contain any of the N forbidden codes in their BCD codes. For the result may be very large, you just need to output it mod 1000000009.
Sample Input
3
1
00
1 10
1
00
1 100
1
1111
1 100
Sample Output
3
9
98
References
Author: GUAN, YaoContest: The 8th Zhejiang Provincial Collegiate Programming Contest
아주 신기한 제목...
먼저 AC자동기를 사용하여 bcd[i][j]를 얻어 상태 i를 표시하고 숫자 j를 추가한 후 도착한 상태는 -1로 이동할 수 없음을 표시한다.
그다음에 디지털 DP.
0으로 기록된 상태 주의
//============================================================================
// Name : ZOJ.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Trie
{
int next[2010][2],fail[2010];
bool end[2010];
int root,L;
int newnode()
{
for(int i = 0;i < 2;i++)
next[L][i] = -1;
end[L++] = false;
return L-1;
}
void init()
{
L = 0;
root = newnode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = 0;i < len ;i++)
{
if(next[now][buf[i]-'0'] == -1)
next[now][buf[i]-'0'] = newnode();
now = next[now][buf[i]-'0'];
}
end[now] = true;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = 0;i < 2;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] = true;
for(int i = 0;i < 2;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]);
}
}
}
};
Trie ac;
int bcd[2010][10];
int change(int pre,int num)
{
if(ac.end[pre])return -1;
int cur = pre;
for(int i = 3;i >= 0;i--)
{
if(ac.end[ac.next[cur][(num>>i)&1]])return -1;
cur = ac.next[cur][(num>>i)&1];
}
return cur;
}
void pre_init()
{
for(int i = 0;i <ac.L;i++)
for(int j = 0;j <10;j++)
bcd[i][j] = change(i,j);
}
const int MOD = 1000000009;
long long dp[210][2010];
int bit[210];
long long dfs(int pos,int s,bool flag,bool z)
{
if(pos == -1)return 1;
if(!flag && dp[pos][s]!=-1)return dp[pos][s];
long long ans = 0;
if(z)
{
ans += dfs(pos-1,s,flag && bit[pos]==0,true);
ans %= MOD;
}
else
{
if(bcd[s][0]!=-1)ans += dfs(pos-1,bcd[s][0],flag && bit[pos]==0,false);
ans %= MOD;
}
int end = flag?bit[pos]:9;
for(int i = 1;i<=end;i++)
{
if(bcd[s][i]!=-1)
{
ans += dfs(pos-1,bcd[s][i],flag&&i==end,false);
ans %=MOD;
}
}
if(!flag && !z)dp[pos][s] = ans;
return ans;
}
long long calc(char s[])
{
int len = strlen(s);
for(int i = 0;i < len;i++)
bit[i] = s[len-1-i]-'0';
return dfs(len-1,0,1,1);
}
char str[210];
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;
scanf("%d",&T);
int n;
while(T--)
{
ac.init();
scanf("%d",&n);
for(int i = 0;i < n;i++)
{
scanf("%s",str);
ac.insert(str);
}
ac.build();
pre_init();
memset(dp,-1,sizeof(dp));
int ans = 0;
scanf("%s",str);
int len = strlen(str);
for(int i = len -1;i >=0;i--)
{
if(str[i]>'0')
{
str[i]--;
break;
}
else str[i] = '9';
}
ans -= calc(str);
ans %=MOD;
scanf("%s",str);
ans += calc(str);
ans %=MOD;
if(ans < 0)ans += MOD;
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU4758 Walk Through Squares AC 자동기 & &dp이 문제는 그때 할 때 수론제라고 생각했는데 01열 두 개가 포함돼 있었다. 경기 후에 문자열이라고 듣고 그럴 가능성이 높았다.어제 팀원들이 이 문제를 물었는데 AC자동기를 배운 후에 많이 간단해졌다고 느꼈다.그때는...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.