TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1725
  • 题目
  • P1725数字
    限制 : 时间限制 : 20000 MS   空间限制 : 128000 KB
    问题描述

    给出一个整数n和一个数组a。数组a中包含十个整数,编号0到9。
    你的任务是统计满足下列条件的正整数的个数:
    1.该正整数的长度不能超过n位;
    2.该正整数的最高位不能是0;
    3.数字i(0<=i<=9)在该正整数中至少出现a[i]次。

    输入格式

    第一行一个整数n(1<=n<=100)。
    第二行,10个空格间隔的整数,表示a[0],a[1]...a[9]里面存的数字

    输出格式

    一行,一个整数,表示满足条件的数字的个数,结果可能很大,输出与1000000007取模后的结果。

    样例输入

    样例输入1:
    1
    0 0 0 0 0 0 0 0 0 1
    样例输入2:
    2
    1 1 0 0 0 0 0 0 0 0
    样例输入3:
    3
    1 1 0 0 0 0 0 0 0 0

    样例输出

    样例输入1:
    1
    样例输入2:
    1
    样例输入3:
    36

    提示

    样例说明:
    满足样例1的数字只有数字"9"
    满足样例2的数字只有数字"10"

    满足样例3的数字有"10,110,101,100,102,103,120,210,301,......"总共36个,这些数字都满足0出现了至少1次,1出现了至少1次,其他数字出现了至少0次,并且长度不超过3。

    注:此题可能会用到排列组合的知识!

    组合公式:Cnk=n!/((n-k)!*k!)=Cn-1k+Cn-1k-1
    排列公式:Ank=n!/(n-k)!=k!*Cnk
    Cn0=An0=1


    来源  源自codeforce