#include<bits/stdc++.h> usingnamespace std; #define ll long long constint INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; constint N = 2e5 + 10; ll Pow(ll a, ll b){ ll res = 1ll; while (b) { if (b & 1)res = res * a%mod; a = a * a%mod; b >>= 1; } return res; } int mu[N], p[N], tot; bool flg[N]; voidgetMu(int n){ mu[1] = 1; for (int i = 2; i <= n; ++i) { if (!flg[i]) p[++tot] = i, mu[i] = -1; for (int j = 1; j <= tot && i * p[j] <= n; ++j) { flg[i * p[j]] = 1; if (i % p[j] == 0) { mu[i * p[j]] = 0; break; } mu[i * p[j]] = -mu[i]; } } } int m; ll f[N]; vector<int>vc[N]; intcal(int i, int x){ int n = m / x, res = 0; i /= x; for (int d : vc[i]) { res += (n / d)*mu[d]; } res += n * mu[1] + (n / i)*mu[i]; return res; } intmain(){ scanf("%d", &m); getMu(m); for (int i = 2; i <= m; i++) { for (int j = 2; j*j <= i; j++) { if (i%j != 0)continue; vc[i].push_back(j); if (i / j != j)vc[i].push_back(i / j); } } f[1] = 0; for (int i = 2; i <= m; i++) { f[i] = m; for (int x : vc[i]) { f[i] = (f[i] + f[x] * cal(i, x) % mod) % mod; } f[i] = f[i] * Pow(m - m / i, mod - 2) % mod; } ll ans = 0; for (int i = 1; i <= m; i++)ans = (ans + f[i]) % mod; ans = ans * Pow(m, mod - 2) % mod; ans = (ans + 1) % mod; printf("%lld\n", ans); return0; }
E. Maximize Mex
题意:给定 n 个学生,m 个俱乐部, 1≤m≤n≤5000,每个学生有 p[i] 的潜力值,0≤pi<5000,且属于第 c[i] 个俱乐部,共有 d 天,每天开始前有一名学生永远离开,接着要从每个非空的俱乐部各选一名学生,当天的值等于当天所选学生集合的 MEX 值。要求每天的值都尽量大,输出每天的值。
二分图匹配
每个俱乐部选一个,所以想到二分图匹配,把 潜力值与俱乐部 作为两个点集,学生看作边。
直接每次删边再重新求复杂度不够。
要逆向求,从最后一天开始,每次加边,每次在旧图的基础上尝试插入更大的值以提高 MEX,也就是保证 MEX 值不会减小,所以最终 d 天下来就相当于求一次二分图匹配,复杂度 nm。
#include<bits/stdc++.h> usingnamespace std; #define ll long long constint INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; constint N = 4e5 + 10; int n, m; vector<int>vc; int p[N], s[N], b[N], inc[N], pref[N], ans[N]; structBIT { int sum[N], n; intlowbit(int x){ return x & -x; } voidadd(int p, int x){ for (int i = p; i <= n; i += lowbit(i))sum[i] += x; } intqry(int r){ int res = 0; for (int i = r; i > 0; i -= lowbit(i))res += sum[i]; return res; } }b1, b2; structX { int p, x, y, op, id; booloperator<(const X& b)const { return p == b.p ? id < b.id : p < b.p; } }; vector<X>vv; intmain(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)scanf("%d", &p[i]); for (int i = 1; i <= n; i++)scanf("%d", &s[i]); for (int i = 1; i <= n; i++)scanf("%d", &b[i]); for (int i = 1; i <= m; i++)scanf("%d", &inc[i]); for (int i = 1; i <= m; i++)scanf("%d", &pref[i]); for (int i = 1; i <= n; i++) { vc.push_back(b[i] - p[i] + 1); vc.push_back(b[i] + p[i]); } for (int i = 1; i <= m; i++) { vc.push_back(inc[i] + pref[i]); vc.push_back(pref[i] - inc[i]); } sort(vc.begin(), vc.end()); vc.erase(unique(vc.begin(), vc.end()), vc.end()); b1.n = b2.n = (int)vc.size(); for (int i = 1; i <= n; i++) { vv.push_back(X{ p[i],b[i],p[i],1,0 }); vv.push_back(X{ s[i] + 1,b[i],p[i],-1,0 }); } for (int i = 1; i <= m; i++) { vv.push_back(X{ inc[i],inc[i],pref[i],0,i }); } sort(vv.begin(), vv.end()); for (auto t : vv) { if (t.id) { int x = lower_bound(vc.begin(), vc.end(), t.x + t.y) - vc.begin() + 1; int y = lower_bound(vc.begin(), vc.end(), t.y - t.x) - vc.begin() + 1; ans[t.id] = b1.qry(x) + b2.qry(y); } else { int x = lower_bound(vc.begin(), vc.end(), t.x + t.y) - vc.begin() + 1; int y = lower_bound(vc.begin(), vc.end(), t.x - t.y + 1) - vc.begin() + 1; b1.add(x, t.op); b2.add(y, -t.op); } } for (int i = 1; i <= m; i++)printf("%d%s", ans[i], i == m ? "\n" : " "); return0; }