为什么前面的人都跑得那么快啊？
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
}
using namespace std;
using namespace remoon;namespace mod_zone {
const int mod = 1e9 + ;
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 < ) 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 < ) ? 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 = ;
for( ; k; k >>= , a = mul(a, a))
if(k & ) ret = mul(ret, a);
return ret;
}
}
using namespace mod_zone;const int sid = ;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) >> ;
build(ls, l, mid);
build(rs, mid + , 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) >> ;
if(p <= mid) mdf(ls, l, mid, p, v);
else mdf(rs, mid + , r, p, v);
upd(o);
}inline int qrys(int o, int l, int r, int ml, int mr) {
if(ml > r || mr < l) return ;
if(ml <= l && mr >= r) return s[o];
int mid = (l + r) >> ;
return Inc(qrys(ls, l, mid, ml, mr), qrys(rs, mid + , r, ml, mr));
}inline int qryS(int o, int l, int r, int ml, int mr) {
if(ml > r || mr < l) return ;
if(ml <= l && mr >= r) return s2[o];
int mid = (l + r) >> ;
return Inc(qryS(ls, l, mid, ml, mr), qryS(rs, mid + , r, ml, mr));
}int main() {
n = read(); m = read();
rep(i, , n) w[i] = read();
build(, , n);
rep(i, , m) {
int c = read(), a = read(), b = read();
if(c == ) mdf(, , n, a, b);
else {
int S = qrys(, , n, a, b);
int S2 = qryS(, , n, a, b);
int iv = fp(b - a + , mod - );
int ans = Dec(mul(b - a + , S2), mul(S, S));
printf("%d\n", mul(ans, mul(iv, iv)));
}
}
return ;
}
1
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
}
using namespace std;
using namespace remoon;const int sid = ;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, , n) {
t[i].x = read();
t[i].y = read();
t[i].z = read();
}
sort(t + , t + n + );
de ans = ;
rep(i, , n - ) {
de dx = t[i + ].x - t[i].x;
de dy = t[i + ].y - t[i].y;
de dz = t[i + ].z - t[i].z;
ans += sqrt(dx * dx + dy * dy + dz * dz);
}
printf("%.3lf\n", ans);
return ;
}
2
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', 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[], f[][];int main() {
n = read(); m = read();
rep(i, , n) w[i] = read();
memset(f, , sizeof(f));
f[][] = ;
rep(i, , n) {
int val = w[i];
drep(j, i - , ) {
rep(k, , m) cmax(f[i][k], f[j][k - ] + val);
val ^= w[j];
}
}
printf("%d\n", f[n][m]);
return ;
}
3
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', 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 = ;
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, , n) {
int nxt = read(), w = read();
addedge(i, nxt, w);
}
rep(i, , n) if(!vis[i]) ++ tim, dfs(i);
printf("%lld\n", ans);
return ;
}
4
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', 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, , n) {
ll v = read();
cmin(mi, v); cmax(ans, v - mi);
}
printf("%lld\n", ans);
}
5
T6：随机数生成器
题目大意：一个数$x$，等概率地变成$[1, x]$中的一个数，询问期望变几次变成$1$
首先写出递推式
$f[n] = \frac{1}{n}(\sum\limits_{i = 1}^{n} f[i]) + 1$
化简
$f[n] = \frac{n + \sum\limits_{i = 1}^{n – 1} f[i]}{n – 1}$
我们考虑用$S[n] = \sum\limits_{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] = \sum\limits_{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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', 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 + ));
res -= 1.0 / (30.0 * x * x * (x + ) * (x + ));
return res + r;
}de solve(int v) {
de ans = ;
if(v == ) return ;
if(v == ) return ;
if(v <= 2e7) {
rep(i, , v - ) ans += 1.0 / i;
ans += (de)(v) / (de)(v - );
}
else ans += H(v - ) + (de)(v) / (de)(v - );
return ans;
}int main() {
int n; cin >> n;
printf("%.5lf\n", solve(n));
return ;
}
6
T7：大循环
题目大意：
求下面这个代码的值
int ans = ;
for(a[] = ; a[] <= n; a[] ++)
for(a[] = ; a[] < a[]; a[] ++)
.......
for(a[k] = ; a[k] < a[k - ]; a[k] ++)
ans += f(q);
其中，$f(q)$是一个需要计算的常数
如果循环了$S$次，那么答案为$S * f(q)$
循环的次数等价于长为$n$的序列，序列元素在$[1, m]$中，满足严格递增的方案数
从$m$个元素中选出$n$个出来，它们的序唯一，因此$S = \binom{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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
}
using namespace std;
using namespace remoon;namespace mod_zone {
const int mod = 1e9 + ;
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 < ) 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 < ) ? 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 = ;
for( ; k; k >>= , a = mul(a, a))
if(k & ) ret = mul(ret, a);
return ret;
}
}
using namespace mod_zone;const int sid = ;ll q;
int n, m, k, ans;inline int C(int n, int m) {
int jc1 = , jc2 = , jc3 = ;
rep(i, , n) jc1 = mul(jc1, i);
rep(i, , m) jc2 = mul(jc2, i);
rep(i, , n - m) jc3 = mul(jc3, i);
jc2 = fp(jc2, mod - ); jc3 = fp(jc3, mod - );
return mul(jc1, mul(jc2, jc3));
}int main() {
n = read(); m = read();
k = read(); q = read() % mod;
int x = ;
rep(i, , m) {
int v = read();
inc(ans, mul(v, x));
x = mul(x, q);
}
printf("%d\n", mul(ans, C(n, k)));
return ;
}
7
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
}
using namespace std;
using namespace remoon;const int sid = ;char s[sid];
int n, id, v[sid], t[sid];
int son[sid][], 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' + ;
}inline void insert(char *s, int p) {
int len = strlen(s + );
int rt = ;
rep(i, , 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 + );
int rt = ;
rep(i, , 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 = ;
for(ri i = v; i; i -= i & (-i))
ret += t[i];
return ret;
}int main() {
n = read();
rep(i, , n) {
scanf("%s", s + );
insert(s, i);
}
rep(i, , n) {
scanf("%s", s + );
v[i] = find(s);
}
drep(i, n, ) {
ans += qry(v[i]);
upd(v[i]);
}
printf("%lld\n", ans);
return ;
}
8
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$
最终答案为$\prod\limits_{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 = ;
int main() {
cin >> n;
for(ll i = ; 1ll * i * i <= n; i ++)
if(n % i == ) {
int cnt = ;
while(n % i == ) cnt ++, n /= i;
ans *= * cnt + ;
}
if(n > ) ans *= ;
printf("%lld\n", ans);
return ;
}
9
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
}
using namespace std;
using namespace remoon;const int sid = ;int n, k;
int p[sid], f[sid], a[sid];inline void trans(int *ans, int *p1, int *p2) {
rep(i, , n) f[i] = p2[p1[i]];
rep(i, , n) ans[i] = f[i];
}int main() {
n = read(); k = read();
rep(i, , n) a[i] = i;
rep(i, , n) p[read()] = i; for( ; k; k >>= , trans(p, p, p))
if(k & ) trans(a, a, p); rep(i, , n) printf("%d ", a[i]);
return ;
}
10
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
}
using namespace std;
using namespace remoon;const int sid = ;int n, m;
int num[sid], t[sid][sid][][];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 & ][y & ] ^= v;
}inline int qry(int x, int y) {
int ret = ;
for(ri i = x; i; i -= (i & (-i)))
for(ri j = y; j; j -= (j & (-j)))
ret ^= t[i][j][x & ][y & ];
return ret;
}int main() {
n = read(); m = read();
rep(i, , 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, , ) num[j] = ;
rep(j, , k) {
int a = read(), b = read();
num[a] += b;
}
int go = ;
rep(j, , ) if(num[j] & ) go |= ( << j - );
upd(xa, ya, go);
upd(xb + , ya, go);
upd(xa, yb + , go);
upd(xb + , yb + , go);
}
else {
int xa = read(), ya = read();
int xb = read(), yb = read();
int ans = qry(xb, yb) ^ qry(xa - , yb);
ans ^= qry(xb, ya - ) ^ qry(xa - , ya - );
rep(j, , )
if(ans & ( << j - )) putchar('');
else putchar('');
putchar('\n');
}
}
return ;
}
11
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
}
}
using namespace std;
using namespace remoon;namespace mod_zone {
const int mod = 1e9 + ;
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 < ) 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 < ) ? 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 = ;
for( ; k; k >>= , a = mul(a, a))
if(k & ) ret = mul(ret, a);
return ret;
}
}
using namespace mod_zone;ll n;
int ans, tot;
long long tn;
ll cy[];inline ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}inline ll nj(ll a) {
return (a + ) / ;
}inline ll solve(ll n) {
ll now = ;
int pot = ;
while() {
bool flag = ;
while() {
if(now % pot == ) pot ++;
else {
if(pot & ) now *= pot / gcd(pot, now), pot ++;
else { flag = ; cy[++ tot] = now; }
}
if(flag || now > n) break;
}
if(now > n) break;
now *= pot / gcd(pot, now); pot ++;
} ll ret = ;
for(int i = ; i <= tot; i ++) ret += nj(n / cy[i]);
return ret;
}int main() {
cin >> tn;
n = tn;
ll n2 = (n + ) / - ;
ll n4 = solve(n);
ll n3 = n / - - n4;
int ans = fp(, n2);
ans = mul(ans, mul(fp(, n3), fp(, n4)));
printf("%d\n", ans);
return ;
}
12
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 = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', 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, : ; }
tpr inline bool ckmax(ra &a, ra b) { return (a < b) ? a = b, : ; }
}
using namespace std;
using namespace remoon;#define ll long longconst int sid = ;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 + ; }inline bool dfs(int l, int r) {
if(l > r) return ;
if(len(l, r) & ) return ;
if(g[l][r] != -) return g[l][r];
bool flag = ;
for(int i = l + ; i <= r; i += ) {
if(ok[l][i])
flag = dfs(l + , i - ) && dfs(i + , r);
if(flag) break;
}
return g[l][r] = flag;
}int main() {
n = read();
rep(i, , n) a[i] = read();
rep(i, , n) b[i] = read(); rep(i, , n) sb[i] = sb[i - ] + b[i];
rep(i, , n) rep(j, i, n)
if(i != j && !(len(i + , j - ) & ) && gcd(a[i], a[j]) != )
ok[i][j] = ; memset(g, -, sizeof(g));
memset(f, , sizeof(f));
f[] = ;
rep(i, , n + ) {
cmax(f[i], f[i - ]);
rep(j, , i - )
if(f[j] + sb[i - ] - sb[j] > f[i] && dfs(j + , i - ))
f[i] = f[j] + sb[i - ] - sb[j];
}
printf("%lld\n", f[n + ]);
return ;
}
13
