T1、完全背包
有 (n (n leq 10 ^ 6)) 件物品，体积为 (a_i (a_i leq 100))，价值为 (b_i (b_i leq 100))。求一个容量为 (m (m leq 10 ^ {18})) 的背包可获得的最大价值。
(Sol_1)：
(lemma)：任意 (n) 个整数中一定能取出一段数使得它们的和被 (n) 整除。
(prf)：
记 (n) 个数的前缀和为 (S_i)；
({i in [0,n] igcap | S_i }) 里的 (n + 1) 个数，一定存在一组 (i,j) 满足 (S_i equiv S_j mod n)。
(Q.E.D.)
观察到物品只需保留不超过 (100) 个。
设所有物品中性价比最高的物品编号为 (s)；
则最优方案中，性价比小于 (frac{b_s}{a_s}) 的物品数量不超过 (a_s)；
证明可以用到上述引理，若个数超过 (a_s) 一定可以选出来一些用物品 (s) 替换。
所以超过 (100a_s) 的部分全部用来取第 (s) 件物品，剩下的完全背包即可。
复杂度 (O(100 imes 100 a_s))。
(Source_1)：
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
long long lin() {
long long x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 1e4;
struct node {
int a, b;
inline bool operator < (const node& y) const {
if (this->b * y.a == y.b * this->a)
return this->a < this->a;
return this->b * y.a > y.b * this->a;
}
} t[105];
int max[105];
int n, nn, f[N + N + 5];
long long m, res;
void backpack() {
f[0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = t[i].a; j <= nn; ++j)
chk_max(f[j], f[j - t[i].a] + t[i].b);
}
int main() {
//freopen("in", "r", stdin);
freopen("backpack.in", "r", stdin);
freopen("backpack.out", "w", stdout);
n = in(), m = lin();
memset(max, -1, sizeof(max));
for (int i = 1, x, y; i <= n; ++i) {
x = in(), y = in();
chk_max(max[x], y);
}
n = 0;
for (int i = 1; i <= 100; ++i)
if (~max[i])
t[++n] = (node){i, max[i]};
std::sort(t + 1, t + 1 + n);
if (m > N) {
res = (m - N) / t[1].a * t[1].b;
nn = (m - N) % t[1].a + N;
} else {
nn = m;
}
backpack();
res += f[nn];
printf("%lld
", res);
return 0;
}
(Sol_2)：
这种数据范围很容易想到用矩阵来优化，可以试着构造一种矩阵运算 (*)。
设有两个矩阵 (A, B)，且 (A * B = C)；
我们规定 (C_{i, j} = max_{k = 1} ^ {n} { A_{i, k} + B_{k, j} }) (类似矩阵乘法)。
该运算的单位矩阵为：
[left[
egin{matrix}
0 & -infin & -infin & cdots & -infin & -infin \
-infin & 0 & -infin & cdots & -infin & -infin \
-infin & -infin & 0 & cdots & -infin & -infin \
vdots & vdots & vdots & ddots & 0 & -infin \
-infin & -infin & -infin & cdots & -infin & 0
end{matrix}
ight]
]
并不难证明该运算有结合律，故快速 (*) (???)。
时间复杂度 (O(100 ^ 3 log_2 m))。
(Source_2)：
//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
long long lin() {
long long x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 105;
int max[105], n;
long long m;
struct matrix {
long long a[N][N];
matrix(long long _ = -1) {
memset(a, -1, sizeof(a));
if (~_)
for (int i = 0; i < 100; ++i)
a[i][i] = _;
}
inline long long* operator [] (const int x) {
return a[x];
}
matrix operator * (matrix b) const {
matrix ret;
for (int k = 0; k < 100; ++k)
for (int i = 0; i < 100; ++i)
if (~a[i][k])
for (int j = 0; j < 100; ++j)
if (~b[k][j])
chk_max(ret[i][j], a[i][k] + b[k][j]);
return ret;
}
matrix operator ^ (long long b) const {
matrix ret(0), base = *this;
for (; b; b >>= 1ll, base = base * base)
if (b & 1ll)
ret = ret * base;
return ret;
}
} ;
void backpack(long long *f) {
f[0] = 0;
for (int i = 1; i <= 100; ++i) {
if (~max[i]) {
for (int j = i; j < 100; ++j) {
if (~f[j - i]) {
chk_max(f[j], f[j - i] + max[i]);
}
}
}
}
}
int main() {
//freopen("in", "r", stdin);
freopen("backpack.in", "r", stdin);
freopen("backpack.out", "w", stdout);
n = in(), m = lin();
memset(max, -1, sizeof(max));
for (int i = 1, a, b; i <= n; ++i) {
a = in(), b = in();
chk_max(max[a], b);
}
matrix f, trans;
backpack(f[0]);
for (int i = 0; i < 99; ++i)
trans[i + 1][i] = 0;
for (int i = 0; i < 100; ++i)
trans[i][99] = max[100 - i];
f = f * (trans ^ m);
printf("%lld
", f[0][0]);
return 0;
}
T2、中间值
有两个长度为 (n (n leq 5 imes 10 ^ 5)) 的非降序列 (a,b)，(m (m leq 10 ^ 6)) 次操作：
1、修改 (a(0)) 或 (b(1)) 中的某个数，保证修改后依旧非降；
2、求将某两个区间 ([l_a,r_a], [l_b,r_b]) 合并后中间的数，保证两区间长度和为奇数。
(Sol_1)：
直接二分，细节较多；
比如在 (l_a, r_a) 中二分到 (mid)，只需判断 (a_{mid}) 在 (b) 中应该出现的位置是否合法即可。
(Sol_2)：
考虑分治。
设当前要求第 (k) 大元素，可能出现答案的区间为 ([l_a, r_a], [l_b, r_b])；
设两个区间中第 (frac{k}{2}) 大的元素为 (a_x, b_y) (不讨论边界)；
不妨设 (a_x < b_y)，那么 (a) 中在 (x) 之前、(b) 中在 (y) 之后的数就不是答案，递归即可。
以上两种做法都可以扩展到第 (k) 大，做法同上。
时间复杂度都为 (O(m log_2 n))。
(Source)：
//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 5e5 + 5;
int n, m, a[N], b[N];
int binary_search(int xl, int xr, int yl, int yr, int *x, int *y) {
int l = xl, r = xr, mid, t, k = (xr - xl + yr - yl + 3) >> 1;
while (l < r) {
mid = (l + r) >> 1;
t = (k - 1) - (mid - xl) + yl;
if (t < yl) {
r = mid - 1;
continue;
} if (t > yr + 1) {
l = mid + 1;
continue;
}
if ((t == yr + 1 || y[t] >= x[mid]) && (t == yl || y[t - 1] <= x[mid]))
return mid;
if (y[t] < x[mid]) {
r = mid - 1;
} else if (y[t - 1] > x[mid]) {
l = mid + 1;
}
}
if (l == r) {
t = (k - 1) - (l - xl) + yl;
if ((t == yr + 1 || y[t] >= x[l]) && (t == yl || y[t - 1] <= x[l]))
return l;
}
return -1;
}
int calc(int l1, int r1, int l2, int r2, int k) {
if (l1 > r1)
return b[l2 + k - 1];
if (l2 > r2)
return a[l1 + k - 1];
if (k == 1)
return a[l1] < b[l2] ? a[l1] : b[l2];
int p1, p2;
if (r1 - l1 + 1 < (k >> 1)) {
p1 = r1 - l1 + 1;
p2 = k - p1;
} else if (r2 - l2 + 1 < ((k + 1) >> 1)) {
p2 = r2 - l2 + 1;
p1 = k - p2;
} else {
p1 = k >> 1;
p2 = (k + 1) >> 1;
}
if (a[l1 + p1 - 1] < b[l2 + p2 - 1]) {
return calc(l1 + p1, r1, l2, l2 + p2 - 1, p2);
} else {
return calc(l1, l1 + p1 - 1, l2 + p2, r2, p1);
}
}
int main() {
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
freopen("median.in", "r", stdin);
freopen("median.out", "w", stdout);
n = in(), m = in();
for (int i = 1; i <= n; ++i)
a[i] = in();
for (int i = 1; i <= n; ++i)
b[i] = in();
int la, ra, lb, rb, res;
while (m--) {
if (in() == 1) {
if (!in()) {
la = in();
a[la] = in();
} else {
la = in();
b[la] = in();
}
} else {
la = in(), ra = in(), lb = in(), rb = in();
//printf("%d
", calc(la, ra, lb, rb, (ra - la + rb - lb + 3) >> 1));
res = binary_search(la, ra, lb, rb, a, b);
if (~res) {
printf("%d
", a[res]);
} else {
res = binary_search(lb, rb, la, ra, b, a);
if (~res) {
printf("%d
", b[res]);
}
}
}
}
return 0;
}
T3、Sequence
记 (f(A)) 表示所有长度为 (n (nleq 10 ^ {18})) 且满足 (forall i in [1,n] a_i | A) 的序列的价值和；
一个序列的价值为 (gcd(a_1, a_2, a_3 dots a_n, B), (B leq 10 ^ {18}))；
求 (sum_{i = 1}^m f(i), (m leq 2 imes 10 ^ {7}))，答案对 (998244353) 取模。
(Sol)：
显然地，若 (gcd(x, y) = 1)，则有 (gcd(xy, B) = gcd(x, B) imes gcd(y, B))。
同样地，若 (gcd(x, y) = 1)，则 (f(xy)) 所对应的集合为 (f(x)) 和 (f(y)) 对应集合的笛卡尔积。
(f(x)) 是一个积性函数。
只需计算形如 (x = p ^ c) 的 (f(x)) 即可，其中 (p) 是质数；
设 (k) 满足 (p ^ k | B) 且 (p ^ {k + 1}
mid B)，那么有：
[egin{align}
f(x) &= sum_{i = 0}^{c} p ^ i ig[ (c - i + 1) ^ n - (c - i) ^ n ig] , (c leq k)
otag \
f(x) &= p ^ k (c - k + 1) ^ n + sum_{i = 0}^{k - 1} p ^ i ig[ (c - i + 1) ^ n - (c - i) ^ n ig] , (c > k)
otag \
end{align}
]
时间复杂度 (O(frac{m}{ln m} imeslog_? ^2 m))，计算 (f(p ^ c)) 时需要枚举 (c)，这个 (log) 很小可以当做常数对待 (应该)。
(Source)：
//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <algorithm>
int in() {
int x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
long long lin() {
long long x = 0; char c = getchar(); bool f = 0;
while (c < '0' || c > '9')
f |= c == '-', c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }
const int N = 2e7 + 5, mod = 998244353;
long long n, B;
int m, pri_cnt, pri[N / 10], min_pri[N], f[N], Pow[105];
std::pair<int, int> g[N];
inline void add(int &_, int __) {
_ += __;
if (_ >= mod)
_ -= mod;
}
int qpow(int base, int b, int ret = 1) {
for (; b; b >>= 1, base = 1ll * base * base % mod)
if (b & 1)
ret = 1ll * ret * base % mod;
return ret;
}
void Euler_sieve() {
for (int i = 2; i <= m; ++i) {
if (!min_pri[i]) {
g[i].second = min_pri[i] = pri[++pri_cnt] = i;
g[i].first = 1;
}
for (int j = 1, tmp; j <= pri_cnt && i * pri[j] <= m; ++j) {
tmp = i * pri[j];
g[tmp].second = min_pri[tmp] = pri[j];
g[tmp].first = 1;
if (!(i % pri[j])) {
g[tmp].first += g[i].first;
g[tmp].second *= g[i].second;
break;
}
}
}
}
void calc_f() {
int nn = n % (mod - 1);
for (int i = 0; i <= 100; ++i)
Pow[i] = qpow(i, nn);
f[1] = 1;
for (int i = 2; i <= m; ++i) {
if (g[i].second == i) {
for (int j = 0, tmp = 1; j <= g[i].first; ++j) {
add(f[i], 1ll * tmp * (Pow[g[i].first - j + 1] - Pow[g[i].first - j] + mod) % mod);
if (!((B / tmp) % min_pri[i]))
tmp *= min_pri[i];
}
} else {
f[i] = 1ll * f[i / g[i].second] * f[g[i].second] % mod;
}
}
for (int i = 1; i <= m; ++i)
add(f[i], f[i - 1]);
}
int main() {
//freopen("in", "r", stdin);
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
n = lin(), m = in(), B = lin();
Euler_sieve();
calc_f();
printf("%d
", f[m]);
return 0;
}