【题意】：给出n个数，问从这n个数中选k个数一共有多少种方案，其中不能包括两个相同的lucky number(lucky number指数位仅包含4和7的数字),1<=k<=n<=100000.

【题解】：先把lucky number离散化，然后对lucky number进行dp。
               设dp[i][j]表示前 i 种lucky number选了 j 种的方案数。
                     dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * c[i],其中c[i]表示第 i 种lucky number的个数。
               然后ans = ∑C(cnt, i) * dp[luckycnt][k-i], cnt 为非lucky number数目，luckycnt 为lucky number 种类数。
               注意，组合数需要用逆元处理。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 using namespace std;
12 #define pb push_back
13 #define lc(x) (x << 1)
14 #define rc(x) (x << 1 | 1)
15 #define lowbit(x) (x & (-x))
16 #define ll long long
17 #define maxn 100050
18 const ll MOD = 1000000007LL;
19 map<int, int> mp;
20 int n, k;
21 int luckycnt, cnt;
22 ll dp[1500], c[1500], p[maxn];
23 
24 void init() {
25     memset(c, 0, sizeof(c));
26     luckycnt = cnt = 0;
27     mp.clear();
28 }
29 
30 bool check(int x) {
31     while(x) {
32         if(x % 10 != 4 && x % 10 != 7) return false;
33         x /= 10;
34     }
35     return true;
36 }
37 
38 void Gcd(ll a, ll b, ll &d, ll &x, ll &y) {
39     if (!b) {
40         d = a, x = 1, y = 0;
41         return;
42     }
43     Gcd(b, a % b, d, y, x);
44     y -= x * (a / b);
45 }
46 
47 ll inv(ll a, ll n) {
48     ll d, x, y;
49     Gcd(a, n, d, x, y);
50     if (d == 1) return (x % n + n) % n;
51     else return -1;
52 }
53 
54 ll C(ll n, ll m) {
55     if(m == 0) return 1;
56     if(m > n) return 0;
57     ll res = (p[n] * inv(p[m], MOD)) % MOD;
58     res = (res * inv(p[n-m], MOD)) % MOD;
59     return res;
60 }
61 
62 void solve() {
63     memset(dp, 0, sizeof(dp));
64     dp[0] = 1;
65     for(int i = 1; i <= luckycnt; i++)
66         for(int j = i; j; j--)
67             dp[j] = (dp[j] + dp[j-1] * c[i]) % MOD;
68     ll ans = 0;
69     for(int i = 0; i <= k && i <= cnt; i++) {
70         if(k - i > luckycnt) continue;
71         ans = (ans + C(cnt, i) * dp[k-i]) % MOD;
72     }
73     cout << ans << endl;
74 }
75 
76 int main() {
77     p[0] = 1;
78     for(int i = 1; i < maxn; i++) p[i] = (p[i-1] * i) % MOD;
79     while(cin >> n >> k) {
80         init();
81         for(int i = 0, val; i < n; i++) {
82             cin >> val;
83             if(check(val)) {
84                 if(mp.find(val) == mp.end()) mp[val] = ++luckycnt;
85                 c[mp[val]]++;
86             } else cnt++;
87         }
88         solve();
89     }
90     return 0;
91 }
92