为什么前面的人都跑得那么快啊？
QAQ
T1：区间方差
题目大意：询问区间方差，支持单点修改
首先把方差的式子展开，得到
$$d = frac{a_1 + ... a_n}{n} - frac{a_1^2 + .. + a_n^2 }{n^2}$$
那么，只需维护$sum a_i$和$sum a_i^2$即可
（没有区间加真是良心）
复杂度$O(n log n)$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; namespace mod_zone { const int mod = 1e9 + 7; inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; } inline void dec(int &a, int b) { a -= b; if(a < 0) a += mod; } inline int Inc(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; } inline int Dec(int a, int b) { return (a - b < 0) ? a - b + mod : a - b; } inline int mul(int a, int b) { return 1ll * a * b % mod; } inline int fp(int a, int k) { int ret = 1; for( ; k; k >>= 1, a = mul(a, a)) if(k & 1) ret = mul(ret, a); return ret; } } using namespace mod_zone; const int sid = 500050; int n, m; int w[sid], s[sid], s2[sid]; #define ls (o << 1) #define rs (o << 1 | 1) inline void upd(int o) { s[o] = Inc(s[ls], s[rs]); s2[o] = Inc(s2[ls], s2[rs]); } inline void build(int o, int l, int r) { if(l == r) { s[o] = w[l]; s2[o] = mul(w[l], w[l]); return; } int mid = (l+ r) >> 1; build(ls, l, mid); build(rs, mid + 1, r); upd(o); } inline void mdf(int o, int l, int r, int p, int v) { if(l == r) { s[o] = v; s2[o] = mul(v, v); return; } int mid = (l + r) >> 1; if(p <= mid) mdf(ls, l, mid, p, v); else mdf(rs, mid + 1, r, p, v); upd(o); } inline int qrys(int o, int l, int r, int ml, int mr) { if(ml > r || mr < l) return 0; if(ml <= l && mr >= r) return s[o]; int mid = (l + r) >> 1; return Inc(qrys(ls, l, mid, ml, mr), qrys(rs, mid + 1, r, ml, mr)); } inline int qryS(int o, int l, int r, int ml, int mr) { if(ml > r || mr < l) return 0; if(ml <= l && mr >= r) return s2[o]; int mid = (l + r) >> 1; return Inc(qryS(ls, l, mid, ml, mr), qryS(rs, mid + 1, r, ml, mr)); } int main() { n = read(); m = read(); rep(i, 1, n) w[i] = read(); build(1, 1, n); rep(i, 1, m) { int c = read(), a = read(), b = read(); if(c == 1) mdf(1, 1, n, a, b); else { int S = qrys(1, 1, n, a, b); int S2 = qryS(1, 1, n, a, b); int iv = fp(b - a + 1, mod - 2); int ans = Dec(mul(b - a + 1, S2), mul(S, S)); printf("%d ", mul(ans, mul(iv, iv))); } } return 0; }
T2：攀爬者
题目大意：在三维平面上有$n$个点，两两高度不相同，一个人会按高度从小到大的顺序爬这些点，询问路径的总长
两个点之间的距离为欧几里得距离
都从小到大爬了，顺序固定了就直接模拟吧
复杂度$O(n log n)$
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define de double #define le long double #define ri register int #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; const int sid = 50050; int n; struct ser { int x, y, z; friend bool operator < (ser a, ser b) { return a.z < b.z; } } t[sid]; int main() { n = read(); rep(i, 1, n) { t[i].x = read(); t[i].y = read(); t[i].z = read(); } sort(t + 1, t + n + 1); de ans = 0; rep(i, 1, n - 1) { de dx = t[i + 1].x - t[i].x; de dy = t[i + 1].y - t[i].y; de dz = t[i + 1].z - t[i].z; ans += sqrt(dx * dx + dy * dy + dz * dz); } printf("%.3lf ", ans); return 0; }
T3：蜈蚣
题目大意：定义一段区间的权值为异或和，把一个长为$n$的序列划分成$m$段，使得各个段的权值和最大
考虑令$f[i][j]$表示到了第$i$个点，已经划分了$j$段的最大权值
然后枚举$f[k][j - 1]$转移即可
复杂度$O(n^2 m)$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } tpr inline void cmax(ra &a, ra b) { if(a < b) a = b; } } using namespace std; using namespace remoon; int n, m; int w[1005], f[1005][105]; int main() { n = read(); m = read(); rep(i, 1, n) w[i] = read(); memset(f, 128, sizeof(f)); f[0][0] = 0; rep(i, 1, n) { int val = w[i]; drep(j, i - 1, 0) { rep(k, 1, m) cmax(f[i][k], f[j][k - 1] + val); val ^= w[j]; } } printf("%d ", f[n][m]); return 0; }
T4：漂浮的鸭子
题目大意：在一张$n$个点和$n$条边的有向图中找到权值最大的环
从一个点开始搜索，并把沿途的点都标记，如果$dfs$到了标记过的点，那么说明是环，统计方案
注意，标记应该具有同时性
即被从点$i$开始的搜索标记的点和被从点$j$开始的搜索标记的点是不同的
复杂度$O(n)$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } tpr inline void cmin(ra &a, ra b) { if(a > b) a = b; } tpr inline void cmax(ra &a, ra b) { if(a < b) a = b; } } using namespace std; using namespace remoon; const int sid = 500050; int n, cnp, tim; int cap[sid], vis[sid], nxt[sid], node[sid], val[sid]; ll dis[sid], ans; inline void addedge(int u, int v, int w) { nxt[++ cnp] = cap[u]; cap[u] = cnp; node[cnp] = v; val[cnp] = w; } #define cur node[i] inline void dfs(int o) { vis[o] = tim; for(int i = cap[o]; i; i = nxt[i]) if(!vis[cur]) dis[cur] = dis[o] + val[i], dfs(cur); else if(vis[cur] == tim) cmax(ans, dis[o] - dis[cur] + val[i]); } int main() { n = read(); rep(i, 1, n) { int nxt = read(), w = read(); addedge(i, nxt, w); } rep(i, 1, n) if(!vis[i]) ++ tim, dfs(i); printf("%lld ", ans); return 0; }
T5：最大差值
题目大意：求满足$i < j$的最大的$A_j - A_i$
对每个$j$分别统计，那么只要维护一个前缀最小值即可
复杂度$O(n)$
最大差值#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } tpr inline void cmin(ra &a, ra b) { if(a > b) a = b; } tpr inline void cmax(ra &a, ra b) { if(a < b) a = b; } } using namespace std; using namespace remoon; int main() { int n = read(); ll ans = -5e9, mi = 5e9; rep(i, 1, n) { ll v = read(); cmin(mi, v); cmax(ans, v - mi); } printf("%lld ", ans); }
T6：随机数生成器
题目大意：一个数$x$，等概率地变成$[1, x]$中的一个数，询问期望变几次变成$1$
首先写出递推式
$f[n] = frac{1}{n}(sumlimits_{i = 1}^{n} f[i]) + 1$
化简
$f[n] = frac{n + sumlimits_{i = 1}^{n - 1} f[i]}{n - 1}$
我们考虑用$S[n] = sumlimits_{i = 1}^n f[i]$来求解$f[i]$，得到
$(n - 1)S[n] = nS[n - 1] + n$
化简
$frac{S[n]}{n} = frac{S[n - 1]}{n - 1} + frac{1}{n - 1}$
令$g[n] = frac{S[n]}{n}$
那么得到$g[n] = sumlimits_{i = 1}^{n - 1} frac{1}{i} = H_{n - 1}$
即$S[n] = n * H_{n - 1}$
即$f[n] = H_{n - 2} + frac{n}{n - 1}(n geq 3)$
注意对$n = 2$特判
我们只需要一个能快速求调和级数的方法
套用欧拉公式即可
复杂度$O(1)$...
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define de double #define le long double #define ri register int #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; const double r = 0.57721566490153286060651209008240243104215933593992; de H(int x) { double res = (log(x * 1.0) + log(x + 1.0)) / 2.0; res += 1.0 / (6.0 * x * (x + 1)); res -= 1.0 / (30.0 * x * x * (x + 1) * (x + 1)); return res + r; } de solve(int v) { de ans = 0; if(v == 1) return 0; if(v == 2) return 1; if(v <= 2e7) { rep(i, 1, v - 2) ans += 1.0 / i; ans += (de)(v) / (de)(v - 1); } else ans += H(v - 2) + (de)(v) / (de)(v - 1); return ans; } int main() { int n; cin >> n; printf("%.5lf ", solve(n)); return 0; }
T7：大循环
题目大意：
求下面这个代码的值
int ans = 0; for(a[1] = 1; a[1] <= n; a[1] ++) for(a[2] = 1; a[2] < a[1]; a[2] ++) ....... for(a[k] = 1; a[k] < a[k - 1]; a[k] ++) ans += f(q);
其中，$f(q)$是一个需要计算的常数
如果循环了$S$次，那么答案为$S * f(q)$
循环的次数等价于长为$n$的序列，序列元素在$[1, m]$中，满足严格递增的方案数
从$m$个元素中选出$n$个出来，它们的序唯一，因此$S = inom{n}{m}$
然后$O(n)$地计算即可
注意$q$不要用$int$来读
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline ll read() { ll p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; namespace mod_zone { const int mod = 1e9 + 7; inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; } inline void dec(int &a, int b) { a -= b; if(a < 0) a += mod; } inline int Inc(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; } inline int Dec(int a, int b) { return (a - b < 0) ? a - b + mod : a - b; } inline int mul(int a, int b) { return 1ll * a * b % mod; } inline int fp(int a, int k) { int ret = 1; for( ; k; k >>= 1, a = mul(a, a)) if(k & 1) ret = mul(ret, a); return ret; } } using namespace mod_zone; const int sid = 500050; ll q; int n, m, k, ans; inline int C(int n, int m) { int jc1 = 1, jc2 = 1, jc3 = 1; rep(i, 1, n) jc1 = mul(jc1, i); rep(i, 1, m) jc2 = mul(jc2, i); rep(i, 1, n - m) jc3 = mul(jc3, i); jc2 = fp(jc2, mod - 2); jc3 = fp(jc3, mod - 2); return mul(jc1, mul(jc2, jc3)); } int main() { n = read(); m = read(); k = read(); q = read() % mod; int x = 1; rep(i, 0, m) { int v = read(); inc(ans, mul(v, x)); x = mul(x, q); } printf("%d ", mul(ans, C(n, k))); return 0; }
T8：会议座位
题目大意：
给定$n$个字符串
之后，给定这$n$个字符串的新的排列，求原本下标满足$i < j$，在新排列中满足$i > j$的字符串对数
把新的字符串排列离散化之后，问题等价于求逆序对
复杂度$O(n log n)$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; const int sid = 500050; char s[sid]; int n, id, v[sid], t[sid]; int son[sid][55], pos[sid]; ll ans; inline int nxt(char c) { if(c >= 'a' && c <= 'z') return c - 'a'; if(c >= 'A' && c <= 'Z') return c - 'A' + 'z' - 'a' + 1; } inline void insert(char *s, int p) { int len = strlen(s + 1); int rt = 1; rep(i, 1, len) { int opt = nxt(s[i]); if(!son[rt][opt]) son[rt][opt] = ++ id; rt = son[rt][opt]; } pos[rt] = p; } inline int find(char *s) { int len = strlen(s + 1); int rt = 1; rep(i, 1, len) { int opt = nxt(s[i]); rt = son[rt][opt]; } return pos[rt]; } inline void upd(int v) { for(ri i = v; i <= n; i += i & (-i)) t[i] ++; } inline int qry(int v) { int ret = 0; for(ri i = v; i; i -= i & (-i)) ret += t[i]; return ret; } int main() { n = read(); rep(i, 1, n) { scanf("%s", s + 1); insert(s, i); } rep(i, 1, n) { scanf("%s", s + 1); v[i] = find(s); } drep(i, n, 1) { ans += qry(v[i]); upd(v[i]); } printf("%lld ", ans); return 0; }
T9：生日礼物
题目大意：求$lcm(a, b) = n$的有序$(a, b)$对数
考虑把$n$质因子分解为$p_1^{a_1} * p_2^{a_2} ... p_k^{a_k}$
那么对于$a$而言，它在$p_1$处取了$a_1$时，$b$有$a_1 + 1$种选择
对$b$而言是一样的
但是$(a_1, a_1)$这种情况算重，因此需要$- 1$
最终答案为$prodlimits_{i = 1}^k (2 * p_i - 1)$
复杂度$O(sqrt n)$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long } using namespace std; using namespace remoon; ll n, ans = 1; int main() { cin >> n; for(ll i = 2; 1ll * i * i <= n; i ++) if(n % i == 0) { int cnt = 0; while(n % i == 0) cnt ++, n /= i; ans *= 2 * cnt + 1; } if(n > 1) ans *= 3; printf("%lld ", ans); return 0; }
T10： HKE与他的小朋友
题目大意：给定一个置换$f$，求$1 * f^k$
直接置换乘法快速幂就行
复杂度$O(n log k)$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline ll read() { ll p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; const int sid = 300050; int n, k; int p[sid], f[sid], a[sid]; inline void trans(int *ans, int *p1, int *p2) { rep(i, 1, n) f[i] = p2[p1[i]]; rep(i, 1, n) ans[i] = f[i]; } int main() { n = read(); k = read(); rep(i, 1, n) a[i] = i; rep(i, 1, n) p[read()] = i; for( ; k; k >>= 1, trans(p, p, p)) if(k & 1) trans(a, a, p); rep(i, 1, n) printf("%d ", a[i]); return 0; }
T11：宝藏
题目大意：
你有$30$种物品
支持矩形给一些物品加上一些值和查询矩阵中每种物品的奇偶性
由于只关心奇偶性，因此把$30$种物品压成一个$int$
那么原问题等价于矩形异或上一个数和查询矩形的异或和
这可以用二维树状数组解决
复杂度$O(m log^2 n)$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; const int sid = 2555; int n, m; int num[sid], t[sid][sid][2][2]; inline void upd(int x, int y, int v) { for(ri i = x; i <= n; i += (i & (-i))) for(ri j = y; j <= n; j += (j & (-j))) t[i][j][x & 1][y & 1] ^= v; } inline int qry(int x, int y) { int ret = 0; for(ri i = x; i; i -= (i & (-i))) for(ri j = y; j; j -= (j & (-j))) ret ^= t[i][j][x & 1][y & 1]; return ret; } int main() { n = read(); m = read(); rep(i, 1, m) { char c = gc(); while(c != 'P' && c != 'Q') c = gc(); if(c == 'P') { int xa = read(), ya = read(); int xb = read(), yb = read(), k = read(); rep(j, 1, 30) num[j] = 0; rep(j, 1, k) { int a = read(), b = read(); num[a] += b; } int go = 0; rep(j, 1, 30) if(num[j] & 1) go |= (1 << j - 1); upd(xa, ya, go); upd(xb + 1, ya, go); upd(xa, yb + 1, go); upd(xb + 1, yb + 1, go); } else { int xa = read(), ya = read(); int xb = read(), yb = read(); int ans = qry(xb, yb) ^ qry(xa - 1, yb); ans ^= qry(xb, ya - 1) ^ qry(xa - 1, ya - 1); rep(j, 1, 30) if(ans & (1 << j - 1)) putchar('2'); else putchar('1'); putchar(' '); } } return 0; }
T12：简单的函数
题目大意：
定义$t$为最小的不是$n$的因子的数
定义$f(2) = 1$，并且$f(n) = f(t) + 1(n geq 3)$
询问$f(2) * f(3) ... * f(n)$
首先打个表，发现$f(i)$落在$[1,4]$内
考虑对$1, 2, 3, 4$分别求解
一. $f(n) = 1$，只有$n = 2$时成立
二. $f(n) = 2$，由于只有$f(2) = 1$，因此$2$是最小的不是$n$的因子的数，即$n$为奇数
三. $f(n) = 3$和$f(n) = 4$，所有能转移到偶数的$n$满足$f(n) = 4$，否则$f(n) = 3$
我们发现，满足$f(n) = 4$的数成一些循环节
这是因为，不妨设$n = 2^k * p$，并且$n$最小的非因子数为$v$
如果$v / gcd(v, n)$是某个奇质数$x$，由于$v$中一定有$2$这个因子，并且$2x > x$，所以不存在$n$不包含$x$因子的情况
类似的探讨，可以得到$v / gcd(v, n) = 2$
那么最小的非因子数为$v$的数一定满足$n = v / 2 * p$，如果对$n$增加$2p$，那么它仍满足$v / gcd(v, n) = 2$
也就是说$2p$是一个循环节
那么比$2p$更大的循环节是怎么来的呢？
一定是最小的非因子数大于$v$的循环节
这时，$n$至少要乘个$2$，由于$n$中$2$的幂次改变了，因此不同的循环节之间不会互相影响
易知循环节不会太多，实际上在$n leq 10^{18}$的范围中，只有$4$个
找出循环节直接统计即可
#include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll __int128 #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline ll read() { ll p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; namespace mod_zone { const int mod = 1e9 + 7; inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; } inline void dec(int &a, int b) { a -= b; if(a < 0) a += mod; } inline int Inc(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; } inline int Dec(int a, int b) { return (a - b < 0) ? a - b + mod : a - b; } inline int mul(int a, int b) { return 1ll * a * b % mod; } inline int fp(int a, ll k) { int ret = 1; for( ; k; k >>= 1, a = mul(a, a)) if(k & 1) ret = mul(ret, a); return ret; } } using namespace mod_zone; ll n; int ans, tot; long long tn; ll cy[105]; inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } inline ll nj(ll a) { return (a + 1) / 2; } inline ll solve(ll n) { ll now = 2; int pot = 3; while(1) { bool flag = 0; while(1) { if(now % pot == 0) pot ++; else { if(pot & 1) now *= pot / gcd(pot, now), pot ++; else { flag = 1; cy[++ tot] = now; } } if(flag || now > n) break; } if(now > n) break; now *= pot / gcd(pot, now); pot ++; } ll ret = 0; for(int i = 1; i <= tot; i ++) ret += nj(n / cy[i]); return ret; } int main() { cin >> tn; n = tn; ll n2 = (n + 1) / 2 - 1; ll n4 = solve(n); ll n3 = n / 2 - 1 - n4; int ans = fp(2, n2); ans = mul(ans, mul(fp(3, n3), fp(4, n4))); printf("%d ", ans); return 0; }
T13：数列游戏
题目大意：
给定两个序列$A, B$
如果$A_i$和$A_{i + 1}$不互质，那么你可以把$A_i$和$A_{i + 1}$删除，并且得到$B_i + B_{i + 1}$的得分
之后，你需要把$A_i, A_{i + 1}, B_i, B_{i + 1}$删除，并将$A, B$按相对顺序重新编号
当$A$中所有相邻的数互质时，游戏结束，试最大化权值
令$f[i]$表示在$i$最后活着的情况下，$1 sim i$的最大收益
那么转移为$f[i] = f[j] + sum(i, j)$，并且区间$[j + 1, i - 1]$可以被删除
我们考虑区间$dp$
令$g[i][j]$表示区间$[i, j]$可不可以被删除
那么转移时，枚举区间$[i, j]$中两个点$a, b$
只需要$a, b$不互质，并且区间$[i, a - 1]$，$[a + 1, b - 1]$，$[b + 1, j]$都可以删除时
那么区间$[i, j]$就可以被删除
这是一个$O(n^4)$的算法
考虑优化，区间$[i, j]$中，如果可以删除完，点$i$一定可以被删除
那么，我们枚举跟$i$配对的是$k$，只需要区间$[i + 1, k - 1]$和区间$[k + 1, j]$可以被删除即可
这样子复杂度就是$O(n^3)$啦...
下面这个代码优化了挺多地方，跑的还行吧...
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } tpr inline void cmin(ra &a, ra b) { if(a > b) a = b; } tpr inline void cmax(ra &a, ra b) { if(a < b) a = b; } tpr inline bool ckmin(ra &a, ra b) { return (a > b) ? a = b, 1 : 0; } tpr inline bool ckmax(ra &a, ra b) { return (a < b) ? a = b, 1 : 0; } } using namespace std; using namespace remoon; #define ll long long const int sid = 805; int n; int a[sid], b[sid]; bool ok[sid][sid]; int g[sid][sid]; ll f[sid], sb[sid]; inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int len(int a, int b) { return b - a + 1; } inline bool dfs(int l, int r) { if(l > r) return 1; if(len(l, r) & 1) return 0; if(g[l][r] != -1) return g[l][r]; bool flag = 0; for(int i = l + 1; i <= r; i += 2) { if(ok[l][i]) flag = dfs(l + 1, i - 1) && dfs(i + 1, r); if(flag) break; } return g[l][r] = flag; } int main() { n = read(); rep(i, 1, n) a[i] = read(); rep(i, 1, n) b[i] = read(); rep(i, 1, n) sb[i] = sb[i - 1] + b[i]; rep(i, 1, n) rep(j, i, n) if(i != j && !(len(i + 1, j - 1) & 1) && gcd(a[i], a[j]) != 1) ok[i][j] = 1; memset(g, -1, sizeof(g)); memset(f, 128, sizeof(f)); f[0] = 0; rep(i, 1, n + 1) { cmax(f[i], f[i - 1]); rep(j, 0, i - 2) if(f[j] + sb[i - 1] - sb[j] > f[i] && dfs(j + 1, i - 1)) f[i] = f[j] + sb[i - 1] - sb[j]; } printf("%lld ", f[n + 1]); return 0; }