1 条题解
-
0Guest LV 0 MOD
-
0
#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%
- 上传者