困难
B. beauty（拆贡献）
http://222.180.160.110:61235/contest/6513/problem/2
给定 \(n,V\)，求出对于所有长度为 \(n\)，值域为 \([1,V]\) 的序列 \(a_{1\sim n}\)，\(\sum_{i=1}^n |a_i-a_{n-i+1}|\) 的和。
\(n,V\le 5000\)。
- 容易想到算贡献，会有一个 \(O(n^2V)\) 的做法。但是想 \(O(nV)\) 做是很抽象的，和 \(O(n^2V)\) 的思路已经很不一样了
- 经典 trick，\(a_{i+n/2}-a_i=\sum\limits_{x=0}^{+\infty} [a_i\le x<a_{i+n/2}]\) 拆贡献 。故要算 \(a_{i}-a_{i+n/2}\)，只需要对于每个 \(x\in[a_i,a_{i+n/2})\) 计算贡献。
- 枚举 \(x\in [1,V)\)，再枚举最大的 \(t\)，满足 \(a_t\ge x\)。那么有 \(t\) 个 \(a_i\le x\)，同时有 \(n-t\) 个 \(a_i>x\)；满足 \(i\le n/2\) 的 \(a_{i},a_{i+n/2}\) 对数应该是 \(\min(t,n-t)\)。故对于一个确定的序列，\(x\) 共有 \(\min(t,n-t)\) 的贡献。
- 考虑计数满足 \(a_t\le x\) 的 \(a\)，这要求第 \(t\) 大的数 \(\le x\) 而第 \(t+1\) 大的数 \(>x\)，也即在 \([1,x]\) 里找 \(t\) 个数再在 \((x,V]\) 里找 \(n-t\) 个数，注意还要再乘上这两种数拼起来的方案数。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("beauty.in", "r", stdin);
std::freopen("beauty.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
std::vector<long long> fac(5001), inv(5001);
std::vector<std::vector<long long> > pw(5001, std::vector<long long> (5001));
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= 5000; ++i) {
fac[i] = fac[i - 1] * i % mod;
pw[i][0] = 1ll;
for (int j = 1; j <= 5000; ++j)
pw[i][j] = pw[i][j - 1] * i % mod;
}
auto qkp = [](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[5000] = qkp(fac[5000], mod - 2);
for (int i = 4999; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[m] % mod * inv[n - m] % mod;
};
for (std::cin >> T; T--; ) {
int n, V;
std::cin >> n >> V;
auto res(0ll);
for (int x = 1; x < V; ++x)
for (int t = 1; t < n; ++t) {
int k = std::min(t, n - t);
(res += k * pw[x][t] % mod * pw[V - x][n - t] % mod * C(n, t) % mod) %= mod;
}
std::cout << res * 2 % mod << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C. Drink Bar（容斥 + 偏序）
https://www.luogu.com.cn/problem/AT_snuke21_j
- 三个属性都是排列，可以推理出只要两个三元组中，作出贡献的元素不完全相同，两个三元组就不同。讨论作出贡献的元素数量。
- 只有一个元素作出贡献，答案为 \(n\)。
- 有两个元素作出贡献，任选的话答案为 \(C_n^2\)，要减去一个元素严格优于另一个元素的情况，三维偏序即可。
有三个元素作出贡献，是个有点复杂的容斥，不妨设三元组为 \((i,j,k)\)，其中贡献次数最多的为 \(i\)
- \(i\) 贡献了 \(\ge 1\) 次，方案数为 \(C_n^3\)
- \(i\) 贡献了 \(\ge 2\) 次，枚举作出两次贡献的属性，以 \(a,b\) 为例，那么有 \(a_j,a_k<a_i\)，以及 \(b_j,b_k<b_i\)，二维偏序即可
- \(i\) 贡献了 \(\ge 3\) 次，依然是三维偏序，可以用『两个元素做出贡献』中 cdq 得到的值算出答案。记得乘 2，因为被多减了 2 次。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
struct node { int a, b, c, res; };
std::vector<node> a(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i].a >> a[i].b >> a[i].c;
a[i].res = 0;
}
long long res = n;
res += (long long)n * (n - 1) / 2;
std::vector<int> bit(n + 1);
auto lowbit = [](int x) {
return x & -x;
};
auto add = [&](int x, int v) {
for (; x <= n; x += lowbit(x))
bit[x] += v;
return;
};
auto ask = [&](int x) {
int res = 0;
for (; x; x -= lowbit(x))
res += bit[x];
return res;
};
std::function<void(int, int)> calc = [&](int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1;
calc(l, mid), calc(mid + 1, r);
int j = l;
for (int i = mid + 1; i <= r; ++i) {
for (; j <= mid && a[j].b < a[i].b; ++j)
add(a[j].c, 1);
a[i].res += ask(a[i].c);
}
for (int i = l; i < j; ++i)
add(a[i].c, -1);
std::inplace_merge(a.begin() + l, a.begin() + mid + 1, a.begin() + r + 1, [&](node x, node y) { return x.b < y.b; });
return;
};
std::sort(a.begin() + 1, a.end(), [&](node x, node y) { return x.a < y.a; });
calc(1, n);
for (int i = 1; i <= n; ++i)
res -= a[i].res;
res += (long long)n * (n - 1) * (n - 2) / 6;
for (int k = 0; k < 3; ++k) {
std::sort(a.begin() + 1, a.end(), [&](node x, node y) { return x.a < y.a; });
std::fill(bit.begin() + 1, bit.end(), 0);
for (int i = 1; i <= n; ++i) {
int t = ask(a[i].b);
res -= (long long)t * (t - 1) / 2;
add(a[i].b, 1);
std::tie(a[i].a, a[i].b, a[i].c) = std::make_tuple(a[i].b, a[i].c, a[i].a);
}
}
for (int i = 1; i <= n; ++i)
res += (long long)a[i].res * (a[i].res - 1);
std::cout << res << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C. 星白 by TTpandaS（笛卡尔树 + dsu on tree）
C. isn
最后一个删去的一定是连接
令 \(f_{i,j,0/1}\) 表示最后一个元素为 \(i\)，序列长为 \(j\)，最后一个被删去的数（未）被确定的方案数。注意确定最后一个被删去的数要在转移过程中进行，而不是作为一个 DP 节点，很容易发现后者是错的。>的数，可以 DP 还剩一个数没删时可能的序列。优化的思路就不一样了。因为要乘上 \((n-j)!\)，所以 \(j\) 的这一维是省不掉的
考虑不管最后一个被删掉的数，直接令 \(f_{i,j}\) 表示最后一个元素为 \(i\)，序列长为 \(j\) 的方案数。有 \(f_{i,j}=\sum\limits_{a_k\le a_i}f_{k,j - 1}\)，可以 DS 优化。但这样会产生不合法的情况。考察什么样的序列合法，发现删去的最后一个数一定是非法的，也就是包含之的序列都是非法的；反之易得被合法序列包含的序列都非法
明白了这一点过后就会知道长度为 \(j\) 的合法序列系数都为 \((n-j)!\)
故容斥，令 \(g_i\) 表示序列长为 \(i\) 的方案数，\(h_i\) 表示序列长为 \(i\) 的合法方案数。从异或角度考虑，易得 \(h_i=g_i-\sum\limits_{j=i+1}h_j\times (j-i)!\times C_j^i\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("isn.in", "r", stdin);
std::freopen("isn.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1), l(1);
std::vector<long long> fac(n + 1), inv(n + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i], l.push_back(a[i]);
fac[i] = fac[i - 1] * i % mod;
}
auto qkp = [](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[m] % mod * inv[n - m] % mod;
};
std::sort(l.begin(), l.end());
l.erase(std::unique(l.begin(), l.end()), l.end());
for (int i = 0; i <= n; ++i)
a[i] = std::lower_bound(l.begin(), l.end(), a[i]) - l.begin() + 1;
int m = (int)l.size();
std::vector<std::vector<long long> > bit(n + 1, std::vector<long long> (m + 1));
auto lowbit = [](int x) {
return x & -x;
};
auto add = [&](int id, int x, long long v) {
for (; x <= m; x += lowbit(x))
(bit[id][x] += v) %= mod;
return;
};
auto ask = [&](int id, int x) {
auto res(0ll);
for (; x; x -= lowbit(x))
(res += bit[id][x]) %= mod;
return res;
};
std::vector<long long> g(n + 1), h(n + 1);
std::vector<std::vector<long long> > f(n + 1, std::vector<long long> (n + 1));
add(0, a[0], 1ll), f[0][0] = 1ll;
for (int i = 1; i <= n; ++i)
for (int j = n; j; --j) {
f[i][j] = ask(j - 1, a[i]);
add(j, a[i], f[i][j]);
(g[j] += f[i][j] * fac[n - j]) %= mod;
}
auto res(0ll);
for (int i = n; i; --i) {
h[i] = g[i];
for (int j = i + 1; j <= n; ++j)
(h[i] += mod - h[j] * fac[j - i] % mod * C(j, i) % mod) %= mod;
(res += h[i]) %= mod;
}
std::cout << res << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}D. ThePowers
TopCoder - 12185，原题交不了故不放链接了
http://222.180.160.110:61235/contest/6522/problem/4
给定 \(A,B\)，对于所有 \(X\le A,Y\le B\)，求 \(X^Y\) 的可能取值数量。\(A,B\le10^9\)。
- 考虑什么时候算重。发现当且仅当 \(x^a=y^b\)，此时记 \(a'=a\div\gcd(a,b),b'=b\div \gcd(a,b)\)，那么 \(t=\sqrt[a']x=\sqrt[b']y\) 为整（写成质因数乘积是易证的），则 \(x=t^b,y=t^a\)，是同一个数的不同次幂
故把 \(A\) 内所有数分组，记 \(S_x\) 表示所有 \(x\) 的次幂，其中 \(x\) 不是其他数的次幂
发现一个对于 \(>\sqrt A\) 的数 \(y\)，只有可能属于 \(S_y\)，或一个 \(x\le \sqrt A\) 的 \(S_x\)。每组最多有 \(30\) 个，故扫一遍 \(\le\sqrt A\) 的数即可完成分组。这样就只用考虑同组内的计数。即对于 \(x\) 和 \(p\le |S_x|,y\le B\)，\(x^{py}\) 有多少种取值，也即 \(py\) 有多少种取值
发现因为值域是连续的，对于一个 \(p\)，只要 \(pB\) 范围内某个数是 \(p\) 的倍数就可以取到，枚举 \([(p-1)B+1,pB]\)，对于每个 \(p\) 容斥，就需要计算 \(p\sim |S_x|\) 的每个子集，复杂度会爆炸。对于 \(x,y\in[p,|S_x|]\)，如果 \(y\) 是 \(x\) 的倍数，就可以 skip，只在剩下的元素里枚举子集，可以代码验证一下 \(30\) 以内最多剩下 \(15\) 个数，可以接受，注意子集信息类似高维前缀和地 \(O(1)\) 求就行了
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("power.in", "r", stdin);
std::freopen("power.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
long long A, B, mx = 1ll;
std::cin >> A >> B;
if (A == 1) {
std::cout << 1 << '\n';
return 0;
}
int cnt = 1;
long long res = 1ll;
for (; (mx + 1) * (mx + 1) <= A; ++mx);
std::vector<int> tag(mx + 1);
for (int i = 2; i <= mx; ++i)
if (!tag[i]) {
int siz = 1;
for (long long j = i; j <= A; j *= i, ++siz)
if (j <= mx)
tag[j] = 1;
cnt += --siz;
for (int j = 1; j <= siz; ++j) {
std::vector<int> p({ j });
for (int k = j + 1; k <= siz; ++k) {
bool flag = 1;
for (auto l : p)
if (k % l == 0) {
flag = 0;
break;
}
if (flag)
p.push_back(k);
}
int m = (int)p.size(), s = 1 << m;
std::vector<long long> mul(s);
mul[0] = 1ll;
auto lcm = [&](long long x, long long y) {
return x / std::__gcd(x, y) * y;
};
for (int k = 1; k < s; ++k) {
mul[k] = lcm(p[std::__lg(k ^ ((k - 1) & k))], mul[(k - 1) & k]);
if (__builtin_popcount(k) & 1)
res += j * B / mul[k] - (j - 1) * B / mul[k];
else
res -= j * B / mul[k] - (j - 1) * B / mul[k];
}
}
}
res += (A - cnt) * B;
std::cout << res << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}搜索做法本质上是一样的，就不赘述了