【P4370 [Code+#4]组合数问题2】题解

· · 题解

给一个小题目

来源于钟神的讲解

【description】

如何比较 C_{n_1}^{m_1} 与 C_{n_2}^{m_2} 的大小。C_{n_1}^{m_1},C_{n_2}^{m_2}很大，存不下就对了

【solution1】:

我们可以暴力求解计算，显然是不能取模的，这就很被动，因为我们根本存不了那么大，那么我们就可以考虑一下别的方法。

取对数 ： 这么大，我们取个对数就能够比较了， log 显然是单调的，我们对 C_{n}^{m} 取个对数就好，那么我们来推导一下，取对数。

logC_{n}^{m} = log\frac{n!}{m!(n-m)!} = log(n!) - log(m!) - log((n-m)!) = \sum_{i=1}^n \log (i) - \sum_{i=1}^m log(i) - \sum_{i=1}^{n-m}log(i)

来到正片

【P4370 [Code+#4]组合数问题2】

【solution2】 ：

这道题的做法，其实很显然，就是有一个地方很坑，就是 C_{n}^{m} 很大，存不下，这怎么办，根据上面的取对数的操作，我们直接对答案取模，然后，用 \log 去比较，就 OK 了。

【Code】

/*
By : Zmonarch
知识点：
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#define int long long
#define qwq register
#define inf 2147483647
const int kmaxn = 1e6 + 10 ;
const int kmod = 1e9 + 7 ;
inline int read() {
    int x = 0 , f = 1 ; char ch = getchar() ;
    while(!isdigit(ch)) {if(ch == '-') f = - 1 ; ch = getchar() ;}
    while( isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar() ;}
    return x * f ;
}
struct Node{
    int n , m ; 
    double val ; 
    bool operator < (const Node &b) const {return val < b.val ;} 
};
std::priority_queue<Node> q ; 
int n , k , ret ; 
int jc[kmaxn] , inv[kmaxn] ; 
double lg[kmaxn] ; 
void init(int n) {
    inv[1] = inv[0] = jc[0] = 1 ;
    for(qwq int i = 1 ; i <= n ; i++) jc[i] = jc[i - 1] * i % kmod ;
    for(qwq int i = 1 ; i <= n ; i++) lg[i] = lg[i - 1] + log(i) ; 
    for(qwq int i = 2 ; i <= n ; i++) inv[i] = ( - kmod / i + kmod) * inv[kmod % i] % kmod ;
    for(qwq int i = 1 ; i <= n ; i++) inv[i] = inv[i - 1] * inv[i] % kmod ; // 我们要的是阶乘的逆元 
}
signed main() {
    init(kmaxn); n = read() , k = read() ;  
    for(qwq int i = 0 ; i <= n ; i++) 
    {
        Node u ; 
        u.n = n ; u.m = i ; u.val = lg[n] - lg[i] - lg[n - i] ; 
        q.push(u) ; 
    }
    while(k--) 
    {
        Node u = q.top() ; q.pop() ; 
        ret = (ret + jc[u.n] * inv[u.m] % kmod * inv[u.n - u.m]) % kmod ; 
        //printf("%lld %lld %lf\n" , u.n , u.m , u.val) ; 
        Node nxt ; 
        nxt.n = u.n - 1 ; nxt.m = u.m ; nxt.val = (lg[nxt.n] - lg[nxt.m] - lg[nxt.n - nxt.m]) ; 
        q.push(nxt) ; 
    }
    printf("%lld\n" , ret) ; 
    return 0 ;
}