コード (practice で accepted)

2012-01-27

12:25 |

（LuXueQi さん、xhl_kogitsune さんのコードも参考にしました）

#define MOD 1000000007LL
#define MAXN 100003
int dp[1024][1024];
int b[MAXN];

int lucky(ll x) {
   for(;x>0;x/=10) if(x%10!=4 && x%10!=7) return 0;
   return 1;
}

ll modpow(ll v, int p) {
   if(p==1) return v;
   ll vv = modpow(v, p/2);
   vv = (vv * vv) % MOD;
   if(p&1) vv = (vv * v) % MOD;
   return vv;
}

ll comb(int n, int k) {
   ll c=1;
   for(int i=1;i<=k;i++) {
        c = (c * (n-i+1)) % MOD;
        c = (c * modpow(i, MOD-2)) % MOD;
   }
   return c;
}

int main() {
   int N,K;
   cin>>N>>K;
   memset(dp, 0, sizeof(dp));

   map<ll, int> hi;
   VI lu;
   int rest=0;
   REP(i, N) {
        int v;
        scanf("%d",&v);
        if(lucky(v)) {
             if(hi[v]==0) lu.PB(v);
             hi[v]++;
        }
        else rest++;
   }
   int nl=hi.size();

   dp[0][0] = 1;
   for(int y=1;y<=nl;y++) {
        dp[y][0] = 1;
        for(int x=1;x<=nl;x++) {
             dp[y][x] = ( dp[y-1][x] + ((ll)dp[y-1][x-1] * hi[lu[y-1]])%MOD ) % MOD;
        }
   }

   b[0]=1;
   for(int i=1;i<=rest;++i){
        b[i]=1LL*b[i-1]*(rest-i+1)%MOD*modpow(i, MOD-2)%MOD;
   }

   ll ans = 0;
   REP(i, nl+1) {
        int lrest = K-i;
        if(lrest < 0 || rest < lrest ) continue;
        ans += (ll)b[lrest] * dp[nl][i];
        ans = ans % MOD;
   }
   cout<<ans<<endl;

   return 0;
}