Codeforces 145 C. Lucky Subsequence
問題
lucky numberとは、全ての桁が4または7のどちらかであるような数をいう。
n個の数が与えられる。
このn個の数の長さkの(必ずしも連続しない)部分列のうち、
同じlucky numberは高々一つしか含まれないようなものはいくつあるか、mod 19^9 + 7で求めよ。
ただし、同じ数列でも、元の列におけるインデックスが違った場合は違う数列と数えるものとする。
制約条件
n, k≦100000
それぞれの数≦10^9
方針
lucky numberはせいぜい2^10個しかない。
なので、lucky numberをi番目まででj個使うときの、場合の数は
動的計画法によりO(m^2)時間で求められる。(mはlucky numberの数)
後は、残りの数の選び方をコンビネーションで求めてかけてやればいい。
コンビネーションは毎回計算すると時間がかかるので、
階乗を覚えるなどして効率的に計算する。
ソースコード
const int mod = (int)1e9 + 7; int fact[100001], dp[100001]; inline int modpow(int n, int m){ int res = 1; for(; m; m >>= 1){ if(m & 1) res = (ll)res * n % mod; n = (ll)n * n % mod; } return res; } inline int C(int n, int k){ if(k < 0 || k > n) return 0; return (ll)fact[n] * modpow(fact[n - k], mod - 2) % mod * modpow(fact[k], mod - 2) % mod; } inline bool lucky(int n){ for(; n; n /= 10) if(n % 10 != 4 && n % 10 != 7) return 0; return 1; } void run() { fact[0] = 1; rep(i, 100000) fact[i+1] = fact[i] * (i+1ll) % mod; int n, k, unlucky = 0; cin >> n >> k; map<int, int> cnt; rep(i, n){ int a; cin >> a; if(lucky(a)) cnt[a]++; else unlucky++; } vi cs; fr(i, cnt) cs.pb(i->second); int m = cs.size(), ans = 0; dp[0] = 1; rep(i, m) for(int j = i; j >= 0; j--){ (dp[j + 1] += (ll)dp[j] * cs[i] % mod) %= mod; } rep(i, k+1) (ans += (ll)C(unlucky, k - i) * dp[i] % mod) %= mod; cout << ans << endl; }