[LibreOJ 2185][SDOI2015]约数个数和
首先我们有这样一个式子：
\[d(ij) = \sum_{a | i}\sum_{b | j} [\gcd(\frac{i}{a}, b) = 1]\]
怎样理解这一结论呢？我们知道\(ij\)的约数\(d\)一定可以被分解为\(ab\)使得\(a | i, b | j\)，但这种划分可能会非常的多，我们要保证每个约数\(d\)只有一种划分被统计过。
那么考虑上述划分方法。对于\(i\)和\(j\)中一个有一个没有的质因子，是一定会划分到\(a\)和\(b\)中固定的一个的。那么考虑一个在\(i\)和\(j\)中都出现的质因子\(p\)，假设\(p\)在\(d\)中出现的次数超过了\(i\)和\(j\)中任何一个的话，那么\(p\)在\(a\)中一定会尽可能多的出现（否则\(\frac{i}{a}\)中会出现\(p\)，而这样无论如何一定有\(p | b\)，因此会不满足\(\gcd(\frac{i}{a}, b) = 1\)）。如果没超过呢？那么一定会全部划分到\(a\)中（其他情况下有\(p | b\)并且会出现\(p | \frac{i}{a}\)）。
下面考虑应用这个结论（为了方便，使用等价的\(d(ij) = \sum_{a | i}\sum_{b | j} [\gcd(a, b) = 1]\)，假设\(n\le m\)）：
\[
\begin{aligned}
\quad&\sum_{i = 1}^n\sum_{j = 1}^m \sum_{a | i}\sum_{b | j}\sum_{d | i, d | j}\mu(d)\\
=&\sum_{d = 1}^n\mu(d)\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{ad}\rfloor\sum_{b = 1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{bd}\rfloor\\
=&\sum_{d = 1}^n\mu(d)\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor}d(a)\sum_{b = 1}^{\lfloor\frac{m}{d}\rfloor}d(b)
\end{aligned}
\]
后面两个和式可以随便\(O(n)\)欲处理一下（然后我当初写了个\(O(n\sqrt{n})\)的神必预处理……），然后这个题做完力，，，
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
typedef long long int_t;
const int maxn = 50005;
int_t miu[maxn], miu_s[maxn], f[maxn];
void process() {
static bool vis[maxn];
static int prm[maxn]; int cnt = 0;
const int N = 50000;
miu[1] = 1LL;
for(int i = 2; i <= N; i ++) {
if(!vis[i]) {
miu[i] = -1LL; prm[cnt ++] = i;
}
for(int j = 0; j < cnt && prm[j] * i <= N; j ++) {
int v = prm[j] * i;
vis[v] = true;
if(i % prm[j] == 0) {
miu[v] = 0; break;
} else {
miu[v] = miu[i] * -1;
}
}
}
for(int i = 1; i <= N; i ++) {
miu_s[i] = miu_s[i - 1] + miu[i];
}
for(int i = 1; i <= N; i ++) {
for(int j = 1; j <= i;) {
int nx = i / (i / j);
f[i] += (int_t(nx - j + 1)) * (int_t(i / j));
j = nx + 1;
}
}
}
int_t solve(int n, int m) {
int_t ans = 0;
for(int i = 1; i <= std::min(n, m);) {
int nx = std::min(m / (m / i), n / (n / i));
ans += (miu_s[nx] - miu_s[i - 1]) * f[m / i] * f[n / i];
i = nx + 1;
}
return ans;
}
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
process(); int T;
scanf("%d", &T);
while(T --) {
int n, m; scanf("%d%d", &n, &m);
printf(LO, solve(n, m)); puts("");
}
return 0;
}
[LibreOJ 2182][SDOI2015]寻宝游戏
很多人说事动态虚树……其实也不算是吧，虽然这个东西用力虚树的思路惹。
第一个想到的思路……就事动态的维护虚树，然后虚树上所有边的长度乘二就事答案。然后我们考虑一点……虚树求的时候需要对DFS序（严格来说事欧拉序）排序，所以我们大致可以认为，虚树上做欧拉回路的本质就事按照DFS序扫描，换言之就事DFS一遍，然后进入和回溯事都把边记录到答案里，这个值也就事虚树上按DFS序排序之后两两相邻点的距离的和（首尾也要额外算一遍）。
然后这样一来，我们发现虚树上的非关键点就可以删掉了。因为非关键点也就是所有两两在DFS序中相邻的关键点的LCA，然后那两个关键点的距离也就等于他们到这个非关键点的距离的和。因此我们不需要维护非关键点，问题就简单了许多……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
const int maxn = 100005;
using ll = long long;
using pii = std::pair<int, ll>;
std::vector<pii> G[maxn];
void add_edge(int u, int v, ll w) {
G[u].push_back(pii(v, w));
}
void ins_edge(int u, int v, ll w) {
add_edge(u, v, w); add_edge(v, u, w);
}
int anc[maxn][17];
int dep[maxn], dfn[maxn]; ll dis[maxn];
int dcnt = 0;
void dfs(int x, int fa = -1) {
anc[x][0] = fa; dfn[x] = ++ dcnt;
for(auto &e : G[x]) {
int v = e.first; ll w = e.second;
if(v != fa) {
dep[v] = dep[x] + 1;
dis[v] = dis[x] + w;
dfs(v, x);
}
}
}
int n;
void process() {
memset(anc, -1, sizeof(anc)); dfs(1);
for(int j = 1; (1 << j) < n; j ++) {
for(int i = 1; i <= n; i ++) {
int a = anc[i][j - 1];
if(a != -1) {
anc[i][j] = anc[a][j - 1];
}
}
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) std::swap(u, v);
for(int j = 16; j >= 0; j --) {
int a = anc[u][j];
if(a != -1 && dep[a] >= dep[v]) {
u = a;
}
}
if(u == v) return u;
for(int j = 16; j >= 0; j --) {
int a1 = anc[u][j], a2 = anc[v][j];
if(a1 != -1 && a2 != -1 && a1 != a2) {
u = a1; v = a2;
}
}
return anc[u][0];
}
ll calc_dist(int u, int v) {
return dis[u] + dis[v] - 2LL * dis[lca(u, v)];
}
// template <typename T>
struct Comp {
bool operator ()(const int &a, const int &b) const {
return dfn[a] < dfn[b];
}
};
ll now = 0LL; std::set<int, Comp> S;
bool sta[maxn];
void add(int p) {
auto suc = S.upper_bound(p);
if(suc != S.begin()) {
auto pre = -- suc; ++ suc;
now += calc_dist(*pre, p);
if(suc != S.end()) {
now -= calc_dist(*pre, *suc);
}
}
if(suc != S.end()) {
now += calc_dist(*suc, p);
}
S.insert(p);
}
void del(int p) {
auto suc = S.upper_bound(p);
if(suc != S.end()) {
now -= calc_dist(*suc, p);
}
if((*S.begin()) != p) {
-- suc; -- suc;
int prev = *suc;
now -= calc_dist(prev, p);
++ suc; ++ suc;
if(suc != S.end()) {
now += calc_dist(prev, *suc);
}
}
S.erase(p);
}
ll query() {
if(S.size() <= 1) return 0LL;
ll ret = now;
auto las = S.end(); -- las;
ret += calc_dist(*S.begin(), *las);
return ret;
}
int main() {
int m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n - 1; i ++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
ins_edge(u, v, w);
}
process();
while(m --) {
int x; scanf("%d", &x);
if(sta[x]) {
del(x);
} else {
add(x);
}
sta[x] = !sta[x];
printf("%lld\n", query());
}
return 0;
}
[LibreOJ 2562][SDOI2018]战略游戏
aji圆方树毁我青春，，，省选现场看出来是圆方树但写不出点双滚粗。
显然可以割的点是某两个点的某一条简单路径上的割点，然后两点间的简单路劲的并就是圆方树上的路径，割点在圆方树上就是非叶子的圆点。我们求所有两点路径的并，就需要虚树。
然后做完了……直接建圆方树，每次询问建虚树xjb统计即可。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
const int maxn = 100005;
const int maxm = 200005;
std::vector<int> G[maxn];
void cz1() {
for(int i = 0; i < maxn; i ++) {
G[i].clear();
}
}
void add_edge1(int u, int v) {
G[u].push_back(v); G[v].push_back(u);
}
using pii = std::pair<int, int>;
int dcnt, bcc_cnt; int pre[maxn]; bool iscut[maxn];
int bccno[maxn]; std::vector<int> bcc[maxm];
int dfs(int x, int fa = -1) {
static std::stack<pii> S;
pre[x] = ++ dcnt; int low = pre[x];
int cld = 0;
for(auto v : G[x]) {
pii e = std::make_pair(x, v);
if(!pre[v]) {
S.push(e); cld ++;
int lowv = dfs(v, x);
low = std::min(low, lowv);
if(lowv >= pre[x]) {
iscut[x] = true; bcc_cnt ++;
bcc[bcc_cnt].clear();
while(true) {
pii ee = S.top(); S.pop();
int f = ee.first, g = ee.second;
if(bccno[f] != bcc_cnt) {
bccno[f] = bcc_cnt;
bcc[bcc_cnt].push_back(f);
}
if(bccno[g] != bcc_cnt) {
bccno[g] = bcc_cnt;
bcc[bcc_cnt].push_back(g);
}
if(f == x && g == v) break;
}
}
} else if(pre[v] < pre[x] && v != fa) {
S.push(e);
low = std::min(low, pre[v]);
}
}
return low;
}
int n, m;
void calc_bcc() {
std::fill(pre, pre + 1 + n, 0);
std::fill(iscut, iscut + 1 + n, false);
std::fill(bccno, bccno + 1 + m, 0);
dcnt = bcc_cnt = 0;
for(int i = 1; i <= n; i ++) {
if(!pre[i]) dfs(i);
}
}
std::vector<int> G2[maxn + maxm];
void cz2() {
for(int i = 0; i < maxn + maxm; i ++) G2[i].clear();
}
void add_edge2(int u, int v) {
G2[u].push_back(v); G2[v].push_back(u);
}
int anc[maxn + maxm][19], dep[maxn + maxm], d[maxn + maxm];
int dfn[maxn + maxm], siz[maxn + maxm];
int cnt2;
void dfs_tree(int x, int fa = -1, int depth = 0, int s = 0) {
#ifdef LOCAL
printf("V (%d, %d, %d, %d)\n", x, fa, depth, s);
#endif
cnt2 ++; dfn[x] = cnt2; siz[x] = 1;
d[x] = s; anc[x][0] = fa; dep[x] = depth;
for(auto v : G2[x]) {
if(v != fa) {
dfs_tree(v, x, depth + 1, s + ((v <= n) ? 1 : 0));
siz[x] += siz[v];
}
}
}
void process_lca() {
memset(anc, -1, sizeof(anc));
cnt2 = 0;
int s = bcc_cnt + n; dfs_tree(n + 1);
#ifdef LOCAL
printf("s : %d\n", s);
#endif
for(int j = 1; (1 << j) < s; j ++) {
for(int i = 1; i <= s; i ++) {
int a = anc[i][j - 1];
if(a != -1) anc[i][j] = anc[a][j - 1];
}
}
}
int lca(int x, int y) {
if(dep[x] < dep[y]) std::swap(x, y);
for(int j = 18; j >= 0; j --) {
int a = anc[x][j];
if(a != -1 && dep[a] >= dep[y]) {
x = a;
}
}
if(x == y) return x;
for(int j = 18; j >= 0; j --) {
int a1 = anc[x][j], a2 = anc[y][j];
if(a1 != -1 && a2 != -1 && a1 != a2) {
x = a1; y = a2;
}
}
return anc[x][0];
}
void process() {
calc_bcc();
cz2();
for(int i = 1; i <= bcc_cnt; i ++) {
int id = n + i;
for(auto u : bcc[i]) {
add_edge2(u, id);
}
}
process_lca();
}
int get_delta(int x, int y) { // y is x's ancestor.
return (d[anc[x][0]] - d[y]);
}
bool is_anc(int fa, int bef) {
int l1 = dfn[fa], r1 = dfn[fa] + siz[fa] - 1;
int l2 = dfn[bef], r2 = dfn[bef] + siz[bef] - 1;
return (l1 <= l2 && r2 <= r1);
}
int query(int sz) {
std::vector<int> V;
for(int i = 1; i <= sz; i ++) {
int x; scanf("%d", &x);
V.push_back(x);
}
std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
return dfn[i] < dfn[j];
});
std::set<int> ds; ds.insert(V[0]);
for(int i = 1; i < sz; i ++) {
ds.insert(V[i]);
ds.insert(lca(V[i - 1], V[i]));
}
V.clear(); for(auto u : ds) V.push_back(u);
std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
return dfn[i] < dfn[j];
});
std::stack<int> S;
int ans = 0;
for(int i = 0; i < V.size(); i ++) {
int u = V[i];
while(!S.empty() && !is_anc(S.top(), u)) {
S.pop();
}
if(!S.empty()) {
#ifdef LOCAL
printf("ans (%d, %d) : %d\n", u, S.top(), get_delta(u, S.top()));
#endif
ans += get_delta(u, S.top());
}
S.push(u);
}
for(auto u : ds) {
if(u <= n) ans ++;
}
ans -= sz;
return ans;
}
int main() {
int T; scanf("%d", &T);
while(T --) {
scanf("%d%d", &n, &m); cz1();
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v);
add_edge1(u, v);
}
process();
int q; scanf("%d", &q);
while(q --) {
int sz; scanf("%d", &sz);
printf("%d\n", query(sz));
#ifdef LOCAL
fflush(stdout);
#endif
}
}
return 0;
}
[LibreOJ 2034][SDOI2016]排列计数
我这种池沼只会做水题陶冶身心了……
考虑用\(f_i\)表示长为\(i\)的完全错位全排列的个数，那么有\(i\)个错位的长度为\(n\)的全排列的数量就是\(\binom{n}{i} f_i\)。从这一点出发，可以得到一个式子（枚举错位的有几个）：
\[n! = \sum_{i = 0}^n \binom{n}{i} f_i\]
考虑使用二项式反演，得到：
\[
\begin{aligned}
f_n &= \sum_{i = 0}^n (-1)^{n - i}\binom{n}{i} i!\\
&= \sum_{i = 0}^n (-1)^{n - i}\frac{n!}{(n - i)!}\\
&= n!\sum_{i = 0}^n \frac{(-1)^{n - i}}{(n - i)!}\\
&= n!\sum_{i = 0}^n \frac{(-1)^i}{i!}
\end{aligned}
\]
后面的和式可以预处理，然后就做完啦~
代码：
#include <cstdio>
#include <cstring>
using ll = long long;
const ll ha = 1000000007LL;
inline ll pow_mod(const ll &a, ll b) {
ll ans = 1LL, res = a;
while(b) {
if(1LL & b) ans = (ans * res) % ha;
res = (res * res) % ha;
b >>= 1;
}
return ans;
}
inline ll inv(ll x) {
return pow_mod(x, ha - 2LL);
}
const int N = 1000000;
const int maxn = N + 5;
ll fac[maxn], f[maxn];
inline void process() {
fac[0] = 1LL;
for(int i = 1; i <= N; i ++) {
fac[i] = (fac[i - 1] * (ll(i))) % ha;
}
for(int i = 0; i <= N; i ++) {
f[i] = (i % 2 == 1) ? (ha - 1LL) : 1LL;
f[i] = (f[i] * inv(fac[i])) % ha;
if(i > 0) f[i] = (f[i - 1] + f[i]) % ha;
}
}
int main() {
process();
int T; scanf("%d", &T);
while(T --) {
int n, m; scanf("%d%d", &n, &m);
int p = n - m;
ll bs = (fac[p] * f[p]) % ha;
ll C = (fac[n] * inv((fac[p] * fac[m]) % ha)) % ha;
printf("%lld\n", (bs * C) % ha);
}
return 0;
}
[LibreOJ 2035][SDOI2016]征途
又做了一道适合我这种沙茶做的题qwq
考虑方差，它满足这个式子：
\[Var(X) = E[X^2] - (E[X])^2\]
对于这个题展开，发现后半部分是一个常量（\((\frac{s_n}{m})^2\)）。最小化的就是前半部分，前半部分相当于要求你求一个序列划分，使得各部分平方和的平均值最小。这个值乘上\(m^2\)之后就变成了各部分平方和乘上\(m\)。
然后就很简单了……DP方程化简之后是这样的：
\[f_{t, i} = ms_i^2 + max(f_{t - 1, j} + ms_j^2 - 2ms_i s_j)\]
求截距式形式，得：
\[2ms_i s_j + d_i = f_j + ms_j^2\]
然后用类似于上上题的方法搞就行。还有我想想啥时候补一下斜率优化的tutorial……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
#include <climits>
typedef long long ll;
typedef ll T;
struct Point {
T x, y;
Point(T qx = 0LL, T qy = 0LL) {
x = qx; y = qy;
}
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
const int maxn = 3005;
T f[maxn][maxn];
T S[maxn];
int n; T m;
void dp() {
for(int t = 1; t <= m; t ++) {
std::deque<Point> Q;
Q.push_back(Point(0LL, 0LL));
for(int i = 1; i <= n; i ++) {
ll k = 2 * m * S[i];
Vector st(1LL, k);
while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
Q.pop_front();
}
f[t][i] = m * S[i] * S[i];
f[t][i] += Q.front().y - Q.front().x * k;
#ifdef LOCAL
printf("f[%d][%d] : %lld\n", t, i, f[t][i]);
#endif
if(t == 1) continue;
Vector ins(S[i], f[t - 1][i] + m * S[i] * S[i]);
while(Q.size() > 1 && times(ins - Q.back(), Q.back() - Q[Q.size() - 2]) > 0LL) {
Q.pop_back();
}
Q.push_back(ins);
}
}
}
int main() {
scanf("%d%lld", &n, &m);
for(int i = 1; i <= n; i ++) {
scanf("%lld", &S[i]);
}
for(int i = 1; i <= n; i ++) {
S[i] += S[i - 1];
}
dp();
printf("%lld\n", f[m][n] - S[n] * S[n]);
return 0;
}
[LibreOJ 2197][SDOI2014]向量集
xjb写了写……我评测时候心脏跳得贼快（逃
考虑如果知道了那一段区间的凸包那么怎么做。首先如果向量是往上指的话，一定在上凸壳上找点比较好，反之则在下凸壳上找点比较好（放到坐标系里脑补一下？）。然后我们观察一点，在上凸壳上的最优解往两边的点会越来越劣，所以这玩意是个上凸函数，可以三分答案（我才学的整数三分啊）。
但区间凸包求起来复杂度很爆炸啊……考虑用线段树搞？观察到一点，我们区间查询所使用的线段树节点一定是只包含了已经加进来的点。所以说，一个线段树节点的凸包需要被求的情况只有一种，那就是这个节点完全已加入点被覆盖了。那每次修改之后看是否一个节点完全被已加入点覆盖，如果被完全覆盖的话才去求它的凸包。
这样一来，线段树上每个节点之多会被求一次凸包。线段树有\(\log n\)层，每一层所有节点的大小加起来是\(n\)，所以求凸包耗费的总复杂度是\(n\log^2 n\)级别的。
其实这就是用线段树模拟二进制分组？
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <climits>
#include <cassert>
using ll = long long;
using T = ll;
struct Point {
T x, y;
Point(T qx = 0LL, T qy = 0LL) {
x = qx; y = qy;
}
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
if((a.x - b.x) == 0LL) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
std::sort(P + 1, P + 1 + L, cmp);
for(int i = 1; i <= L; i ++) {
if(i != 1 && (P[i].x - P[i - 1].x) == 0LL) continue;
while(bot.size() > 1 && (times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0LL) {
bot.pop_back();
}
bot.push_back(P[i]);
}
for(int i = L; i >= 1; i --) {
if(i != L && (P[i].x - P[i + 1].x) == 0LL) continue;
while(top.size() > 1 && (times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0LL) {
top.pop_back();
}
top.push_back(P[i]);
}
std::reverse(top.begin(), top.end());
}
const int maxn = 400005;
const int maxno = maxn << 2;
const int N = 400000;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
static Point tmp[maxn];
const int lc = o << 1, rc = o << 1 | 1;
const bool used = zen[o];
zen[o] = (zen[lc] && zen[rc]);
if(zen[o] != used) {
std::copy(P + L, P + R + 1, tmp + 1);
int len = R - L + 1;
andrew(tmp, len, bot[o], top[o]);
}
}
void modify(int o, int L, int R, const int &p, const Point &v) {
if(L == R) {
zen[o] = true;
P[L] = v;
bot[o].push_back(v); top[o].push_back(v);
} else {
const int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o, L, R);
}
}
inline T search(const std::vector<Point> &vec, const Point &p) {
int l = 0, r = vec.size() - 1;
while(r - l > 2) {
int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
if(dot(p, vec[lm]) > dot(p, vec[rm])) {
r = rm;
} else {
l = lm;
}
}
T ans = LLONG_MIN;
for(int i = l; i <= r; i ++) {
ans = std::max(ans, dot(p, vec[i]));
}
return ans;
}
T query(int o, int L, int R, const int &ql, const int &qr, const Point &p) {
if(ql <= L && R <= qr) {
if(p.y > 0LL) {
return search(top[o], p);
} else {
return search(bot[o], p);
}
} else {
int M = (L + R) / 2;
T ans = LLONG_MIN;
if(ql <= M) {
ans = std::max(ans, query(o << 1, L, M, ql, qr, p));
}
if(qr > M) {
ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, p));
}
return ans;
}
}
inline int decode(int x, long long lastans) {
return x ^ (lastans & 0x7fffffff);
}
int main() {
int q; char buf[4]; scanf("%d%s", &q, buf);
bool typ_E = (buf[0] == 'E' && buf[1] == char(0));
T las = 0LL;
int tot = 0;
while(q --) {
char op[4]; scanf("%s", op);
if(op[0] == 'A') {
T x, y; scanf("%lld%lld", &x, &y);
if(!typ_E) {
x = decode(x, las); y = decode(y, las);
}
tot ++;
modify(1, 1, N, tot, Point(x, y));
} else {
T x, y, l, r; scanf("%lld%lld%lld%lld", &x, &y, &l, &r);
if(!typ_E) {
x = decode(x, las); y = decode(y, las);
l = decode(l, las); r = decode(r, las);
}
las = query(1, 1, N, l, r, Point(x, y));
printf("%lld\n", las);
}
}
return 0;
}
[LibreOJ 2033][SDOI2016]生成魔咒
辣鸡爆炸OJ又被卡了说好的修bug呢说好的新OJ呢哼我去loj交了
本题的正解是SA，但很显然可以用SAM搞过去（逃
首先字符集过大？我们可以考虑开map解决转移的问题。
然后思考一个点加入后对答案会有什么影响。一个点的对答案的贡献，就是他自己的最大表示范围减去他父亲的。因为更小的长度在之前都已经被表示过了。即使之后这个点被拆成了两个，那这两个点对答案的总贡献是不会变的。所以每次加完点，把贡献加到答案里即可。
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
typedef long long ll;
#define REP(i, l, r) for(int i = (l); i <= (r); i ++)
struct Node {
Node *fa;
std::map<int, Node*> *ch;
int len;
Node() {
fa = NULL;
ch = new std::map<int, Node*>();
}
Node(int l) {
fa = NULL;
ch = new std::map<int, Node*>();
len = l;
}
~Node() {
delete ch;
}
};
Node *rt, *last;
void init() {
rt = new Node(0);
// rt -> tl = 1;
last = rt;
}
ll ans = 0;
void insert(int c) {
static int clk = 1;
Node *np = new Node();
np -> len = last -> len + 1;
Node *p = last;
while(p != NULL && p -> ch -> count(c) == 0) {
p -> ch -> insert(std::make_pair(c, np));
p = p -> fa;
}
if(p == NULL) {
np -> fa = rt;
} else {
Node *q = (*(p -> ch -> find(c))).second;
if(q -> len == p -> len + 1) {
np -> fa = q;
} else {
Node *nq = new Node(p -> len + 1);
nq -> fa = q -> fa;
nq -> ch -> insert(q -> ch -> begin(), q -> ch -> end());
// nq -> ch -> insert(std::make_pair(c, np));
np -> fa = q -> fa = nq;
while(p != NULL && ((*(p -> ch -> find(c))).second) == q) {
p -> ch -> erase(p -> ch -> find(c));
p -> ch -> insert(std::make_pair(c, nq));
p = p -> fa;
}
}
}
last = np;
ans += np -> len - np -> fa -> len;
}
int main() {
int n; scanf("%d", &n);
init();
REP(i, 1, n) {
int c; scanf("%d", &c);
insert(c);
printf("%lld\n", ans);
}
return 0;
}
[BZOJ 4816][SDOI2017]数字表格
当年在考场上一点反演都不会啊啊啊啊啊啊
这题虽然牵扯到了对积的反演，但其实也不是很难。先让我们大力推导一波（逃
考虑枚举柿子中的\(f[(i, j)]\)中的最大公约数（设为\(k\)），然后式子变成了（这里不妨偷个懒，钦定\(n\leq m\)）：
\[\prod_{k = 1}^n f[k]^{\sum_{i = 1}^n \sum_{j = 1}^m\:[(i, j) = k]}\]
然后发现上面那个指数就是Problem b的式子，显然可化为\(\sum_{d = 1}^n \mu(d) \lfloor\frac{n}{kd}\rfloor \lfloor\frac{m}{kd}\rfloor\)。然后似乎化简没有余地了，但是根据直觉，我们可以钦定\(T = kd\)，然后枚举\(T\)。
然后柿子变成了：
\[\prod_{T = 1}^n (\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})})^{\lfloor\tfrac{n}{T}\rfloor \lfloor\tfrac{m}{T}\rfloor}\]
柿子中的\(\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})}\)是一个类似狄利克雷卷积的东西（取完对数就是了），可以枚举约数预处理。并且这个东西很不错的一点就是上面的指数是莫比乌斯函数，可以取到的值只有那三种，不需要快速幂。
然后剩下的部分就和通常的反演题一般无二了……
代码（卡线过的蒟蒻……求轻喷……但我在LOJ上跑的还挺快的）：
/**************************************************************
Problem: 4816
User: danihao123
Language: C++
Result: Accepted
Time:50840 ms
Memory:33048 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cctype>
#include <cassert>
const int N = 1000000;
const int maxn = N + 5;
typedef long long ll;
const ll ha = 1000000007LL;
bool p_flag = false;
ll pow_mod(ll a, ll b) {
if(!b) return 1LL;
ll ans = pow_mod(a, b / 2LL);
ans = (ans * ans) % ha;
if(1LL & b) ans = (ans * a) % ha;
#ifdef LOCAL
if(p_flag) printf("%lld^%lld : %lld\n", a, b, ans);
if(b == ha - 2LL) p_flag = false;
#endif
return ans;
}
ll inv(ll x) {
// if(x == 1LL) p_flag = true;
return pow_mod(x, ha - 2LL);
}
int miu[maxn];
void sieve() {
static int prm[maxn]; int cnt = 0;
static bool vis[maxn];
miu[1] = 1;
for(int i = 2; i <= N; i ++) {
if(!vis[i]) {
miu[i] = -1;
prm[cnt ++] = i;
}
for(int j = 0; j < cnt && prm[j] * i <= N; j ++) {
int v = prm[j] * i;
vis[v] = true;
if(i % prm[j] == 0) {
miu[v] = 0;
break;
} else {
miu[v] = miu[i] * -1;
}
}
}
}
ll f[maxn], inv_d[maxn], F[maxn];
void process() {
sieve();
f[1] = 1LL; inv_d[1] = 1LL;
for(int i = 2; i <= N; i ++) {
f[i] = (f[i - 1] + f[i - 2]) % ha;
inv_d[i] = inv(f[i]);
assert(f[i] != 0LL); assert(inv_d[i] != 0LL);
}
for(int i = 1; i <= N; i ++) F[i] = 1LL;
for(int i = 1; i <= N; i ++) {
for(int j = i; j <= N; j += i) {
int res = j / i;
if(miu[res] == 1) {
F[j] = (F[j] * f[i]) % ha;
#ifdef LOCAL
if(j <= 3) printf("f[%d](%lld) -> F[%d]\n", i, f[i], j);
#endif
continue;
}
if(miu[res] == -1) {
F[j] = (F[j] * inv_d[i]) % ha;
#ifdef LOCAL
if(j <= 3) printf("inv_f[%d](%lld) -> F[%d]\n", i, inv_d[i], j);
#endif
}
}
}
F[0] = 1LL;
bool flag = true;
for(int i = 1; i <= N; i ++) {
F[i] = (F[i] * F[i - 1]) % ha;
if(flag && F[i] == 0LL) {
printf("SF[%d] has been 0.\n", i);
flag = false;
}
}
}
ll calc(ll n, ll m) {
if(n > m) std::swap(n, m);
ll ans = 1LL;
for(ll i = 1; i <= n;) {
ll nx = std::min(n / (n / i), m / (m / i));
#ifdef LOCAL
// printf("nx of %lld : %lld\n", i, nx);
#endif
ll mulv = pow_mod((F[nx] * inv(F[i - 1])) % ha, (n / i) * (m / i));
ans = (ans * mulv) % ha;
i = nx + 1LL;
}
return ans;
}
int main() {
process();
int T; scanf("%d", &T);
while(T --) {
int n, m; scanf("%d%d", &n, &m);
printf("%lld\n", calc(n, m));
}
return 0;
}
[BZOJ 3992][SDOI2015]序列统计
终于调过去了……（然而不就是道NTT+生成函数水题吗至于调半天）
首先积非常的恶心，考虑转成和。这个事需要求指标的……求指标的话枚举原根的若干次幂即可（恰好$m$是素数一定有原根……），判断原根用比较大力的手段即可（我搞了一个$O(n\sqrt{n}logn)$的……求轻喷）。
然后这题还算比较简单吧……用生成函数表示原来的集合，然后$n$次幂就可以了。
注意那事个循环卷积……所以要开两倍然后每次乘完了再把右半部分搞过去。
代码：
/**************************************************************
Problem: 3992
User: danihao123
Language: C++
Result: Accepted
Time:6652 ms
Memory:1864 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <cmath>
typedef long long ll;
const int maxn = 32005;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll n, m, gl; int sz;
ll pow_mod(ll a, ll b, ll p) {
if(!b) return 1LL;
ll ans = pow_mod(a, b >> 1, p);
ans = (ans * ans) % p;
if(b & 1LL) ans = (ans * a) % p;
return ans;
}
ll inv(ll x, ll p) {
return pow_mod(x, p - 2LL, p);
}
void break_up(ll x, std::vector<ll> &V) {
int bd = sqrt(x + 0.5);
for(ll i = 2; i <= bd; i ++) {
if(x % i == 0) {
V.push_back(i);
while(x % i == 0) x /= i;
}
if(x == 1LL) break;
}
if(x > 1LL) V.push_back(x);
}
ll get_phi() {
if(m == 2LL) return 1LL;
ll mi = m - 1LL;
std::vector<ll> V;
break_up(mi, V);
for(ll i = 2; i <= mi; i ++) {
bool ok = true;
for(int j = 0; j < V.size(); j ++) {
ll b = mi / V[j];
if(pow_mod(i, b, m) == 1LL) {
ok = false;
#ifdef LOCAL
printf("%lld not passed!\n", i);
#endif
break;
}
}
if(ok) {
return i;
}
}
}
int bi, len;
int flip(int x) {
int ans = 0;
for(int i = 0; i < bi; i ++) {
if((1 << i) & x) {
ans += (1 << (bi - i - 1));
}
}
return ans;
}
void ntt(ll *A, bool flag = false) {
for(int i = 0; i < len; i ++) {
int v = flip(i);
if(v < i) std::swap(A[i], A[v]);
}
for(int L = 1; L < len; L <<= 1) {
ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)), ha);
if(flag) xi_n = inv(xi_n, ha);
for(int i = 0; i < len; i += (L << 1)) {
ll w = 1;
for(int j = i; j < i + L; j ++) {
ll p1 = A[j], p2 = A[j + L];
A[j] = (p1 + (p2 * w) % ha) % ha;
A[j + L] = (p1 - (p2 * w) % ha + ha) % ha;
w = (w * xi_n) % ha;
}
}
}
}
void poly_mul(ll *A, ll *B) {
static ll C[maxn]; memset(C, 0, sizeof(C));
#ifdef LOCAL
printf("A :");
for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
puts("");
printf("B :");
for(int i = 0; i < len; i ++) printf(" %lld", B[i]);
puts("");
#endif
ntt(A); ntt(B);
for(int i = 0; i < len; i ++) C[i] = (A[i] * B[i]) % ha;
ntt(C, true);
ll inv_n = inv(len, ha);
for(int i = 0; i < len; i ++) {
C[i] = (C[i] * inv_n) % ha;
}
#ifdef LOCAL
printf("C (not processed) :");
for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
puts("");
#endif
for(int i = 0; i < len; i ++) {
int v = i % (m - 1LL);
if(v != i) {
C[v] = (C[v] + C[i]) % ha;
C[i] = 0LL;
}
}
#ifdef LOCAL
printf("C :");
for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
puts("");
#endif
std::copy(C, C + len, A);
}
void poly_pow(ll *A, ll b) {
static ll B[maxn];
static ll res[maxn];
std::copy(A, A + len, res);
std::fill(A, A + len, 0); A[0] = 1LL;
#ifdef LOCAL
printf("A :");
for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
puts("");
printf("res : ");
for(int i = 0; i < len; i ++) printf("%lld ", res[i]);
puts("");
#endif
while(b) {
if(1LL & b) {
std::copy(res, res + len, B);
poly_mul(A, B);
std::fill(B, B + len, 0);
}
std::copy(res, res + len, B);
poly_mul(res, B);
std::fill(B, B + len, 0);
b >>= 1LL;
}
}
int main() {
static bool vis[maxn];
static ll A[maxn];
scanf("%lld%lld%lld%d", &n, &m, &gl, &sz);
ll phi = get_phi();
for(int i = 1; i <= sz; i ++) {
int v; scanf("%d", &v);
if(v == 0) continue;
vis[v] = true;
}
int logx = 0;
bi = 0; len = 1;
while(len <= (2 * m - 2)) {
bi ++; len <<= 1;
}
for(int i = 0; i < (m - 1); i ++) {
int v = pow_mod(phi, i, m);
if(vis[v]) {
A[i] ++;
#ifdef LOCAL
printf("log(%d) : %d\n", v, i);
#endif
}
if(v == gl) {
logx = i;
}
}
poly_pow(A, n);
printf("%lld\n", A[logx]);
return 0;
}
[BZOJ 2186]沙拉公主的困惑
这个题啊……亦可赛艇！
答案是[tex]\varphi(m!)*n!/m![/tex]。原因很简单，把[tex][1,n!][/tex]分成长度为[tex]m![/tex]的若干段，除去第一段外每一段中与[tex]m![/tex]互质的数[tex]k[/tex]肯定满足[tex](k\bmod m!,m!)=1[/tex]（否则，[tex]k[/tex]和[tex]m![/tex]就会有大于一的公因子了)。所以说每一段内与[tex]m![/tex]互质的数都有[tex]\varphi(m!)[/tex]个。
麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数，它的所有因子在前面都有了，只能把他自己贡献出来；如果这个数是质数（假设为[tex]p[/tex]），出了贡献自己以外还会贡献一个[tex](1-1/p)[/tex]，最后乘起来就是贡献了[tex]p-1[/tex]。筛一遍素数再递推一下就好辣~
并且……[tex]n-m[/tex]可能非常大，所以说除去[tex]m![/tex]那块要用逆元做。
（顺便说下阶乘也要递推）
代码：
/**************************************************************
Problem: 2186
User: danihao123
Language: C++
Result: Accepted
Time:9408 ms
Memory:166836 kb
****************************************************************/
#include <cstdio>
#include <cmath>
typedef unsigned long long ull;
const int maxn=10000000;
ull R;
bool vis[maxn+5];
inline void sievePrime(){
register int i,j,m=sqrt(maxn+0.5);
for(i=2;i<=m;i++)
if(!vis[i])
for(j=i*i;j<=maxn;j+=i)
vis[j]=true;
}
ull fac[maxn+5];
inline void sieveFac(){
register int i;
fac[0]=1%R;
for(i=1;i<=maxn;i++)
fac[i]=(fac[i-1]*(i%R))%R;
}
ull phifac[maxn+5];
inline void sievePhiFac(){
register int i;
phifac[1]=1%R;
for(i=2;i<=maxn;i++){
if(vis[i])
phifac[i]=(phifac[i-1]*(i%R))%R;
else
phifac[i]=(phifac[i-1]*((i%R-1%R+R)%R))%R;
}
}
void exgcd(ull a,ull b,ull& d,ull& x,ull& y){
if(!b){
d=a;
x=1;
y=0;
}else{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
ull inv(ull a){
ull d,x,y;
exgcd(a,R,d,x,y);
return (x+R)%R;
}
int main(){
int T;
int n,m;
scanf("%d%llu",&T,&R);
sievePrime();
sieveFac();
sievePhiFac();
while(T--){
scanf("%d%d",&n,&m);
printf("%llu\n",(phifac[m]*((fac[n]*inv(fac[m]))%R))%R);
}
return 0;
}
