储能表
将n, m分解为二进制，考虑一个log(n)层的trie树，n会在这颗trie树上走出了一个路径，因为 行数 $ \le n$，所以在n的二进制路径上，每次往1走的时候，与m计算贡献，m同样处理，$O(Tlog(n)log(m))$
当然可以数位dp, $f_{i, n, m, k}$分别代表考虑到第i位，与n, m, k的大小关系，不是很好写，就写了上面的方法。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template <typename T> void Max(T& a, T b) { if (b > a) a = b; }
//********************************* ll n, m, k, mod; ll POW(ll base, ll num) {
ll ret = ;
while (num) {
if (num & ) ret = ret * base % mod;
base = base * base % mod;
num >>= ;
}
return ret;
} ll calc(ll st, ll num) {
if (st < ) { num += st; st = ; }
if (num <= ) return ;
ll t1 = * st + num - ;
if (t1 & ) num >>= ;
else t1 >>= ;
return t1 % mod * (num % mod) % mod;
}
ll solve(ll x, ll y, ll i, ll j) {
ll ret();
if (j > i) swap(i, j), swap(x, y);
ll z = x ^ (y ^ (y & ((1ll << i) - )));
ret = calc(z - k, 1ll << i);
return (ret * ((1ll << j) % mod)) % mod;
}
int main() {
/*
freopen("table.in", "r", stdin);
freopen("table.out", "w", stdout);
*/
int T; scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld%lld", &n, &m, &k, &mod); ll x();
ll ans();
drep(i, , ) if (n >> i & ) {
ll y();
drep(j, , ) if (m >> j & ) {
(ans += solve(x, y, i, j)) %= mod;
y |= 1ll << j;
}
x |= 1ll << i;
} printf("%lld\n", ans);
}
}
table
数字配对
网络流，首先这个图不是奇环，这个图如果有环，那么结构应该是对称的？【我也不是非常清楚，求教。。。】
把费用和容量连成边，进行二分图染色，一直增广到费用加上当前费用小于0为止，别忘了考虑最后一次的流量。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template <typename T> void Max(T& a, T b) { if (b > a) a = b; }
//********************************* const int maxn = ; struct Ed {
int u, v, c; ll w; int nx; Ed() {}
Ed(int _u, int _v, int _c, ll _w, int _nx) :
u(_u), v(_v), c(_c), w(_w), nx(_nx) {}
} E[maxn * maxn << ];
int G[maxn], edtot = ;
void addedge(int u, int v, int c, ll w) {
E[++edtot] = Ed(u, v, c, w, G[u]);
G[u] = edtot;
E[++edtot] = Ed(v, u, , -w, G[v]);
G[v] = edtot;
} bool judge(int num) {
int sqr = sqrt(num);
if (num == ) return ;
rep(i, , sqr) if (num % i == ) return ;
return ;
}
int s, t;
int knd[maxn];
int n;
int a[maxn], b[maxn], c[maxn];
void dfs(int x, int col) {
knd[x] = col;
for (int i = ; i <= n; i++) if (knd[i] == - && (a[i] % a[x] == && judge(a[i] / a[x]) || a[x] % a[i] == && judge(a[x] / a[i]))) dfs(i, col ^ );
} ll dis[maxn]; int pre[maxn];
bool spfa() {
rep(i, , n + ) dis[i] = -INF;
static int que[maxn]; int qh(), qt();
static int vis[maxn]; memset(vis, , sizeof(vis));
vis[que[++qt] = s] = ; dis[s] = ;
while (qh != qt) {
int x = que[++qh]; if (qh == maxn - ) qh = ;
for (int i = G[x]; i; i = E[i].nx) if (E[i].c && dis[E[i].v] < dis[x] + E[i].w) {
dis[E[i].v] = dis[x] + E[i].w; pre[E[i].v] = i;
if (!vis[E[i].v]) {
vis[que[++qt] = E[i].v] = ;
if (qt == maxn - ) qt = ;
}
}
vis[x] = ;
}
return dis[t] != -INF;
}
int ans; ll cost;
bool mcf() {
int flow = inf; ll nm();
for (int i = pre[t]; i; i = pre[E[i].u]) { flow = min(flow, E[i].c); nm += E[i].w; }
if (nm * flow + cost < ) {
ans += cost / -nm;
return ;
}
ans += flow, cost += nm * flow;
for (int i = pre[t]; i; i = pre[E[i].u]) E[i].c -= flow, E[i ^ ].c += flow;
return ;
} int main() {
/*
freopen("pair.in", "r", stdin);
freopen("pair.out", "w", stdout);
*/
scanf("%d", &n);
rep(i, , n) scanf("%d", a + i);
rep(i, , n) scanf("%d", b + i);
rep(i, , n) scanf("%d", c + i); memset(knd, -, sizeof(knd));
rep(i, , n) if (knd[i] == -) dfs(i, ); rep(i, , n) rep(j, , n) if (knd[i] == && knd[j] == ) {
if (a[i] % a[j] == && judge(a[i] / a[j]) || a[j] % a[i] == && judge(a[j] / a[i])) addedge(i, j, min(b[i], b[j]), 1ll * c[i] * c[j]);
}
s = n + , t = n + ;
rep(i, , n) if (knd[i]) addedge(s, i, b[i], ); else addedge(i, t, b[i], ); while (spfa()) if (!mcf()) break; cout << ans << endl;
}
pair
游戏
树链剖分，考虑树链剖分时，每一次的修改均是连续的一段，我们对每一段维护标记$ax + b$x为当前点到这一段起点的距离。
那么假如有新的标记$Ax + B$，我们讨论$Ax + B <= ax + b$的情况，如果影响范围在mid的一边，就把新的标记向一边推，如果新的标记覆盖了多余一半，我们将新标记放在当前节点上，将原来的标记向不足mid的部分下推。
可以说是把标记永久化了。
复杂度为$O(mlog^{3}n)$，树链剖分两个log，标记一次最多下推log层。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template <typename T> void Max(T& a, T b) { if (b > a) a = b; }
//********************************* const int maxn = ; struct Ed {
int u, v, w, nx; Ed() {}
Ed(int _u, int _v, int _w, int _nx) :
u(_u), v(_v), w(_w), nx(_nx) {}
} E[maxn << ];
int G[maxn], edtot; void addedge(int u, int v, int w) {
E[++edtot] = Ed(u, v, w, G[u]);
G[u] = edtot;
E[++edtot] = Ed(v, u, w, G[v]);
G[v] = edtot;
} int pre[maxn], dep[maxn], son[maxn], sz[maxn];
ll dis[maxn];
int f[maxn][];
int dfs(int x, int fa) {
pre[x] = fa, dep[x] = dep[fa] + ; f[x][] = fa;
for (int i = ; i <= ; i++) f[x][i] = f[f[x][i - ]][i - ];
son[x] = , sz[x] = ;
for (int i = G[x]; i; i = E[i].nx) if (E[i].v != fa) {
dis[E[i].v] = dis[x] + E[i].w;
sz[x] += dfs(E[i].v, x);
if (sz[E[i].v] > sz[son[x]]) son[x] = E[i].v;
}
return sz[x];
}
int pos[maxn], inv[maxn], top[maxn], ndtot;
void repos(int x, int tp) {
top[x] = tp; pos[x] = ++ndtot; inv[ndtot] = x;
if (son[x]) repos(son[x], tp);
for (int i = G[x]; i; i = E[i].nx) if (E[i].v != son[x] && E[i].v != pre[x]) repos(E[i].v, E[i].v);
} int LCA(int l, int r) {
if (dep[l] < dep[r]) swap(l, r);
int t = dep[l] - dep[r];
drep(i, , ) if (t >> i & ) l = f[l][i];
if (l == r) return l;
drep(i, , ) if (f[l][i] != f[r][i]) l = f[l][i], r = f[r][i];
return f[l][];
} ll Min[maxn << ];
ll A[maxn << ], B[maxn << ], Flag[maxn << ];
void pushup(int o, int l, int r) {
if (Flag[o]) Min[o] = min(B[o], A[o] * (dis[inv[r]] - dis[inv[l]]) + B[o]);
if (l != r) Min[o] = min(Min[o], min(Min[o << ], Min[o << | ]));
}
void giveFlag(int o, int l, int r, ll a, ll b) {
if (!Flag[o]) { A[o] = a, B[o] = b; Flag[o] = ; }
else {
int mid = l + r >> ; ll len = dis[inv[mid + ]] - dis[inv[l]];
if (A[o] == a || l == r) B[o] = min(B[o], b);
else if (a > A[o] && B[o] < b);
else if (a > A[o] && B[o] >= b) {
ll d = (B[o] - b) / (a - A[o]);
if (d < len) giveFlag(o << , l, mid, a, b);
else {
swap(A[o], a), swap(B[o], b);
giveFlag(o << | , mid + , r, a, b + a * len);
}
}
else if (a < A[o] && B[o] > b) swap(A[o], a), swap(B[o], b);
else if (a < A[o] && B[o] <= b) {
ll d = (B[o] - b - ) / (a - A[o]) + ;
if (d >= len) giveFlag(o << | , mid + , r, a, b + a * len);
else {
swap(A[o], a), swap(B[o], b);
giveFlag(o << , l, mid, a, b);
}
}
} pushup(o, l, r);
} void modify(int o, int l, int r, int ql, int qr, ll a, ll b) {
if (ql <= l && r <= qr) {
giveFlag(o, l, r, a, b + a * (dis[inv[l]] - dis[inv[ql]]));
return;
} int mid = l + r >> ;
if (ql <= mid) modify(o << , l, mid, ql, qr, a, b);
if (qr > mid) modify(o << | , mid + , r, ql, qr, a, b);
pushup(o, l, r);
} int n;
void modify2(int tar, int x, ll a, ll b) {
while (top[tar] != top[x]) {
int F = top[x];
modify(, , n, pos[F], pos[x], a, b + a * (dis[F] - dis[tar]));
x = pre[F];
} modify(, , n, pos[tar], pos[x], a, b);
} void modify(int l, int r, ll a, ll b) {
int lca = LCA(l, r);
modify2(lca, l, -a, b + a * (dis[l] - dis[lca]));
modify2(lca, r, a, b + a * (dis[l] - dis[lca]));
} ll query(int o, int l, int r, int ql, int qr) {
ll ret = INF;
if (Flag[o]) {
int L = max(l, ql), R = min(r, qr);
ret = min(A[o] * (dis[inv[L]] - dis[inv[l]]) + B[o], A[o] * (dis[inv[R]] - dis[inv[l]]) + B[o]);
} if (ql <= l && r <= qr) return min(ret, Min[o]);
else {
int mid = l + r >> ;
if (ql <= mid) ret = min(ret, query(o << , l, mid, ql, qr));
if (qr > mid) ret = min(ret, query(o << | , mid + , r, ql, qr));
}
return ret;
} ll solve(int l, int r) {
ll ret = INF;
while (top[l] != top[r]) {
if (dep[top[l]] < dep[top[r]]) swap(l, r);
ret = min(ret, query(, , n, pos[top[l]], pos[l]));
l = pre[top[l]];
}
if (dep[l] < dep[r]) swap(l, r);
ret = min(ret, query(, , n, pos[r], pos[l])); return ret;
} int main() {
/*
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
*/
int m; scanf("%d%d", &n, &m);
REP(i, , n) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
} dfs(, ), repos(, ); REP(i, , maxn << ) Min[i] = 123456789123456789ll; while (m--) {
int op; scanf("%d", &op);
if (op == ) {
int u, v, a, b; scanf("%d%d%d%d", &u, &v, &a, &b);
modify(u, v, a, b);
}
else {
int s, t; scanf("%d%d", &s, &t);
printf("%lld\n", solve(s, t));
}
} return ;
}
game
生成魔咒
后缀数组，将字符串反过来，维护一个set，每次加入的字符串找到位置，计算贡献。
#include <bits/stdc++.h>
#define rep(i, a, b) for (register int i = a; i <= b; i++)
#define drep(i, a, b) for (register int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second using namespace std; typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
//******************************** const int maxn = ; int a[maxn], hsh[maxn], cd;
int sa[maxn], t[maxn], t2[maxn], c[maxn], n; void build_sa(int m) {
int *x = t, *y = t2;
rep(i, , m) c[i] = ;
rep(i, , n) c[x[i] = a[i]]++;
rep(i, , m) c[i] += c[i - ];
drep(i, n, ) sa[c[x[i]]--] = i; for (int k = ; k <= n; k <<= ) {
int p = ;
rep(i, n - k + , n) y[++p] = i;
rep(i, , n) if (sa[i] > k) y[++p] = sa[i] - k; rep(i, , m) c[i] = ;
rep(i, , n) c[x[y[i]]]++;
rep(i, , m) c[i] += c[i - ];
drep(i, n, ) sa[c[x[y[i]]]--] = y[i]; swap(x, y);
p = ; x[sa[]] = ;
rep(i, , n)
x[sa[i]] = y[sa[i]] == y[sa[i - ]] && y[sa[i] + k] == y[sa[i - ] + k] ? p - : p++;
if (p >= n) break;
m = p;
}
} int rnk[maxn], height[maxn];
void build_height() {
int k();
rep(i, , n) rnk[sa[i]] = i;
rep(i, , n) {
if (k) k--;
int j = sa[rnk[i] - ];
while (a[j + k] == a[i + k]) k++;
height[rnk[i]] = k;
}
} int Min[maxn][], Log[maxn];
void build_st() {
Log[] = ;
rep(i, , n) {
Log[i] = Log[i - ];
if ( << Log[i] + == i) Log[i]++;
}
drep(i, n, ) {
Min[i][] = height[i];
for (int j = ; i + ( << j) - <= n; j++)
Min[i][j] = min(Min[i][j - ], Min[i + ( << j - )][j - ]);
}
}
int query(int l, int r) {
int len = r - l + , k = Log[len];
return min(Min[l][k], Min[r - ( << k) + ][k]);
} int main() {
scanf("%d", &n);
rep(i, , n) scanf("%d", a + i), hsh[i] = a[i]; cd = n;
sort(hsh + , hsh + + n), cd = unique(hsh + , hsh + + cd) - hsh - ;
rep(i, , n) a[i] = lower_bound(hsh + , hsh + + cd, a[i]) - hsh;
rep(i, , n / ) swap(a[i], a[n - i + ]); a[++n] = ;
a[n + ] = inf;
build_sa(cd);
build_height(); build_st();
ll ans();
set <int> S; S.insert(-inf), S.insert(inf);
drep(i, n - , ) {
set<int> :: iterator H = S.lower_bound(rnk[i]), P = S.upper_bound(rnk[i]);
int A, B;
if (H != S.begin()) A = *--H; else A = -inf;
B = *P;
if (A != -inf) ans += query(min(rnk[i], A) + , max(rnk[i], A));
if (B != inf) ans += query(min(rnk[i], B) + , max(rnk[i], B));
if (A != -inf && B != inf) ans -= query(min(A, B) + , max(A, B));
printf("%lld\n", 1ll * (n - i) * (n - i - ) / + n - i - ans);
S.insert(rnk[i]);
}
return ;
}
incantation
排列计数
组合数*错排数
$f_{n} = (n - 1)(f_{n - 1} + f_{n - 2})$
#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define drep(i, a, b) for (long long i = a; i >= b; i--)
#define REP(i, a, b) for (long long i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template <typename T> void Max(T& a, T b) { if (b > a) a = b; }
//********************************* const int maxn = ;
const int mod = 1e9 + ; ll fac[maxn];
ll f[maxn];
void prepare() {
f[] = , f[] = , f[] = ;
rep(n, , ) f[n] = ((n - ) * (n - ) % mod * f[n - ] % mod + (n - ) * (n - ) % mod * f[n - ] % mod) % mod; fac[] = ;
rep(n, , ) fac[n] = fac[n - ] * n % mod;
} ll POW(ll base, int num) {
ll ret = ;
while (num) {
if (num & ) ret = ret * base % mod;
base = base * base % mod;
num >>= ;
}
return ret;
}
ll C(int n, int m) {
ll ret = fac[n];
ret = ret * POW(fac[n - m], mod - ) % mod;
ret = ret * POW(fac[m], mod - ) % mod;
return ret;
}
int main() {
prepare();
int T; scanf("%d", &T);
while (T--) {
int n, m; scanf("%d%d", &n, &m);
if (n < m) puts("");
else printf("%lld\n", C(n, m) * f[n - m] % mod);
}
return ;
}
permutation
征途
$s^{2} = \frac{\sum\limits_{i = 1}^{m}(x_{i} - \overline{x})^{2}}{m}$，将$(x_{i} - \overline{x})^{2}$展开，会发现我们其实要最小化$\sum\limits_{i = 1}^{m}x_{i}^{2}$
设$f_{i,j}$代表dp到第i位(包括i)，是第j段的最小平方和。
那么$f_{i,j} = min(f_{k,j - 1}) + (s_{i}-s_{k})^{2}$， s为前缀和。
固定j以后发现只与k有关，斜率优化即可。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
template <typename T> void Max(T& a, T b) { if (b > a) a = b; }
//********************************* const int maxn = ; ll f[maxn], s[maxn], a[maxn];
inline ll p(ll num) { return num * num; } struct HH {
ll x, y;
};
double k(HH A, HH B) { return (double)(A.y - B.y) / (A.x - B.x); } int main() {
int n, m; scanf("%d%d", &n, &m);
rep(i, , n) scanf("%lld", a + i), s[i] = s[i - ] + a[i]; rep(i, , n) f[i] = p(s[i]); rep(j, , m) {
static HH que[maxn]; int qh = , qt();
rep(i, , n) {
HH t = (HH) {s[i], f[i] + p(s[i])};
while (qt > qh && k(que[qt], t) < k(que[qt - ], que[qt])) qt--;
que[++qt] = t; while (qt > qh && k(que[qh], que[qh + ]) < * s[i]) qh++; f[i] = que[qh].y - p(que[qh].x) + p(s[i] - que[qh].x);
}
} cout << m * f[n] - p(s[n]) << endl; return ;
}
journey