热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

个人训练赛第十七场问题D:vfk式名字重排

有一种隐忍其实是蕴藏着的一种力量,有一种静默其实是惊天的告白。题目描述传说中很多大牛喜欢用自己姓名拼音的重排列,比如著名的吕凯风大牛,
有一种隐忍其实是蕴藏着的一种力量,有一种静默其实是惊天的告白。

题目描述

传说中很多大牛喜欢用自己姓名拼音的重排列,比如著名的吕凯风大牛,他的姓名拼音是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

 

这个题考察排列组合问题,手算结果大家应该都知道怎么算(这个高中学过,就是给你n个m种数让你求排列方式),比如n=7,m=3,数为1,2,1,0,0,2,1,则可知ans=n!/(A(3,3)*A(2,2)*A(2,2))=210,这里除法用逆元实现。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1000000007
typedef long long ll;
using namespace std;
int k,n,ls,a[2000010];
ll s[2000010];
ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1)ans=(ans*a)%inf;a=(a*a)%inf;b>>=1;}return ans;
}
ll ny(ll a,ll p){return ksm(a,p-2);
}
int main(){int i;ll jg;s[0]&#61;1;for(i&#61;1;i<&#61;2000010;i&#43;&#43;)s[i]&#61;(s[i-1]*i)%inf;//求阶层scanf("%d%d",&n,&k);for(i&#61;0;i1)jg&#61;(jg*ny(s[a[i]],inf))%inf;}printf("%lld\n",jg);return 0;
}

 


推荐阅读
  • 本文深入探讨了POJ2762问题,旨在通过强连通分量缩点和单向连通性的判断方法,解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤,并附带完整的代码示例。 ... [详细]
  • 丽江客栈选择问题
    本文介绍了一道经典的算法题,题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈,并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]
  • 本题探讨了在一个有向图中,如何根据特定规则将城市划分为若干个区域,使得每个区域内的城市之间能够相互到达,并且划分的区域数量最少。题目提供了时间限制和内存限制,要求在给定的城市和道路信息下,计算出最少需要划分的区域数量。 ... [详细]
  • 本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数,并使用递推算法和大数处理技术来解决这一问题。 ... [详细]
  • 中科院学位论文排版指南
    随着毕业季的到来,许多即将毕业的学生开始撰写学位论文。本文介绍了使用LaTeX排版学位论文的方法,特别是针对中国科学院大学研究生学位论文撰写规范指导意见的最新要求。LaTeX以其精确的控制和美观的排版效果成为许多学者的首选。 ... [详细]
  • 本文介绍了一种解决二元可满足性(2-SAT)问题的方法。通过具体实例,详细解释了如何构建模型、应用算法,并提供了编程实现的细节和优化建议。 ... [详细]
  • 本题旨在通过给定的评级信息,利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表,或者是否存在冲突或信息不足的情况。 ... [详细]
  • 本文介绍如何通过 JavaScript 实现一个基于鼠标坐标的 Tooltip 弹出层,详细解释了如何获取窗口和文档的尺寸及滚动位置,并优化了代码结构。 ... [详细]
  • CentOS系统安装与配置常见问题及解决方案
    本文详细介绍了在CentOS系统安装过程中遇到的常见问题及其解决方案,包括Vi编辑器的操作、图形界面的安装、网络连接故障排除等。通过本文,读者可以更好地理解和解决这些常见问题。 ... [详细]
  • 本文将详细探讨Linux pinctrl子系统的各个关键数据结构,帮助读者深入了解其内部机制。通过分析这些数据结构及其相互关系,我们将进一步理解pinctrl子系统的工作原理和设计思路。 ... [详细]
  • 在网站制作中随时可用的10个 HTML5 代码片段
    HTML很容易写,但创建网页时,您经常需要重复做同样的任务,如创建表单。在这篇文章中,我收集了10个超有用的HTML代码片段,有HTML5启动模板、空白图片、打电话和发短信、自动完 ... [详细]
  • 深入解析Redis内存对象模型
    本文详细介绍了Redis内存对象模型的关键知识点,包括内存统计、内存分配、数据存储细节及优化策略。通过实际案例和专业分析,帮助读者全面理解Redis内存管理机制。 ... [详细]
  • 由二叉树到贪心算法
    二叉树很重要树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。单就面试而言,在 ... [详细]
  • 并发编程 12—— 任务取消与关闭 之 shutdownNow 的局限性
    Java并发编程实践目录并发编程01——ThreadLocal并发编程02——ConcurrentHashMap并发编程03——阻塞队列和生产者-消费者模式并发编程04——闭锁Co ... [详细]
  • 深入解析RDMA中的队列对(Queue Pair)
    本文将详细探讨RDMA架构中的关键组件——队列对(Queue Pair,简称QP),包括其基本概念、硬件与软件实现、QPC的作用、QPN的分配机制以及用户接口和状态机。通过这些内容,读者可以更全面地理解QP在RDMA通信中的重要性和工作原理。 ... [详细]
author-avatar
手机用户2602906645
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有