【East!_XX】手机号码

2015年4月18日9660

Description

众所周知,天朝泱泱五千年的文化积淀下,人们在数字上尤为挑剔。很多人认为,不吉利的数字会导致流年困顿。【阿弥陀佛,作为社会主义接班人,我们应该相信科学,远离迷信!】

在天朝,不同的人读手机号码有不同的方式(见右图)。人们选择手机号码时,为了照顾“不吉利数字恐惧症”患者,总会希望任何人报自己的电话号码时都不会连续说出来不吉利数字。

例如,很多天朝子民认为5914是一串很不吉利的号码,因此尾号为5914的手机号码理所当然地被众人所避忌。而号码188-8859-1488却不是一个不吉利号码,因为无论使用右图中的哪一种方式去读,5914均会被拆分开来。

现在,我们想知道的是,在天朝,有多少电话号码能被人们所接受。

* 常识:在中国,民用手机号段均以1开头。

Input

第一行输入一个正整数N,表示有N个不吉利的数字串。

接下来N行,每行一个5位以内的数字串,表示一个不吉利的号码。

Output

一个正整数,表示并非不吉利的号码总数。

Sample I/O

Sample Input

Sample Output

1

5914

9996000100

Hint

对于20% 的数据,N ≤ 2

对于100% 的数据,N ≤ 100

题解

出题人Eolv:

对右图所示四种读电话号码的方式进行总结,可得到信息:

符合题意的电话号码中第1~4位、第4~7位、第5~8位、第7~11位均不包含不吉利数字串。

令f[i,x]表示对于前i位号码,以数字串x结尾的方案数。显然,只需要依次求出f[4,0…9]、f[7,000…999]、f[8,00…99]、f[11,00000…99999]即可统计出答案。由于不吉利数字串的总数较少,转移时直接枚举所有的情况即可。也可以建立AC自动机对这一过程进行优化。