首页 > 代码库 > 曦皓的幸运数

曦皓的幸运数

【题目描述】

仅包含4或7的数被称为幸运数。

一个序列的子序列被定义为从序列中删去若干个数,剩下的数组成的新序列。两个子序列被定义为不同的当且仅当其中的元素在原始序列中的下标的集合不相等。对于一个长度为N的序列,共有2^N个不同的子序列(包含一个空序列)。

一个子序列被称为不幸运的,当且仅当其中不包含两个相同的幸运数。

对于一个给定序列,求其中长度恰好为K的不幸运子序列的个数,答案 mod (10^9+7)输出。

【输入描述】

第一行两个正整数N、K,表示原始序列的长度和题目中的K;

接下来一行N个整数ai,表示序列中第i个元素的值。

【输出描述】

输出一个数,表示不幸运子序列的个数 mod (10^9+7)。

【样例输入】

样例1:

3 2

1 1 1

 

样例2:

4 2

4 7 4 7

【样例输出】

样例1:

3

 

样例2:

4

【数据范围及提示】

对于样例1,每个长度为2的子序列都是符合条件的。

对于样例2,4个不幸运子序列元素下标分别为:{1,2}、{3,4}、{1,4}、{2,3}。注意下标集{1,3}对应的子序列不是“不幸运”的,因为它包含两个相同的幸运数4。

技术分享

曦皓的幸运数