Choose and divide ( 爆long long处理 )
程序员文章站
2022-06-02 12:06:07
...
Choose and divide ( 爆long long处理 )
题意:
给出p,q,r,s;
然后按照所给公式算出C(p,q)和C(r,s);输出C(p,q)/C(r,s);
思路:
首先直接算的话会超出范围;
我们通过看公式可以知道,分子分母个数是一样的;
比如
10! / (5!*(10 - 5)!)那么我们可以选择把5!和10!对消,或者(10 - 5)!和10!对消;反正剩下的个数都是一样的,分子是10*9*8*7*6;分母是5*4*3*2*1;
直接算会超出范围,那么我们就乘一个除一个,但是先算C(p,q)再算C(r,s)还是会超出,所以要把两个一起算.
也就是乘一个p,除一个q,再乘一个s,除一个r;然后p,q,r,s都减减;
但是我一开始的做法是这样从大到小算,一直WA;
后来改成从小到大算就过了也就是先成p-q+i,除以i,再乘i,除以r-s+i,在i++就过了,这点我也想不明白;
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,q,s,r;
int main()
{
while ( cin >> p >> q >> r >> s ) {
if ( q*2>p ) q = p-q;
if ( s*2>r ) s=r-s;
double ans = 1.0;
ll down1 = 1,down=1;
for ( ll up1=p-q+1,up=r-s+1; up1<=p||up<=r; up1++,up++ ) {
if ( up1<=p ) { // 两个c放到一个循环里, 从小到大来
ans *= up1;
ans /= 1.0*down1;
}
if ( up<=r ) {
ans *= down;
ans /= 1.0*up;
}
down1 ++; down ++;
}
printf("%.5f\n",ans);
}
return 0;
}
上一篇: 国内九个最适合毕业旅行攻略
推荐阅读
-
前端处理后端传回的 Long 类型数据精度丢失
-
java Long类型转为json后数据损失精度的处理方式
-
Java中关于时间的处理:Calendar、Date、Long、String
-
Choose and divide ( 爆long long处理 )
-
一个php处理oracle的 long型数据的简单例子
-
ORA-00494 enqueue [CF] held for too long故障分析处理
-
ORA-00494 enqueue [CF] held for too long故障分析处理
-
解决JS处理Long类型丢失精度
-
Java中关于时间的处理:Calendar、Date、Long、String
-
java Long类型转为json后数据损失精度的处理方式