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

暑假数学班的题目能让我咕咕咕到现在也是可以的,现在列表里面一堆模板还没做,noip前应该也不会做了2333333
这个题目是当时长者给我们讲的,脑洞真是清奇2333333333
首先分析这个题目的话,难点就在于,我们取模以后没法判断数字的大小了。这个时候有一个比较显然的思路,用double类型去存储组合数。但是组合数太大了,double类型只能存20位左右的精准数字,剩下的全部以浮点数的形式存储,那么怎么比较大小呢?
这也就是这个题目的关键,我们利用对数函数来判断数字的大小。我们统一取log2函数值的大小,这样就可以保证精度的同时判断大小了2333333
代码实现并不难,就是有点小恶心,开始wa了发,后来看到网上dalao的偷懒写法写了一发

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const lo ms = 1e6 + 10;

const lo mo = 1e9 + 7;

lo n, k, ans, fac[ms], inv[ms], fx[4] = {-1, 0, 1, 0}, fy[4] = {0, 1, 0, -1};

double fc[ms];

struct in
{
    lo x, y, c; double lg;
    inline in(lo a, lo b)
    {
        x = a, y = b, lg = fc[a] - fc[b] - fc[a - b];
        c = fac[a] * inv[b] % mo * inv[a - b] % mo;
    }
    inline bool operator < (const in &a) const
    {
        return lg < a.lg;
    }
};

priority_queue <in> qwq;

inline lo ksm(lo x, lo kk)
{
    lo a = x, rt = 1;
    while(kk)
        rt = rt * ((kk & 1) ? a : 1) % mo, a = a * a % mo, kk >>= 1;
    return rt;
}

int main()
{
    re(n), re(k), fac[0] = inv[0] = 1;
    for(ri i = 1; i <= n; i ++)
        fac[i] = (fac[i - 1] * i) % mo, fc[i] = fc[i - 1] + log2(i);
    inv[n] = ksm(fac[n], mo - 2);
    for(ri i = n - 1; i > 0; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    for(ri i = 0; i <= n; i ++)
        qwq.push(in(n, i));
    while(k --)
    {
        in qaq = qwq.top(); qwq.pop();
        ans = (ans + qaq.c) % mo, qaq.x --;
        qwq.push(in(qaq.x, qaq.y));
    }
    printf("%lld", ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注