T1004 游戏(HDU 7460)
注意到对于两个人，他们 \(t\) 轮后能力值相同的概率只与他们初始时的能力差有关，所以我们先 \(\text{FFT}\) 求出 \(|a_i - a_j| = k\) 的 \((i, j)\) 对数。
构造多项式 \(F(x) = (p_1 x^2 + p_2 + p_3x)\)，其中 \(p_1, p_2, p_3\)，分别表示在一轮中两个人相对能力值变化为 \(+1/-1/0\) 的概率，这三个数容易用 \(n\) 表示，我们现在的任务是 \(\forall k \in [0, V)\)，求 \([x^{t + k}] F(x)^t\)。
令 \(G(x) = F(x)^t\)，考虑对 \(G\) 求导，我们有 \(G'(x) = t \times F'(x) \times F(x)^{t - 1} \iff G'(x) \times F(x) = t \times F'(x) \times G(x)\)，将 \(F\) 和 \(F'\) 展开可得 \(G'(x) \times (p_1 x^2 + p_2 + p_3x) = t \times (2p_1x + p_3) \times G(x)\)，取 \(G\) 的 \(i\) 次项系数即可得到 \(G\) 的系数的递推式。
时间复杂度 \(O(V \log V + t)\)。
Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <complex>
#include <cmath>
using namespace std;
using LL = long long;
using Cp = complex<double>;
const int N = 1e6 + 5, T = 2e7 + 5;
const int Mod = 998244353;
int power (int x, int y = Mod - 2) {
int res = 1;
while (y) {
if (y & 1) {
res = 1ll * res * x % Mod;
}
x = 1ll * x * x % Mod;
y >>= 1;
}
return res;
}
int m, t;
int inv[T], g[T];
LL a[N];
namespace FFT {
const double pi = acos(-1);
int len = 1;
vector<int> r;
void FFT (vector<Cp> &a, int v) {
for (int i = 0; i < len; ++i) {
if (i < r[i]) {
swap(a[i], a[r[i]]);
}
}
for (int i = 1; i < len; i <<= 1) {
for (int j = 0; j < len; j += (i << 1)) {
for (int k = 0; k < i; ++k) {
Cp p = a[j + k], q = Cp(cos(pi * k / i), sin(pi * k / i) * v) * a[j + k + i];
a[j + k] = p + q, a[j + k + i] = p - q;
}
}
}
}
vector<LL> convolution (vector<int> &a, vector<int> &b) {
int n = a.size() - 1, m = b.size() - 1;
for (; len <= n + m; len <<= 1) {
}
a.resize(len), b.resize(len), r.resize(len);
vector<Cp> A(len);
for (int i = 0; i < len; ++i) {
A[i] = Cp(a[i], b[i]);
r[i] = (r[i >> 1] >> 1) | (i & 1) * (len >> 1);
}
FFT(A, 1);
for (int i = 0; i < len; ++i) {
A[i] *= A[i];
}
FFT(A, -1);
vector<LL> res(n + m + 1);
for (int i = 0; i <= n + m; ++i) {
res[i] = LL(A[i].imag() / len / 2 + 0.5);
}
return res;
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
inv[1] = 1;
for (int i = 2; i < T; ++i) {
inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;
}
int tmpn;
cin >> tmpn >> t;
vector<int> arr(tmpn);
for (int i = 0; i < tmpn; ++i) {
cin >> arr[i];
m = max(m, arr[i]);
}
vector<int> c(m + 1);
for (auto x : arr) {
++c[x];
}
for (auto t : c) {
a[0] += 1ll * (t - 1) * t / 2;
}
vector<int> _c = c;
reverse(_c.begin(), _c.end());
vector<LL> z = FFT::convolution(c, _c);
for (int i = 1; i < m; ++i) {
a[i] += z[i + m];
}
--m;
int p1 = 2ll * (tmpn - 2) * inv[tmpn] % Mod * inv[tmpn - 1] % Mod, p2 = p1, p3 = (1 - p1 * 2 + Mod * 2) % Mod;
int p1i = 1ll * power(p1) * (Mod - 1) % Mod;
g[t * 2] = power(p1, t);
if (t) g[t * 2 - 1] = 1ll * power(p1, t - 1) * p3 % Mod * t % Mod;
for (int i = t * 2 - 1; i >= t; --i) {
g[i - 1] = ((1ll * (t - i + Mod) * p3 % Mod * g[i] - 1ll * (i + 1) * p2 % Mod * g[i + 1] + 1ll * Mod * Mod) % Mod) * inv[t * 2 + 1 - i] % Mod * p1i % Mod;
}
int ans = 0;
for (int i = 0; i <= min(t, m); ++i) {
ans = (ans + 1ll * g[i + t] * (a[i] % Mod)) % Mod;
}
cout << ans << '\n';
return 0;
}
T1005 数论(HDU 7461)
考虑固定一个端点向左/右扫，可以得到 \(O(\log n)\) 个 \(\gcd\) 相同的段（\(\gcd\) 每次变化至少减半），每段形如 \((g, l, r, t)\)，表示一个端点为 \(t\)，另一个端点在 \([l, r]\) 中，这样构成的区间都满足 \(\gcd = g\)，总段数 \(O(n \log n)\)，找段考虑二分 + ST 表，时间复杂度 \(O(n \log^2 n)\)。
对答案进行容斥，算出总方案数和不包含 \(i\) 的方案数，不包含一个数又可以拆成一段前缀和一段后缀任选，所以我们只需对前缀和后缀分别做 \(\text{dp}\) 即可。
对于前缀而言，我们枚举 \(\gcd\) 然后分别算贡献，对于某个 \(\gcd = g\) 有若干段 \((l, r, t)\)，我们按 \(t\) 排序，设 \(f_i\) 表示在 \([1, i]\) 中选若干满足 \(\gcd = g\) 的不交区间，最后一个区间右端点为 \(i\) 的方案数，转移方程是 \(f_t = \sum\limits_{i = l}^{r} \sum\limits_{j = 0}^{i - 1} f_j\)。考虑一个 \(f_j\) 的贡献，对于 \(j < l\)，\(f_j\) 系数为 \(r - l + 1\)，对于 \(j \in [l, r]\)，\(f_j\) 系数构成公差为 \(-1\)，末项为 \(0\) 的等差数列。相当于单点修改，区间和，区间等差数列加权和，线段树容易维护。
后缀类似，设 \(g_i\) 表示在 \([i, n]\) 中选若干满足 \(\gcd = g\) 的不交区间，第一个区间以 \(i\) 为左端点的方案数，再开一棵线段树维护即可。
时间复杂度 \(O(n \log^2 n)\)。
Code
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <chrono>
#include <cassert>
#define lc (k << 1)
#define rc ((k << 1) | 1)
using namespace std;
using LL = long long;
using uLL = unsigned long long;
uLL Get_time () { return chrono::steady_clock::now().time_since_epoch().count(); }
const int N = 1e5 + 5, M = 17;
const int Mod = 998244353;
int n, allsum;
int a[N], st[N][M], diff[N];
struct Tr {
int l, r, t;
};
namespace Pre_Seg {
const int T = N * 4;
struct Tree {
int sum[T], rsum[T], len[T];
void Build (int k, int L = 0, int R = n) {
len[k] = R - L + 1;
if (L == R) return;
int mid = (L + R) >> 1;
Build(lc, L, mid);
Build(rc, mid + 1, R);
}
void Modify (int k, int x, int y, int L = 0, int R = n) {
if (L == R) {
sum[k] = y;
return;
}
int mid = (L + R) >> 1;
if (x <= mid) {
Modify(lc, x, y, L, mid);
}
else {
Modify(rc, x, y, mid + 1, R);
}
sum[k] = (sum[lc] + sum[rc]) % Mod;
rsum[k] = (rsum[lc] + rsum[rc] + 1ll * sum[lc] * len[rc]) % Mod;
}
LL Query_sum (int k, int l, int r, int L = 0, int R = n) {
if (l > r) return 0;
if (l <= L && r >= R) {
return sum[k];
}
int mid = (L + R) >> 1;
LL res = 0;
if (l <= mid) {
res = (res + Query_sum(lc, l, r, L, mid));
}
if (r > mid) {
res = (res + Query_sum(rc, l, r, mid + 1, R));
}
return res;
}
LL Query_rsum (int k, int l, int r, int L = 0, int R = n) {
if (l <= L && r >= R) {
return (rsum[k] + 1ll * (r - R) * sum[k]) % Mod;
}
int mid = (L + R) >> 1;
LL res = 0;
if (l <= mid) {
res = (res + Query_rsum(lc, l, r, L, mid));
}
if (r > mid) {
res = (res + Query_rsum(rc, l, r, mid + 1, R));
}
return res;
}
};
}
namespace Suf_Seg {
const int T = N * 4;
struct Tree {
int sum[T], rsum[T], len[T];
void Build (int k, int L = 1, int R = n + 1) {
len[k] = R - L + 1;
if (L == R) return;
int mid = (L + R) >> 1;
Build(lc, L, mid);
Build(rc, mid + 1, R);
}
void Modify (int k, int x, int y, int L = 1, int R = n + 1) {
if (L == R) {
sum[k] = y;
return;
}
int mid = (L + R) >> 1;
if (x <= mid) {
Modify(lc, x, y, L, mid);
}
else {
Modify(rc, x, y, mid + 1, R);
}
sum[k] = (sum[lc] + sum[rc]) % Mod;
rsum[k] = (rsum[lc] + rsum[rc] + 1ll * len[lc] * sum[rc]) % Mod;
}
LL Query_sum (int k, int l, int r, int L = 1, int R = n + 1) {
if (l > r) return 0;
if (l <= L && r >= R) {
return sum[k];
}
int mid = (L + R) >> 1;
LL res = 0;
if (l <= mid) {
res = (res + Query_sum(lc, l, r, L, mid));
}
if (r > mid) {
res = (res + Query_sum(rc, l, r, mid + 1, R));
}
return res;
}
LL Query_rsum (int k, int l, int r, int L = 1, int R = n + 1) {
if (l <= L && r >= R) {
return (rsum[k] + 1ll * (L - l) * sum[k]) % Mod;
}
int mid = (L + R) >> 1;
LL res = 0;
if (l <= mid) {
res = (res + Query_rsum(lc, l, r, L, mid));
}
if (r > mid) {
res = (res + Query_rsum(rc, l, r, mid + 1, R));
}
return res;
}
};
}
Pre_Seg::Tree pret;
Suf_Seg::Tree suft;
signed main () {
// freopen("tmp.in", "r", stdin);
// freopen("1005.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
uLL st0 = Get_time();
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
pret.Build(1), pret.Modify(1, 0, 1);
suft.Build(1), suft.Modify(1, n + 1, 1);
for (int i = 1; i <= n; ++i) {
st[i][0] = a[i];
}
for (int k = 1; k < M; ++k) {
for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
st[i][k] = __gcd(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}
}
auto Query = [&](int l, int r) -> int {
int k = log2(r - l + 1);
return __gcd(st[l][k], st[r - (1 << k) + 1][k]);
};
map<int, vector<Tr>> mpre;
map<int, vector<Tr>> msuf;
for (int i = 1; i <= n; ++i) {
for (int p = i, l = 1, r = p; p; p = l - 1, l = 1, r = p) {
int g = Query(p, i);
while (l <= r) {
int mid = (l + r) >> 1;
if (Query(mid, i) == g) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
auto it = mpre.find(g);
if (it == mpre.end()) {
mpre.insert({g, vector<Tr>{{l, p, i}}});
}
else {
it->second.push_back({l, p, i});
}
}
for (int p = i, l = p, r = n; p <= n; p = r + 1, l = p, r = n) {
int g = Query(i, p);
while (l <= r) {
int mid = (l + r) >> 1;
if (Query(i, mid) == g) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
auto it = msuf.find(g);
if (it == msuf.end()) {
msuf.insert({g, vector<Tr>{{p, r, i}}});
}
else {
it->second.push_back({p, r, i});
}
}
}
for (auto ipre = mpre.begin(), isuf = msuf.begin(); ipre != mpre.end(); ++ipre, ++isuf) {
assert(ipre->first == isuf->first);
vector<Tr> vp = ipre->second, sp = isuf->second;
sort(vp.begin(), vp.end(), [&](Tr i, Tr j) -> bool {
return i.t < j.t;
});
sort(sp.begin(), sp.end(), [&](Tr i, Tr j) -> bool {
return i.t > j.t;
});
vector<int> dpoint;
for (auto i : vp) {
dpoint.push_back(i.t);
int f = (pret.Query_sum(1, 0, i.l - 1) % Mod * (i.r - i.l + 1) + pret.Query_rsum(1, i.l, i.r)) % Mod;
pret.Modify(1, i.t, f);
allsum = (allsum + f) % Mod;
}
for (auto i : sp) {
dpoint.push_back(i.t);
int f = (suft.Query_sum(1, i.r + 1, n + 1) % Mod * (i.r - i.l + 1) + suft.Query_rsum(1, i.l, i.r)) % Mod;
suft.Modify(1, i.t, f);
}
sort(dpoint.begin(), dpoint.end());
dpoint.resize(unique(dpoint.begin(), dpoint.end()) - dpoint.begin());
int la = 0;
auto Range_add = [&](int l, int r) -> void {
if (l > r) return;
int x = ((pret.Query_sum(1, 1, l - 1) % Mod + 1) * (suft.Query_sum(1, l + 1, n) % Mod + 1) % Mod - 1 + Mod) % Mod;
diff[l] = (diff[l] + x) % Mod;
diff[r + 1] = (diff[r + 1] - x + Mod) % Mod;
};
for (auto i : dpoint) {
Range_add(la + 1, i - 1);
Range_add(i, i);
la = i;
}
Range_add(la + 1, n);
for (auto i : vp) {
pret.Modify(1, i.t, 0);
}
for (auto i : sp) {
suft.Modify(1, i.t, 0);
}
}
for (int i = 1; i <= n; ++i) {
diff[i] = (diff[i] + diff[i - 1]) % Mod;
}
for (int i = 1; i <= n; ++i) {
cout << (allsum - diff[i] + Mod) % Mod << ' ';
}
cout << '\n';
uLL ed0 = Get_time();
// cerr << "Time = " << (ed0 - st0) / int(1e6) << '\n';
return 0;
}
T1006 字符串(HDU 7462)
不会。
T1009 圣芙蕾雅(HDU 7465)
不会。
T1010 绘世之卷(HDU 7466)
首先带删除肯定是不好做的，考虑线段树分治一下，变成插入和撤销，这样我们只需在加入一个数时，算它和其他数的贡献。
根号分治，令 \(d = \lfloor \sqrt n \rfloor\)。注意到当集合大小 \(|S| > d\) 时，答案 \(\le d\)，证明：容易说明一定存在一对 \((x, y)\) 满足 \(1 \le y - x \le d\)，如果 \(x \le d\) 那么用 \(x\) 做被除数，否则用 \(y\) 做被除数即可。
当 \(|S| \le d\) 时直接暴力和每个元素匹配算贡献。当 \(|S| > d\) 时，分类讨论，假设当前加入的是 \(x\)。
- 若 \(ky + r = x \iff ky = x - r\)，枚举 \(r\)，在插入 \(y\) 时预处理 \(k \in [0, d]\) 即可。
- 若 \(kx + r = y\)，枚举 \(k\)，只需找到 \(kx\) 的前驱，插入一个数 \(y\) 时修改 \([y, y + d]\) 的前驱即可。
两种修改操作都方便撤销。
时间复杂度 \(O(n \sqrt n \log n)\)。
Code
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;
#define lc (k << 1)
#define rc ((k << 1) | 1)
const int N = 5e4 + 5, Inf = 1e9, T = N * 4;
const int S = 1e6;
int n, d, q, cur, ans[N], pre[N], mik[N];
vector<int> vec[T];
set<int> st;
int len1, len2;
pair<int, int> stpre[S], stmik[S];
void Add (int k, int l, int r, int x, int L = 1, int R = q) {
if (l <= L && r >= R) {
vec[k].push_back(x);
return;
}
int mid = (L + R) >> 1;
if (l <= mid) {
Add(lc, l, r, x, L, mid);
}
if (r > mid) {
Add(rc, l, r, x, mid + 1, R);
}
}
void Solve (int k, int L = 1, int R = q) {
int lst = cur, tmp1 = len1, tmp2 = len2;
for (auto x : vec[k]) {
if (st.size() >= d) {
for (int r = 0; r <= d && x - r; ++r) {
cur = min(cur, mik[x - r] + r);
}
for (int k = 0; k <= d && x * k <= n; ++k) {
cur = min(cur, x * k - pre[x * k] + k);
}
}
else {
for (auto y : st) {
cur = min(cur, min(x / y + x % y, y / x + y % x));
}
}
st.insert(x);
for (int k = 0; k <= d && x * k <= n; ++k) {
if (k < mik[x * k]) {
stmik[++len1] = {x * k, mik[x * k]};
mik[x * k] = k;
}
}
for (int i = x; i <= min(n, x + d); ++i) {
if (x > pre[i]) {
stpre[++len2] = {i, pre[i]};
pre[i] = x;
}
else {
break;
}
}
}
if (L == R)
ans[L] = cur;
else {
int mid = (L + R) >> 1;
Solve(lc, L, mid);
Solve(rc, mid + 1, R);
}
cur = lst;
for (auto x : vec[k])
st.erase(x);
for (; len1 > tmp1; --len1)
mik[stmik[len1].first] = stmik[len1].second;
for (; len2 > tmp2; --len2)
pre[stpre[len2].first] = stpre[len2].second;
}
int main () {
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while (T--) {
cin >> n >> q, d = sqrt(n);
vector<int> occ(n + 1, -1);
fill(vec + 1, vec + q * 4 + 1, vector<int>());
for (int o, x, i = 1; i <= q; ++i) {
cin >> o >> x;
if (o == 0) {
Add(1, occ[x], i - 1, x);
occ[x] = -1;
}
else {
occ[x] = i;
}
}
for (int i = 1; i <= n; ++i) {
if (occ[i] != -1) {
Add(1, occ[i], q, i);
}
}
fill(mik + 1, mik + n + 1, Inf);
fill(pre, pre + n + 1, -Inf);
cur = N, Solve(1);
for (int i = 1; i <= q; ++i) {
cout << (ans[i] == N ? -1 : ans[i]) << '\n';
}
}
return 0;
}