TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2842
  • 問題
  • P2842【SDOI2014 R1D1】数数
    制限 : 時間制限 : 10000 MS   メモリ制限 : 565536 KB
    問題説明

    我们称一个正整数N是幸运数,当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为子串。例如当S={22,333,0233}时,223是幸运数,2333、20233、3223都不是幸运数。
    给定N和S,计算不大于N的幸运数个数。

    入力形式

    第一行包含一个整数N
    接下来一行一个整数M,表示S中元素的数量
    接下来M行,每行一个数字串,表示S中的元素

    出力形式

    输出一行一个整数,表示答案模109+7的值。

    サンプル入力

    20
    3
    2
    3
    14

    サンプル出力

    14

    ヒント

    设l表示N的长度,L表示S中所有串的长度之和,则
    对于10%的数据,1<=l<=6,M=1,1<=L<=2
    对于20%的数据,1<=l<=8,1<=M<=3,1<=L<=12
    对于70%的数据,1<=l<=100,1<=M<=50,1<=L<=300
    对于100%的数据,1<=l<=1200,1<=M<=100,1<=L<=1500


    ソース  感谢nodgd放题