首页 > 其他分享 >CF145C Lucky Subsequence

CF145C Lucky Subsequence

时间:2022-08-17 18:46:08浏览次数:88  
标签:ch return int 个数 Lucky Subsequence CF145C 幸运

题目链接:
洛谷
Codeforces

Problem

这题目翻译真的神了,好多歧义,看不懂,给一个本人翻译:

给你一个长度为 \(n\) 的序列 \(a\),定义幸运数为含有 \(4\) 或 \(7\) 的数,你需要取出它的一个的子序列,满足以下条件:

  • 长度为 \(k\)。
  • 幸运数只能出现 \(1\) 次,其它数可出现任意次数。

问有多少种取法,对 \(10^9+7\) 取模。

Solution

计数题,首先要想好策略,这题只有两种数,所以肯定是枚举其中一种数的个数。

对于幸运数,其数量显然不会很多,所以设 \(f(i,j)\) 为前 \(i\) 种幸运数选 \(j\) 个的方案,由于每种只能选一个,有选或不选,所以:

\[f(i,j)=f(i-1,j)+f(i-1,j-1)\times s_i \]

其中 \(s_i\) 表示第 \(i\) 种幸运数的个数。然后很容易像 01 背包一样把第一维滚掉。

对于非幸运数,直接组合数就可以了。

令 \(t\) 为非幸运数的个数,枚举选 \(i\) 个幸运数,所以最后的答案为:

\[\sum_{i=0}^kf_i\times \binom{t}{k-i} \]

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x)
{
	char ch=getchar();
	int r=0,w=1;
	while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch))r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
	x=r*w;
}
const int N=1e5+7,mod=1e9+7;
int f[N],s[N],cnt,p[N];
map<int,int>mp;
void init()
{
	p[0]=1;
	for(int i=1;i<=1e5;i++)p[i]=p[i-1]*i%mod;
}
int Pow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}
int C(int n,int m)
{
	if(m==0)return 1;
	if(n<m)return 0;
	return p[n]*Pow(p[m],mod-2)%mod*Pow(p[n-m],mod-2)%mod;
}
bool check(int x)
{
	while(x)
	{
		if(x%10!=4&&x%10!=7)return false;
		x/=10;
	}
	return true;
}
main()
{
	init();
	int n,k,t=0;
	read(n);read(k);
	for(int i=1,x;i<=n;i++)
	{
		read(x);
		if(check(x))
		{
			if(!mp[x])mp[x]=++cnt;
			s[mp[x]]++;
		}
		else t++;
	}
	f[0]=1;
	for(int i=1;i<=cnt;i++)
	for(int j=cnt;j>=1;j--)
		f[j]=(f[j]+f[j-1]*s[i]%mod)%mod;
	int ans=0;
	for(int i=0;i<=k;i++)
		ans=(ans+f[i]*C(t,k-i)%mod)%mod;
	cout<<ans;
	return 0;
}

标签:ch,return,int,个数,Lucky,Subsequence,CF145C,幸运
From: https://www.cnblogs.com/LAK666/p/16596320.html

相关文章