CodeForces 146E - Lucky Subsequence DP+扩展欧几里德求逆元

CodeForces 146E - Lucky Subsequence DP+扩展欧几里德求逆元

题意:

一个数只含有4,7就是lucky数...现在有一串长度为n的数...问这列数有多少个长度为k子串..这些子串不含两个相同的lucky数...

子串的定义..是从这列数中选出的数..只要序号不同..就不不同的串..如 1 1 的长度为1的子串有两个

题解:

解题前可以先求一下1000000000内有多少个数是lucky的...可以递推的求..也可以暴力求~~可以看出最多1022个lucky数..很少...

现将这堆数的所有lucky数找出来...把相同的放在一个lucky数里计数...

dp[ i ] [ k ] 代表到了第i个lucky数..选了k个lucky数的方案总数...

dp全部处理完后统计答案:

ans= sigma ( dp [ last ] [ i ]  + C ( 非lucky数个数 ) ( n-i ) )  , ( 0<=i<=这堆数中lucky数总数 )      C求组合数

那么现在的关键是求C ( a, b) 了..有题目数据可知...a,b都可能达到10^5...如果用传统的递推: C( i , j )=C( i-1 , j )+C( i-1 , j-1 ) 是会爆空间+爆时间的...

要求C ( a, b )只能用数学知识了...

C( a, b ) =  a! / (b!*(a-b)!)  可以先把n!打个表出来.所有的阶乘就可以直接的取...问题进一步简化为求 ( a / b ) % 1000000007

如果a,b分别取模计算..是错误的...只能 a * (b的逆元) % 1000000007

这里所说的b你逆元,实质上是在模1000000007系统中b的逆元..也就是(b*x)%1000000007=1

问题再简化...求b的逆元....两种思路...

1、费马小定理

根据费马小定理 ( a^(p-1) ) % p = 1 当p是质数并且a不是p的倍数....而题目给的1000000007就是一个质数..所以对于任意一个非p倍数的数有

( a * (a^(p-2) ) % p =1 ..所以 a^(p-2) 就是 a的逆元...用快速幂取模求出即可

2、扩展欧几里德

ax+by = gcd(a,b) 扩展欧几里得就是来求满足条件的一组x,y的...

令x为a的逆元...p为要模的数...根据逆元的定义有 ( a*x ) %p=1....可以理解为 a*x - p*y = 1 , 其中y为整数.

又有 gcd (a,p) = 1..那么 a*x - p*y = gcd (a,p) ..这样就成了拓展欧几里得的形式了..求出x即可

总的来说..费马小定理来得方便...但扩展欧几里德的应用范围更广

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 1200using namespace std;int n,k,temp[100005],m;ll lucky[MAXN],dp[MAXN][MAXN],factorial[100005];bool IsLucky(int x){ while (x) { if (x%10!=4 && x%10!=7) return false; x/=10; } return true;}void PreWork(){ factorial[0]=1; for (ll i=1;i<=100000;i++) factorial[i]=(factorial[i-1]*i)%oo; return;}void Ex_Gcd(ll a,ll b,ll &x,ll &y){ if (b==0) { x=1,y=0; return; } Ex_Gcd(b,a%b,x,y); ll t; t=x,x=y,y=t-a/b*y; return;}ll C(ll a,ll b){ ll x,y; if (b>a) return 0; b=(factorial[b]*factorial[a-b])%oo; a=factorial[a]; Ex_Gcd(b,oo,x,y); a=(a*x)%oo; if (a<0) a+=oo; return a;}int main(){ PreWork(); int i,j,num; ll ans; while (~scanf("%d%d",&n,&k)) { m=0; for (i=1;i<=n;i++) { int x; scanf("%d",&x); if (IsLucky(x)) temp[++m]=x; } sort(temp+1,temp+1+m); temp[0]=num=0; for (i=1;i<=m;i++) if (temp[i]!=temp[i-1]) lucky[++num]=1; else lucky[num]++; memset(dp,0,sizeof(dp)); for (i=0;i<=num;i++) dp[i][0]=1; for (i=1;i<=num;i++) for (j=1;j<=i;j++) dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*lucky[i])%oo; ans=0; for (i=0;i<=min(k,m);i++) ans=(ans+dp[num][i]*C(n-m,k-i))%oo; printf("%I64d\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。