CodeChef FAVNUM FavouriteNumbers（AC自动机+数位dp+二分答案）

All submissions for this problem are available.

Chef likes numbers and number theory, we all know that. There are N digit strings that he particularly likes. He likes them so much that he defines some numbers to be beautiful numbers based on these digit strings.

Beautiful numbers are those numbers whose decimal representation contains at least one of chef's favorite digit strings as a substring. Your task is to calculate the K^th smallest number amongst the beautiful numbers in the range from L to R (both inclusive). If the number of beautiful numbers between L and R is less than K, then output "no such number".

Input

In the first line of input there will be integers L, R, K and N. Then N lines follow. Each line will contain a single string of decimal digits.

Output

Output one integer - the solution to the problem described above or a string "no such number" if there is no such number.

Constraints

1<=L<=R<=10^18
1<=K<=R-L+1
1<=N<=62
1<=The length of any Chef's favourite digit string<=18. Each string begins with a nonzero digit.

Example

Input:
1 1000000000 4 2
62
63

Output:
163

Input:
1 1 1 1
2

Output:
no such number

Input:
1 1000 15 2
6
22

Output:
67

Author:6★xcwgf666

Tester:6★laycurse

Editorial:http://discuss.codechef.com/problems/FAVNUM

Tags:aho-corasick, dynamic-programming, july12, medium, xcwgf666

Date Added:20-12-2011

Time Limit:0.1 - 0.146779 secs

Source Limit:50000 Bytes

Languages:C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS

题解：给你一些幸运数字，然后问你在一个区间内的第k大的，含有幸运数字的数是哪一个数字。

第K大，二分答案，然后考虑数位DP。如果是单个数字的话这样就可以了。多个数字，我们把它们放在AC自动机里面，然后dp[len][pos][flag]表示当前长度为len，走到AC自动机上pos点的时候取幸运数字状态为flag（是或否取到）的方案数。那么我们显然可以有转移方程：dp[len][pos][flag]=Σ dp[len-1][ch][flag || AC.T[ch].cnt]，其中ch为pos的某一个后继节点。意思是，如果到下一个节点能够组成一个幸运数字，那么flag的状态就要相应改变。之后，按照普通数位dp的套路那样，记忆化搜索转移即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 2400  
int n,tot;  
ll L,R,K;
char s[20];                                   
int ch[maxn][10],fail[maxn],val[maxn],last[maxn]; 

void Init()  
{  
    tot=1;
    memset(ch[0],0,sizeof(ch[0]));  
    memset(val,0,sizeof(val));  
}     
int idx(char c){ return c - '0';}  
void Insert(char*s)
{  
    int u=0,len=strlen(s);  
    for(int i=0;i<len;++i)  
    {  
        int c=idx(s[i]);  
        if(!ch[u][c])  
        {  
            memset(ch[tot],0,sizeof(ch[tot]));  
            val[tot]=0;  
            ch[u][c]=tot++;   
        }  
        u=ch[u][c];  
    }  
    val[u]=1;  
}
void GetFail()  
{  
    queue<int> q;  
    fail[0]=0;  
    for(int c=0;c<10;++c)  
    {  
        int u=ch[0][c];  
        if(u){ fail[u]=0;q.push(u);last[u]=0; }  
    }  
    while(!q.empty())  
    {  
        int r=q.front(); q.pop();  
        val[r]|=val[fail[r]];
        for(int c=0;c<10;++c)  
        {                                  
            int u=ch[r][c];  
            if(!u){ch[r][c]=ch[fail[r]][c];continue;}  
            q.push(u);  
            int v=fail[r];  
            fail[u]=ch[v][c];  
            last[u] = val[fail[u]]?fail[u]:last[fail[u]];  
        }  
    }  
}   
int dig[20];
ll dp[20][maxn][2];
ll dfs(int len,int pos,bool flag,int lim)
{    
    if(len<=0) return flag;
    if(!lim&&dp[len][pos][flag]>=0) return dp[len][pos][flag];
    ll res=0;
    int sz=lim?dig[len]:9;
    for(int i=0;i<=sz;++i)
    {
        int nxt=ch[pos][i];
        res+=dfs(len-1,nxt,val[nxt]||flag,lim&&i==sz);
    }
    if(!lim) dp[len][pos][flag]=res;
    return res;
}
ll work(ll x)
{
    int len=0;
    while(x)
    {
        dig[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1);
}

int main()
{
    scanf("%lld%lld%lld%d",&L,&R,&K,&n);
    Init();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s);
        Insert(s);    
    }
    GetFail();
    memset(dp,-1,sizeof dp);
    ll num=work(L-1),mid,ans=0;
    while(L<=R)
    {
        mid=L+R>>1;
        if(work(mid)-num>=K) R=mid-1,ans=mid;
        else L=mid+1;    
    }
    if(ans) printf("%lld
",ans);
    else puts("no such number");
    
    return 0;
}

View Code