运(Lucky.*) DP

发布于 2017-08-04  4.65k 次阅读


[toggle hide="yes" title="题目" color=""]运(lucky.*)
【问题背景】
zhx 和妹子们玩数数游戏。
【问题描述】
仅包含4 或7 的数被称为幸运数。一个序列的子序列被定义为从序列中删去若
干个数, 剩下的数组成的新序列。两个子序列被定义为不同的当且仅当其中的元
20170804 考试
素在原始序列中的下标的集合不相等。对于一个长度为N 的序列,共有2^N 个不
同的子序列。( 包含一个空序列)。一个子序列被称为不幸运的, 当且仅当其中
不包含两个或两个以上相同的幸运数。对于一个给定序列, 求其中长度恰好为K
的不幸运子序列的个数, 答案mod 10^9+7 输出。
【输入格式】
第一行两个正整数N, K, 表示原始序列的长度和题目中的K。
接下来一行N 个整数ai, 表示序列中第i 个元素的值。
【输出格式】
仅一个数,表示不幸运子序列的个数。( mod 10^9+7)
【样例输入】
3 2
1 1 1
【样例输出】
3
【样例输入】
4 2
4 7 4 7
【样例输出】
4
【样例解释】
对于样例1,每个长度为2 的子序列都是符合条件的。
对于样例2,4 个不幸运子序列元素下标分别为:{1, 2}, {3, 4}, {1, 4}, {2, 3}。注意
下标集{1, 3}对应的子序列不是“不幸运”的, 因为它包含两个相同的幸运数4.
【数据规模与约定】
对于50%的数据, 1 ≤N ≤ 16。
对于70%的数据, 1 ≤ N ≤ 1000, ai ≤ 10000。
对于100%的数据, 1 ≤ N ≤ 100000,K ≤ N, 1 ≤ ai ≤ 109。[/toggle]

前50分可以压位暴力,不过想再多得分就要换种思路了。

首先,可以将数列中所有幸运的数进行分组并计数,那么在一个不幸运的子序列中,同样的幸运数最多出现1次。先统计选幸运数的方案数:设f[i][j]表示前i种幸运数,选出j个数的方案总数;cnt[i]表示第i种幸运数的数量。易得:$$f[i][j]=f[i-1][j]+f[i-1][j-1]*cnt[i]$$

而非幸运数的方案数很显然,就是在n-幸运数个数中选出k-已选幸运数个数即可,求和即为答案。

设tot=幸运数个数,d=幸运数种数,则

$$\sum_{i=1}^{min(tot,k)} C_{n-tot}^{k-i} * f[d][i]$$

f数组可以滚动起来。

[toggle hide="no" title="代码" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974