题意：
规定只包含4或7的数为幸运数字，给定n个数的序列，求他的子序列，使得该子序列的长度为k并且满足该子序列中不存在相同的两个幸运数字。问一共寻在多少种可能。（只要该数的下标不同则认为是不同的序列）
思路：
记录每个幸运数字的个数，枚举从非幸运数中取出的个数i，那么在幸运数字中取k - i。这里C（no，i）好算，直接带公式算除法取模，而在幸运数字中取k-i个的可能需要同过dp来算，这里类似于01背包模型，dp[i +1][j + 1] = dp[i][j]*a[i] + dp[i][j + 1]; 表示前i个取了j个的可能数。
这里对dp进行了空间优化
View Code //#pragma comment(linker,"/STACK:327680000,327680000") #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <functional> #include <numeric> #include <sstream> #include <stack> #include <map> #include <queue>#define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1#define ll __int64 #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) (x) < 0 ? -(x) : (x) #define OUT(x) printf("%I64d\n", x) #define lowbit(x) (x)&(-x) #define Read() freopen("din.txt", "r", stdin) #define Write() freopen("dout.txt", "w", stdout);#define M 26 #define N 100007using namespace std;const int inf = 0x1F1F1F1F; const int mod = 1000000007; const int X = 1000000005;ll fac[N]; ll a[N]; ll dp[1230];set<int> iset; map<int,int> imap;void init() {int i;fac[0] = 1;for (i = 1; i < N; ++i){fac[i] = fac[i - 1]*i%mod;} } bool isL(int x) {while (x){if (x % 10 != 4 && x % 10 != 7) return false;x /= 10;}return true; } ll modexp(ll a,ll b,ll c) {ll rs = 1;ll tmp = a;while (b){if (b&1) rs = rs*tmp%c;tmp = tmp*tmp%c;b >>= 1;}return rs; } ll cal(int x,int y) {ll ans = 0;ans = fac[x]*modexp(fac[x - y],X,mod)%mod;ans = ans*modexp(fac[y],X,mod)%mod;return ans; } int main() { // Read();int n,m;int i,x,j;scanf("%d%d",&n,&m); init();iset.clear(); imap.clear();int no = 0;for (i = 0; i < n; ++i){scanf("%d",&x);if (isL(x)){iset.insert(x);imap[x]++;}else no++;}set<int>::iterator it;int la = 0;for (it = iset.begin(); it != iset.end(); ++it) a[++la] = imap[*it];for (i = 0; i <= la; ++i) dp[0] = 1;for (i = 0; i < la; ++i){for (j = i; j >= 0; --j){dp[j + 1] += dp[j]*a[i + 1];dp[j + 1] %= mod;}}ll ans = 0;for (i = 0; i <= m; ++i){if (no >= i && la >= m - i){ll tmp = cal(no,i)*dp[m - i]%mod;ans = (ans + tmp)%mod;}}cout<<ans<<endl;return 0; }
