xdoj-1106(判断组合数是否溢出)

时间:2022-09-14 22:05:08

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(判断组合数是否溢出)的更多相关文章

  1. 判断文本是否溢出&sol;hover显示全部

    前言 在工作中我们经常会遇到,文字过多,需要用省略号,并且鼠标hover的时候 还需要 显示全部的文字的需求. 正文 文字过多需要用省略号的实现:上代码啦 .ellipsis { width: 100 ...

  2. Python解释器判断整数相加溢出

    溢出,则和的最高位(即符号位)与两个加数都不相同,例如 1)非负数+非负数=负数 2)负数+负数=非负数 那么,假设x为a与b的和,((a^b)>=0 && (x^a)<0 ...

  3. js判断文本是否溢出容器

    onShowNameTipsMouseenter: function(e) { var target = e.target; var containerLength = $(target).width ...

  4. jQuery关于文字内容溢出用点点点&lpar;…&rpar;省略号表示

    1.jQuery限制字符字数的方法代码很简单,使用也很方便,如下: $(document).ready(function(){//限制字符个数$(“.zxx_text_overflow”).each( ...

  5. C&num;使用checked关键字处理&quot&semi;溢出&quot&semi;错误

    代码如下: private void btnCalculate_Click(object sender, EventArgs e) { byte num1, num2;//定义两个byte变量 if( ...

  6. css单行文本及多行文本溢出显示省略号

    关于文本溢出的相关属性: 1. text-overflow: clip|ellipsis|string;   该属性规定当文本溢出包含元素时发生的事情. clip : 修剪文本. ellipsis : ...

  7. datagrid 文本溢出时候 鼠标经过出现提示信息tooltip

    1只有文本溢出的单元格鼠标经过才显示提示信息 $('.datagrid-cell').mouseover(function () { if (this.offsetWidth < this.sc ...

  8. 【PAT甲级】1065 A&plus;B and C &lpar;64bit&rpar; &lpar;20 分&rpar;(大数溢出)

    题意: 输入三个整数A,B,C(long long范围内),输出是否A+B>C. trick: 测试点2包括溢出的数据,判断一下是否溢出即可. AAAAAccepted code: #defin ...

  9. Leetcode分类刷题答案&amp&semi;心得

    Array 448.找出数组中所有消失的数 要求:整型数组取值为 1 ≤ a[i] ≤ n,n是数组大小,一些元素重复出现,找出[1,n]中没出现的数,实现时时间复杂度为O(n),并不占额外空间 思路 ...

随机推荐

  1. MVC视图展现模式之移动布局解析-续集

    网站就必须用响应式布局吗?MVC视图展现模式之移动布局:http://www.cnblogs.com/dunitian/p/5213787.html demo:http://pan.baidu.com ...

  2. 高性能 CSS3 动画

    注:本文出自腾讯AlloyTeam的元彦,文章也可以在github上浏览.请尊重版权,转载请注明来源,多谢-- 高性能移动Web相较PC的场景需要考虑的因素也相对更多更复杂,我们总结为以下几点: 流量 ...

  3. C&num;基础---C&num;如何对Json字符串处理

    Json字符串对于做web应用的应该很熟悉,其实在很多请求我们返回的都是Json字符串.那对于C#代码如何处理Json字符串呢,.Net封装了一个类叫做JavaScriptSerializer[MSD ...

  4. javascript基础总结

    一.语法 ------------------------------ javascript中的一切(变量.函数名和操作符)都区分大小写. 标识符:就是指变量.函数.属性的名字,标识符要求如下 1 第 ...

  5. C&num;图解教程读书笔记(第15章 委托)

    委托是C#的一个很重要的知识点. 1.什么是委托 委托在我认为,就是一系列格式相同的方法列表,可能就是定义的名称不一致,参数.返回值等都是一样的. 2.如何声明委托 delegate void MyF ...

  6. SqlServer tsql语句大全

    下列语句部分是Mssql语句,不可以在access中使用. SQL分类: DDL—数据定义语言(CREATE,ALTER,DROP,DECLARE) DML—数据操纵语言(SELECT,DELETE, ...

  7. softmax&lowbar;cross&lowbar;entropy&lowbar;with&lowbar;logits

    softmax_cross_entropy_with_logits 原创文章,请勿转载 函数定义 def softmax_cross_entropy_with_logits(_sentinel=Non ...

  8. &lbrack;ZJOI2008&rsqb;泡泡堂

    题目描述 第XXXX届NOI期间,为了加强各省选手之间的交流,组委会决定组织一场省际电子竞技大赛,每一个省的代表队由n名选手组成,比赛的项目是老少咸宜的网络游戏泡泡堂.每一场比赛前,对阵双方的教练向组 ...

  9. javascript 正则表达式学习

    正则表达式 正则表达式,一个描述字符模式的对象.javascript的RegExp类表示正则表达式,String和RegExp都定义了方法,后者使用正则表达式进行强大的模式和匹配与替换功能. -- f ...

  10. 微信小程序新闻列表功能(读取文件、template模板使用)

    微信小程序新闻列表功能(读取文件.template) 不忘初心,方得始终.初心易得,始终难守. 在之前的项目基础上进行修改,实现读取文件内容作为新闻内容进行展示. 首先,修改 post.wxml 文件 ...