【HDU-5976】Detachment【二分+模逆元(费马小定理+同余式解法)】

【HDU-5976】Detachment【二分+模逆元(费马小定理+同余式解法)】

代码:

#include <iostream>

using namespace std;

typedef long long LL;
const int SIZE = 5e4;
const int LIM = 1e5;
const LL MOD = 1e9 + 7;
const LL MOD2 = 1e9 + 5;
LL pre[SIZE];
LL fractorial[SIZE];
// modula reverse identity element
LL mr[SIZE];

LL fastPow(LL base, LL p) {
    LL ret = 1;
    while (p) {
        if (p & 1) ret = ret * base % MOD;
        p >>= 1;
        if (p) base = base * base % MOD;
    }
    return ret;
}

int main(void) {
    // init
    // the index is the number of answer's segments
    pre[2] = 0;
    pre[3] = 4;
    int maxn;
    for (LL i = 4; pre[i - 1] <= 1e9; i++) {
        pre[i] = pre[i - 1] + i + 1;
        // cout << i << " : " << pre[i] << "\n";
        maxn = i;
    }
    // build the fractorial numbers' array
    fractorial[0] = fractorial[1] = 1;
    for (LL i = 2; i < SIZE; i++) {
        fractorial[i] = fractorial[i - 1] * i % MOD;
    }
    // build the modulo reverse identity elements' array
    for (LL i = 1; i < SIZE; i++) {
        mr[i] = fastPow(i, MOD2);
    }
    int t;
    LL x;
    // start to deal with input
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &x);
        if (x < 5) {
            printf("%lld\n", x);
            continue;
        }
        // offset is 5
        x -= 5;
        int l = 2, r = maxn;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (pre[mid] > x) r = mid;
            else l = mid + 1;
        }
        if (pre[l] > x) l--;
        x += 5;
        LL diff = x - (l * (l + 3) / 2);
        // printf("cnt : %d\n", l);
        // printf("fractorial[%d]: %lld\n", l + 2, fractorial[l + 2]);
        // printf("pre[%d]: %lld\n", l, pre[l]);
        // printf("diff: %lld\n", diff);
        if (diff > l) {
            printf("%lld\n", fractorial[l + 3] * mr[2] % MOD * mr[2 * l + 3 - diff] % MOD);
        } else {
            printf("%lld\n", fractorial[l + 2] * mr[l + 2 - diff] % MOD);
        }
    }
}

参考了:https://blog.csdn.net/qq_34374664/article/details/53466435

https://www.cnblogs.com/hsd-/p/5325780.html

感谢大神们的分享。

另外,这个数列十分有趣,附上OEIS相关页面:

https://oeis.org/A034893

相关论文:https://cs.uwaterloo.ca/journals/JIS/VOL8/Doslic/doslic15.pdf