1 首先 ans=c(n,a[0] )*c(n-a[0],a[1])*(n-a[0]-a[1],a[2])......
a[i]: 含义 在数列中i的个数有a[i]个
2 如何判断 x*y>p(1e18LL)--->乘法变除法 p/x<y
3 如何判断组合数 c (n,m)是否溢出 这里采用交叉乘除 c(n,m)=c(n-1,m-1)*(n/m)
想办法先除掉m: 1)t=gcd(n,m) n/=t m/=t
2) k=c(n-1,m-1)/m
3) 再判断 k*n 是否溢出
其实m最大为20左右。。。
法二: 判断C(n,m)是否溢出 可把每一个数分解为素数的乘积,用加减法代替乘除法 (代码是法一)
1106: xry111的排列
时间限制: 4 Sec 内存限制: 128 MB
提交: 122 解决: 11
[提交][状态][讨论版]
题目描述
fpcsong有一天闲着无聊,就拿了一张纸,写下了n个数a1, a2, ..., an,问xry111这些数的全排列的个数是多少。xry111说不就是n!么,然而fpcsong说你个SB,这些数有好多重复的。于是xry111就傻眼了,快帮帮他吧。
fpcsong讨厌高精度,所以如果答案超过了1018,就输出“Look, shability!”。
输入
多组数据(最多100组)。
每组数据,第1行,一个整数n。之后1行,包含n个整数a1, a2, ..., an,用空格分割。
对于90%的数据,有0<n≤100。
对于100%的数据,有0<n≤106,0≤ai≤1000。
注意:输入文件较大,请使用较快的IO。
输出
对于每组数据输出1行,若答案不超过1018,输出答案,否则输出“Look, shability!”。
样例输入
4
0 0 0 1
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例输出
4
Look, shability!
1
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const LL p=1e18;
int a[],n;
int gcd (int a,int b) {
return !b?a:gcd(b,a%b);
}
LL C (int n,int m) {
if (n-m<m) m=n-m;
LL sum=; int k=;
for (int i=n-m+;i<=n;i++,k++) {
int d=gcd (i,k);
int t1=i/d; int t2=k/d;
LL x=sum/(LL)t2; sum=x*(LL)t1;
if (sum<=||sum>p||p/x<t1) return ;
}
return sum;
}
int main ()
{
while (~scanf ("%d",&n)) {
memset (a,,sizeof(a)); int _max=;
for (int i=;i<=n;i++) {
int x; scanf ("%d",&x);
a[x]++; _max=max (_max,x);
}
int x=n; LL ans=; bool flag=;
for (int i=;i<=_max;i++) {
if (a[i]) {
LL t1=ans;
LL t2=C (x,a[i]);
ans*=t2;
if (ans<=||ans>p||p/t1<t2) { flag=; break;}
x-=a[i];
}
}
if (!flag) printf ("Look, shability!\n");
else printf ("%lld\n",ans);
}
return ;
}
!!永远记住代码不重要,思想最重要。。。
xdoj-1106(判断组合数是否溢出)的更多相关文章
-
判断文本是否溢出/hover显示全部
前言 在工作中我们经常会遇到,文字过多,需要用省略号,并且鼠标hover的时候 还需要 显示全部的文字的需求. 正文 文字过多需要用省略号的实现:上代码啦 .ellipsis { width: 100 ...
-
Python解释器判断整数相加溢出
溢出,则和的最高位(即符号位)与两个加数都不相同,例如 1)非负数+非负数=负数 2)负数+负数=非负数 那么,假设x为a与b的和,((a^b)>=0 && (x^a)<0 ...
-
js判断文本是否溢出容器
onShowNameTipsMouseenter: function(e) { var target = e.target; var containerLength = $(target).width ...
-
jQuery关于文字内容溢出用点点点(…)省略号表示
1.jQuery限制字符字数的方法代码很简单,使用也很方便,如下: $(document).ready(function(){//限制字符个数$(“.zxx_text_overflow”).each( ...
-
C#使用checked关键字处理";溢出";错误
代码如下: private void btnCalculate_Click(object sender, EventArgs e) { byte num1, num2;//定义两个byte变量 if( ...
-
css单行文本及多行文本溢出显示省略号
关于文本溢出的相关属性: 1. text-overflow: clip|ellipsis|string; 该属性规定当文本溢出包含元素时发生的事情. clip : 修剪文本. ellipsis : ...
-
datagrid 文本溢出时候 鼠标经过出现提示信息tooltip
1只有文本溢出的单元格鼠标经过才显示提示信息 $('.datagrid-cell').mouseover(function () { if (this.offsetWidth < this.sc ...
-
【PAT甲级】1065 A+B and C (64bit) (20 分)(大数溢出)
题意: 输入三个整数A,B,C(long long范围内),输出是否A+B>C. trick: 测试点2包括溢出的数据,判断一下是否溢出即可. AAAAAccepted code: #defin ...
-
Leetcode分类刷题答案&;心得
Array 448.找出数组中所有消失的数 要求:整型数组取值为 1 ≤ a[i] ≤ n,n是数组大小,一些元素重复出现,找出[1,n]中没出现的数,实现时时间复杂度为O(n),并不占额外空间 思路 ...
随机推荐
-
MVC视图展现模式之移动布局解析-续集
网站就必须用响应式布局吗?MVC视图展现模式之移动布局:http://www.cnblogs.com/dunitian/p/5213787.html demo:http://pan.baidu.com ...
-
高性能 CSS3 动画
注:本文出自腾讯AlloyTeam的元彦,文章也可以在github上浏览.请尊重版权,转载请注明来源,多谢-- 高性能移动Web相较PC的场景需要考虑的因素也相对更多更复杂,我们总结为以下几点: 流量 ...
-
C#基础---C#如何对Json字符串处理
Json字符串对于做web应用的应该很熟悉,其实在很多请求我们返回的都是Json字符串.那对于C#代码如何处理Json字符串呢,.Net封装了一个类叫做JavaScriptSerializer[MSD ...
-
javascript基础总结
一.语法 ------------------------------ javascript中的一切(变量.函数名和操作符)都区分大小写. 标识符:就是指变量.函数.属性的名字,标识符要求如下 1 第 ...
-
C#图解教程读书笔记(第15章 委托)
委托是C#的一个很重要的知识点. 1.什么是委托 委托在我认为,就是一系列格式相同的方法列表,可能就是定义的名称不一致,参数.返回值等都是一样的. 2.如何声明委托 delegate void MyF ...
-
SqlServer tsql语句大全
下列语句部分是Mssql语句,不可以在access中使用. SQL分类: DDL—数据定义语言(CREATE,ALTER,DROP,DECLARE) DML—数据操纵语言(SELECT,DELETE, ...
-
softmax_cross_entropy_with_logits
softmax_cross_entropy_with_logits 原创文章,请勿转载 函数定义 def softmax_cross_entropy_with_logits(_sentinel=Non ...
-
[ZJOI2008]泡泡堂
题目描述 第XXXX届NOI期间,为了加强各省选手之间的交流,组委会决定组织一场省际电子竞技大赛,每一个省的代表队由n名选手组成,比赛的项目是老少咸宜的网络游戏泡泡堂.每一场比赛前,对阵双方的教练向组 ...
-
javascript 正则表达式学习
正则表达式 正则表达式,一个描述字符模式的对象.javascript的RegExp类表示正则表达式,String和RegExp都定义了方法,后者使用正则表达式进行强大的模式和匹配与替换功能. -- f ...
-
微信小程序新闻列表功能(读取文件、template模板使用)
微信小程序新闻列表功能(读取文件.template) 不忘初心,方得始终.初心易得,始终难守. 在之前的项目基础上进行修改,实现读取文件内容作为新闻内容进行展示. 首先,修改 post.wxml 文件 ...