问题 D: 记一次惨痛的教训(组合数的计算)

2024-01-26 07:48

本文主要是介绍问题 D: 记一次惨痛的教训(组合数的计算),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

传说中很多大牛喜欢用自己姓名拼音的重排列,比如著名的吕凯风大牛,他的姓名拼音是lvkaifeng,重新排列之后就得到了VFleaKing,也就是著名的伏特跳蚤国王。现在,火星人觉得VFleaKing太强啦!于是他们也要这样取他们的ID名,现在问题来了,他们的名字都非常长,而且都是由火星文组成的(火星文有好多好多字符)。火星人想请你帮他们算算如果把他们的名字重排有几种方案,当然了,原序列也是一种方案啦如果你不帮他们算出正确的答案你就会死哦

形式化描述:给定一个长度为N的整数序列A1…N,求有多少种不同长度为的N的整数序列B1…N是A的重排,即可重集{Ai}={Bi}。两个序列不同当且仅当它们任一位置上的元素不相等。

输入

第1行:两个正整数N,k,其中N代表该火星人名字的长度,k代表火星文有多少种字符,我们不妨设在有k种字符的情况下的火星文中的字符分别是0到k−1。
第2行:用空格隔开的N个正整数,代表这个火星人的名字,我们保证这N个数字一定在0到k−1的范围内。

输出

第1行:一个正整数——这个火星人的名字重排方案数对109+7取模的结果(火星人的逻辑特别奇怪,只要知道模数是多少就可以放过你了)。

样例输入
复制样例数据 4 2
0 0 1 1

样例输出
6

提示

满足条件的重排共有如下6种:
0,0,1,1
0,1,0,1
1,0,0,1
0,1,1,0
1,0,1,0
1,1,0,0

被自己坑了:109 +7是1e9+7而不是10e9+7,比赛时卡了一个半小时,一直wa,赛后补题又花了快2个小时才补起来,惨痛的教训;还有使用map超时也是一个注意点map的操作是O(logn)的复杂度

思路:设数0到k-1分别有a1,a2,…,ak个,由题目可以推出来ans=C(n,a1)*C(n-a1,a2) * … *C(n-a1-a2-…-an-1,an);
重点是组合数的计算:
1)可以直接利用组合数的公式C(n,m)=n! /((n-m)!m!),因为要%mod,所以要求(n-m)!和m!的逆元,直接利用线性的算法求阶乘的逆元即可,n!直接O(n)求即可;

2)或者直接使用卢卡斯定理也可以

代码1:

const long long  mod=1e9+7;
int len=0;
typedef long long ll;
ll fac[2000005];
ll inv[2100000]={0};
ll cnt[2000005];
template <typename _tp> inline _tp read(_tp&x){char ch=getchar(),sgn=0;x=0;while(ch^'-'&&!isdigit(ch))ch=getchar();if(ch=='-')ch=getchar(),sgn=1;while(isdigit(ch))x=x*10+ch-'0',ch=getchar();if(sgn)x=-x;return x;
}ll qmod(ll a,ll b)
{ll sum=1;while(b){if(b&1) sum=sum*a%mod;a=a*a%mod;b>>=1;}sum%=mod;return sum;
}void getinv(long long n)
{fac[0]=1;///求阶乘的最大值for(register int i=1;i<=n;i++)  fac[i]=fac[i-1]*i%mod;///求阶乘最大值的逆元inv[n]=qmod(fac[n],mod-2);for(register int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}inline ll C(ll m,ll n)
{ll ans=1;ans=fac[m]*inv[n]%mod*inv[m-n]%mod;//cout<<fac[m]<<' '<<inv[n]<<' '<<inv[m-n]<<endl;if(ans==0) return 1;return ans;
}int main()
{getinv(2000005);ll n,k;cin>>n>>k;for(register int i=1;i<=n;i++){ll a;read(a);cnt[a]++;}//cout<<Lucas(2,3,4);ll ans=1;ll Cnt=n;for(int i=1;i<=n;i++){ans=ans%mod*C(Cnt,cnt[i])%mod;Cnt-=cnt[i];}ans%=mod;cout<<ans<<endl;}

代码2(卢卡斯定理)

const long long  mod=1e9+7;
long long  cnt[2000005],fac[2000005];
int len=0;
typedef long long ll;
void ini(int n)
{fac[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i]*i%mod;
}ll exgcd(ll a,ll b,ll& x,ll& y){if(a%b==0){x=0,y=1;return b;}ll r,tx,ty;r=exgcd(b,a%b,y,x);y-=a/b*x;
}ll comp(ll a,ll b,ll m){if(a<b) return 0;if(a==b) return 1;if(b>a-b) b=a-b;ll ans=1,ca=1,cb=1;ca=fac[a];cb=fac[b]*fac[a-b]%m;ll x,y;exgcd(cb,m,x,y);x=(x%m+m)%m;ans=ca*x%m;return ans;
}ll lucas(ll a,ll b,ll m){ll ans=1;while(a&&b){ans=(ans*comp(a%m,b%m,m))%m;a/=m;b/=m;}return ans;
}int main()
{ini(2000002);map<int ,int >m;ll n,k;cin>>n>>k;for(int i=1;i<=n;i++){int a;scanf("%d",&a);cnt[a]++;}ll ans=1;ll Cnt=n;for(int i=1;i<=n;i++){ans=ans%mod*lucas(Cnt,cnt[i],mod);Cnt-=cnt[i];}ans%=mod;cout<<ans<<endl;
}

这篇关于问题 D: 记一次惨痛的教训(组合数的计算)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/646108

相关文章

解决RocketMQ的幂等性问题

《解决RocketMQ的幂等性问题》重复消费因调用链路长、消息发送超时或消费者故障导致,通过生产者消息查询、Redis缓存及消费者唯一主键可以确保幂等性,避免重复处理,本文主要介绍了解决RocketM... 目录造成重复消费的原因解决方法生产者端消费者端代码实现造成重复消费的原因当系统的调用链路比较长的时

深度解析Nginx日志分析与499状态码问题解决

《深度解析Nginx日志分析与499状态码问题解决》在Web服务器运维和性能优化过程中,Nginx日志是排查问题的重要依据,本文将围绕Nginx日志分析、499状态码的成因、排查方法及解决方案展开讨论... 目录前言1. Nginx日志基础1.1 Nginx日志存放位置1.2 Nginx日志格式2. 499

kkFileView启动报错:报错2003端口占用的问题及解决

《kkFileView启动报错:报错2003端口占用的问题及解决》kkFileView启动报错因office组件2003端口未关闭,解决:查杀占用端口的进程,终止Java进程,使用shutdown.s... 目录原因解决总结kkFileViewjavascript启动报错启动office组件失败,请检查of

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