【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

【HDU-5975】Aninteresting game【lowbit数列】

【HDU-5975】Aninteresting game【lowbit数列】

Solution:

对于查询1,我们可以发现,输出的其实就是L到R之间(包含L和R)所有数的lowbit之和,即\(\sum_{i = L}^Rlowbit(i)\)。但是我们不能去枚举这个数,因为枚举的平均复杂度是\(O(n)\),而这道题的n取值为1e18.我们采用前缀和的方法,因为我们可以\(O(logn)\)的时间复杂度求出从1到n之间的所有数lowbit之和,我们先考虑如果对于单个要求的lowbit,如何求出拥有这个lowbit的数在1到x中出现的次数,如果我们用x除以\(lowbit(i) = 2^k\),就可以知道x中有多少个不小于\(2^k\)的数,用它再减去x中有多少个不小于\(2^{k + 1}\)的个数,就得知了拥有lowbit(i)的数的个数,由于我们要求它们lowbit之和,求出每个拥有lowbit(i)的数的个数,再乘上lowbit(i)就可以了,于是我们的策略就是枚举lowbit(i)。【这道题时间卡很紧,这个查询尽量避免多余的移位、乘除、条件判断操作,否则会超时】

对于查询2,直接把平常树状数组更新操作的循环那里加一个计数,即可解决。

#include <iostream>

using namespace std;

typedef long long LL;

LL query1(LL x) {
    LL ret = 0;
    for (LL i = 1; i <= x; i <<= 1) {
        ret += ((x / i) - (x / (i << 1))) * i;
    }
    return ret;
}

LL query2(LL x, LL n) {
    LL ret = 0;
    while (x <= n) {
        x += x & (-x);
        ret++;
    }
    return ret;
}

int main(void) {
    LL n, q, l, r;
    int op;
    while (~scanf("%lld%lld", &n, &q)) {
        while (q--) {
            scanf("%d", &op);
            if (op & 1) {
                scanf("%lld%lld", &l, &r);
                printf("%lld\n", query1(r) - query1(l - 1));
            } else {
                scanf("%lld", &l);
                printf("%lld\n", query2(l, n));
            }
        }
    }
    return 0;
}

相关阅读:

关于这个数列与此数列的前缀和:

lowbit数列:https://oeis.org/A006519

lowbit数列前缀和:https://oeis.org/A006520

【HDU-5973】Game of Taking Stones【威佐夫博弈】

【HDU-5973】Game of Taking Stones【威佐夫博弈】

Solution:

直接根据威佐夫博弈的定理,两堆数量之差乘上黄金分割比等于数量少的那堆的个数,先手必输,反之先手必胜。

求解黄金分割比使用公式\(\frac{\sqrt{5} – 1}{2}\),关于\(\sqrt{5}\)的求解,等价于求解函数\(f(x) = x^2 – 5\)与横坐标轴的正值交点的横坐标,显然\(\sqrt{5}\)就是上面所述问题的解,但是我们现在需要一个浮点数值,也就是一定精度下根号的浮点近似值,可以使用二分法(基于介值定理,我们知道如果在一个区间内有根,这个区间的左右端点函数值之积一定小于零),还可以使用牛顿迭代法,它的收敛速度会比二分法快,但是有时牛顿迭代法比二分法更容易出现不收敛的情况,不过对于当前函数是不存在这个问题的,因为我们确定要找的根在0到5的区间内,并且这个函数显然在这个区间内单调递增,因此选取初始值5可以确保函数值收敛到我们想要的位置上。

