## 【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://www.cnblogs.com/hsd-/p/5325780.html

https://oeis.org/A034893

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

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

Solution:

#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:

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");
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;

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++) {
} 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++) {
} else if (parent[bad[i]] == GOOD) {
return false;
}
if (vis[i]) continue;
}
// 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++)
good.clear();
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v;
}
for (int i = 0; i < x; i++) {
cin >> u;
good.push_back(u);
}
for (int i = 0; i < y; i++) {
cin >> u;