题解

1 条题解

  • 0
    @ 2017-11-07 17:20:40
    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<map>
    #define M 100005
    #define P 1000000007
    using namespace std;
    map<int,int>mp;
    int fact[M],dp[2000][2000],A[M],C[M];
    bool check(int x){
        if(x==0)return false;
        while(x){
            int d=x%10;
            if(d!=4&&d!=7)return false;
            x/=10;
        }
        return true;
    }
    int fast(int a,int b){
        int res=1;
        while(b){
            if(b&1)res=1LL*res*a%P;
            b>>=1;
            a=1LL*a*a%P;
        }
        return res;
    }
    int Calc(int n,int m){
        if(n>m)return 0;
        return 1LL*fact[m]*fast(fact[m-n],P-2)%P*fast(fact[n],P-2)%P;
    }
    void Check(int &a,int b){
        a+=b;
        if(a>P)a%=P;
    }
    int main(){
    //  freopen("lucky.in","r",stdin);
    //  freopen("lucky.out","w",stdout);
        int n,k,tot=0,ans=0,d=0;
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%d",&A[i]);
            if(check(A[i]))mp[A[i]]++;
            else d++;
        }
        fact[0]=1;
        for(int i=1;i<=n;i++)
            fact[i]=1LL*fact[i-1]*i%P;
        for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
            C[++tot]=it->second;
        for(int i=0;i<=tot;i++)
            dp[i][0]=1;
        for(int i=1;i<=tot;i++)
            for(int j=1;j<=i;j++){
                Check(dp[i][j],dp[i-1][j]);
                Check(dp[i][j],1LL*dp[i-1][j-1]*C[i]%P);
            }
        for(int i=0;i<=min(tot,k);i++)
            ans=(ans+1LL*dp[tot][i]*Calc(k-i,d))%P;
        printf("%d\n",ans);
        return 0;
    }
    
  • 1

信息

难度
8
分类
(无)
标签
(无)
递交数
26
已通过
3
通过率
12%
上传者