牛顿迭代法公式:\(x_n = x_{n – 1} – \frac{f(x_{n – 1})}{f'(x_{n – 1})}\)。

代码:

import java.util.Scanner;
import java.math.BigDecimal;

public class Main {
    private static final BigDecimal EPS = new BigDecimal("0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001");
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigDecimal sqrt5 = sqrtNewtownMethod("5");
        BigDecimal goldNum = sqrt5.add(BigDecimal.valueOf(1)).divide(BigDecimal.valueOf(2));
        while (in.hasNext()) {
            BigDecimal a = in.nextBigDecimal();
            BigDecimal b = in.nextBigDecimal();
            if (a.compareTo(b) > 0) {
                BigDecimal t = a;
                a = b;
                b = t;
            }
            BigDecimal c = b.subtract(a).multiply(goldNum);
            if (c.setScale(0, BigDecimal.ROUND_FLOOR).compareTo(a) == 0)
                System.out.println("0");
            else
                System.out.println("1");
        }
    }
    private static BigDecimal sqrtNewtownMethod(String b) {
        BigDecimal two = BigDecimal.valueOf(2);
        BigDecimal num = new BigDecimal(b);
        BigDecimal pre = new BigDecimal(b);
        BigDecimal crt = new BigDecimal("0");
        while (true) {
            // System.out.println(pre.subtract(pre.multiply(pre).subtract(num).divide(two.multiply(pre))));
            crt = pre.subtract(pre.multiply(pre).subtract(num).divide(two.multiply(pre), 102, BigDecimal.ROUND_FLOOR));
            if (crt.subtract(pre).abs().compareTo(EPS) < 0) break;
            pre = crt;
        }
        return crt;
    }
}

 

【HDU-5971】Wrestling Match【二分图+并查集+dfs】

【HDU-5971】Wrestling Match【二分图+并查集+dfs】

#include <iostream>
#include <stack>
#include <cstring>
#include <vector>

using namespace std;

const int LIM = 1e3 + 10;
int parent[LIM];
bool vis[LIM];
vector<int> good;
vector<int> bad;
vector<int> adj[LIM];

enum {NIL = -1, GOOD, BAD};

bool dfs(int crt) {
    stack<int> s;
    s.push(crt);
    while (!s.empty()) {
        crt = s.top();
        s.pop();
        if (vis[crt]) continue;
        vis[crt] = true;
        // cout << crt << " : " << parent[crt] << endl;
        for (int i = 0; i < adj[crt].size(); i++) {
            if (parent[adj[crt][i]] == NIL) {
                parent[adj[crt][i]] = parent[crt] ^ 1;
                s.push(adj[crt][i]);
            } else if (parent[crt] + parent[adj[crt][i]] != 1) {
                return false;
            }
        }
    }
    return true;
}

bool judge(int n) {
    // use pre-acknowledge give identities to some certain persons
    for (int i = 0; i < good.size(); i++) {
        if (parent[good[i]] == NIL) {
            parent[good[i]] = GOOD;
        } else if (parent[good[i]] == BAD) {
            return false;
        }
        if (vis[i]) continue;
        if (!dfs(good[i])) return false;
    }
    for (int i = 0; i < bad.size(); i++) {
        if (parent[bad[i]] == NIL) {
            parent[bad[i]] = BAD;
        } else if (parent[bad[i]] == GOOD) {
            return false;
        }
        if (vis[i]) continue;
        if (!dfs(bad[i])) return false;
    }
    // prejudge if there are some person never join in any matchs
    for (int i = 1; i <= n; i++)
        if (parent[i] == NIL && !adj[i].size())
            return false;
    // find if there are some person doesn't have identities
    int pos = NIL;
    for (int i = 1; i <= n; i++)
        if (parent[i] == NIL) {
            pos = i;
            break;
        }
    // if everyone have the identities
    if (pos == NIL) return true;
    // give identities to one of the person who doesn't have identity
    // and try to detect if there is the contradiction
    parent[pos] = GOOD;
    if (!dfs(pos)) return false;
    // if there are still some person doesn't have identities,
    // return false
    for (int i = 1; i <= n; i++)
        if (parent[i] == NIL)
            return false;
    return true;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, x, y;
    while (cin >> n >> m >> x >> y) {
        // init
        memset(vis, false, sizeof vis);
        memset(parent, NIL, sizeof parent);
        for (int i = 1; i <= n; i++)
            adj[i].clear();
        good.clear();
        bad.clear();
        // load the adjacent map
        int u, v;
        for (int i = 0; i < m; i++) {
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        // load the set
        for (int i = 0; i < x; i++) {
            cin >> u;
            good.push_back(u);
        }
        for (int i = 0; i < y; i++) {
            cin >> u;
            bad.push_back(u);
        }
        cout << (judge(n) ? "YES" : "NO") << "\n";
    }
    return 0;
}