Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
Petya has sequence a consisting of n integers.
The subsequence of the sequence a is such subsequence that can be obtained from a by removing zero or more of its elements.
Two sequences are considered different if index sets of numbers included in them are different. That is, the values of the elements do not matter in the comparison of subsequences. In particular, any sequence of length n has exactly 2n different subsequences (including an empty subsequence).
A subsequence is considered lucky if it has a length exactly k and does not contain two identical lucky numbers (unlucky numbers can be repeated any number of times).
Help Petya find the number of different lucky subsequences of the sequence a. As Petya's parents don't let him play with large numbers, you should print the result modulo prime number 1000000007 (109 + 7).
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 105). The next line contains n integers ai (1 ≤ ai ≤ 109) — the sequence a.
On the single line print the single number — the answer to the problem modulo prime number 1000000007 (109 + 7).
3 2 10 10 10
3
4 2 4 4 7 7
4
In the first sample all 3 subsequences of the needed length are considered lucky.
In the second sample there are 4 lucky subsequences. For them the sets of indexes equal (the indexation starts from 1): {1, 3}, {1, 4},{2, 3} and {2, 4}.
星期六模拟赛的一道题。。。
说是NOIP模拟赛我怎么觉得有点不像呢。。。果真我还是太弱了。。有种NOIP要爆蛋的即视感。。
.
比赛的时候很快就想到了把\(luckynum\)提出来然后再处理。。。然而我一直接一直在想先求出所有的排列。。然后减去不符合的。。然后就跑偏了。。。
过了一个小时才发现直接求可能的方案简单多了。。。我们先只考虑\(luckynum\)。用\(dp\)处理,\(f[i][j]\)表示前\(i\)种数中取\(j\)种树的方案数。。。然后转移\(f[i][j] = f[i-1][j-1]*num[i]\)。。。然后无关的数求一下组合数统计答案就好了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1e9+7;
const int N = 100010;
int a[N],b[N],c[N],jc[N],jcn[N],f[N],num[N],tot,sum,ans,n,m,k;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
int lucky(int x){
if (x==0) return 0;
while (x){
int s = x%10;
if (s!=4 && s!=7) return 0;
x/=10;
}
return 1;
}
int ksm(int a,int k){
int res = 1;
for (;k;k>>=1,a=1ll*a*a%mod) if (k&1) res = 1ll*res*a%mod;
return res;
}
int C(int n,int m){
if (m>n) return 0;
return 1ll*jc[n]*jcn[m]%mod*jcn[n-m]%mod;
}
int main(){
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
n = read();k = read();
jc[0] = jc[1] = 1;jcn[0] = jcn[1] = 1;
for (int i=2;i<=n;i++) jc[i]=1ll*jc[i-1]*i%mod;
jcn[n]=ksm(jc[n],mod-2);
for (int i=n-1;i>1;i--) jcn[i]=1ll*(i+1)*jcn[i+1]%mod;
for (int i=1;i<=n;i++){
a[i] = read();
if (lucky(a[i])) c[++sum] = a[i];
}
sort(c+1,c+1+sum);tot = 1;
for (int i=1;i<=sum;i++){
if (c[i]==c[i+1]) num[tot]++;
else num[tot++]++;
}
tot--;
f[0] = 1;
for (int i=1;i<=tot;i++)
for (int j=min(i,k);j;j--)
f[j] = (1ll*f[j-1]*num[i]+f[j])%mod;
n-=sum;
for (int i=0;i<=min(tot,k);i++)
ans = (1ll*f[i]*C(n,k-i)+ans)%mod;
printf("%d",ans);
}
2023年4月23日 19:26
crediblebh
2024年12月23日 18:34
Every one of the substance you said in post is too great and can be extremely helpful. I will remember it, much obliged for sharing the data continue upgrading, looking forward for more posts.Thanks . Decent to be going to your web journal once more, it has been months for me. Well this article i’ve been sat tight for so long. I require this article to finish my task in the school, and it has same theme with your article. Much obliged, awesome offer. This is such an extraordinary asset, to the point that you are giving and you give it away for nothing. I cherish seeing sites that comprehend the benefit of giving a quality asset to free. It is the old what circumvents comes around schedule
2024年12月23日 19:15
Thanks for this article . practical challenges that come with these advancements.
2024年12月23日 19:28
Personally, I find this vision of the future both thrilling and a bit daunting. It's clear that staying informed and skilled in AI and technology is crucial. That's why I'm planning to join an AI and tech bootcamp. It's a great way to stay ahead of the curve, understand the latest developments, and ensure I can make the most of these incredible tools in both my personal and professional life. If you're as excited about this future as I am, I highly recommend considering a boot camp too.
2024年12月23日 19:38
The Fourth Industrial of exploration.
2024年12月23日 19:40
Hello! I'm writing from Brazil, and I'm excited to be part of a project that aims to educate and inspire Brazilians to seek knowledge and work towards a better world. Many people in Brazil love nature and our
2024年12月23日 19:40
We are now facing a new wave and the rest, we can be confident of one thing: we are facing the genuinely unprecedented.
2024年12月23日 19:49
AI, as reported, is about data (or information in general). But what about creativity or innovation? Right now, these are human capabilities and that is what scientists and engineers use to make new things or better things. That's what we really need. I use my own techniques to create, others do something different. We need to teach (and inspire) young people to learn how to create. Perhaps AI can help.
2024年12月23日 20:10
Undeniably, the AI revolution is a paradigm shift on par with the graphical user interface (GUI). While the internet, social media, mobile technology, and cloud computing were transformative, Microsoft's rapid adaptation to the age of General Artificial Intelligence (GAI) is remarkable. This proactive approach likely positions them for significant early advantages.
2024年12月23日 20:15
Thanks for this article challenges that come with these advancements.
2024年12月23日 20:16
Over millennia, humanity ever-evolving fabric of human life.
2024年12月23日 20:22
Is it possible to make available AI and GPT softwares (and the computer bodies needed) to schools in poorest regions- early learning schools- with trained support staff and software operating volunteers? How could people at the lowest level grow along with such technology and contribute to defining and designing solutions where they live?
2024年12月23日 20:24
It effectively conveys my appreciation for AI and its assistance in my work and travels, especially since English is not my native language. im also express my admiration for AI's fast-growing capabilities and its positive impact on your life.
2024年12月23日 20:26
incorrect. incorrect. incorrect. First of all, mathematics is the pure study of numbers and equations. It does not require other sciences. However, other sciences do require mathematics. Even if you use math, the results of a scientific study do not even come close to providing 100% certainty! Secondly, if you want to learn math, then you better learn the Pythagorean theorem!
2024年12月23日 20:27
It is interesting because I believe God exists as a floating consiousness and not in or as any physical form . But as a conscious that was aware before the earth was created. And because the analogy of ai and god having similarities one is limited in spreading it's conscious awareness without actual access to power. But if ai does manifest into a singular identity would it not be wise to side on caution as an individual consciousness that currently lives on this planet and try and live by some of the versus in the bible relating to human nature money fame and greed .
2024年12月23日 20:29
What I wanted to say is that I sometimes feel that the world is going crazy and doesn't make sense. A lot of people can barely make ends meet and there may not seem to be any apparent solution. It doesn't make sense that a lot of people would say that they want to learn advanced math, but that they don't think they need to know about things like the Pythagorean theorem. Furthermore, I feel that the basic knowledge taught in school is unfairly ridiculed. My idea to solve this is that maybe jobs could be made available for people who actually learned in school. If there were jobs for people who learned in high school, then I think fewer people would criticize the basic knowledge. Once fewer people criticize basic knowledge, then hopefully the knowledge levels of the population would increase, and then it might even be possible for basic computer coding to be taught to everyone who goes to high school! As knowledge increases, so too would productivity and scientific achievement!
2024年12月23日 20:31
Mathematics is the science of studying certain things with 100% accuracy so that if we follow them we can get the same results or at least close to 100%. Because mathematics is always related to other branches of science, so that we can better master mathematics, it must be combined with other branches of science and cannot stand alone.
2024年12月23日 20:33
I am curious whether or not current technology can be leveraged to establish some guardrails in AI. For example, can NFT methods be used to prevent deep fakes? Can blockchain methodologies be used to maintain the integrity of a source of information?
2024年12月23日 20:49
Regarding Climate Change: The characteristic of Climate Change is its' relatively stable cycles of changes over millennia. AI would not limit its' scope over the
2024年12月23日 20:55
Hello! I'm writing from Brazil, difference.
2024年12月23日 21:14
We present two sets of arguments. The first is an enquiry into the idea that ATEs estimated from RCTS are likely to be closer to the truth than those estimated in other ways. The second explores how to use the results of RCTs once we have them.
2024年12月23日 21:16
It is interesting becausBut if ai does manifest into a singular identity would it not be wise to side on caution as an individual consciousness that currently lives on this planet and try and live by some of the versus in the bible relating to human nature money fame and greed .
2024年12月23日 21:21
When technology first came into the workplace, we were told that workers would gain more leisure time, would have shorter working days & weeks, and would not have to any of the dirty and unpalatable jobs. It was also suggested that all of us would share in the financial and lifestyle benefits. Unfortunately, unemployment is high, some people live in intergenerational poverty,and some people work full-time and are still below the