striving & singing
考虑欧几里得算法： $$\gcd(q^a-1,q^b-1)=\gcd(q^a-1-q^{a-b}(q^b-1),q^b-1)\\=\gcd(q^{a-b}-1,q^b-1)$$
相当于每次对指数进行一次更相减损，因此答案就是$q^{\gcd(a,b)}-1$。
#include<cstdio>
int t, q, a, b, p;
inline int pwr(int x, int k) {
int ans = 1;
for (; k; x = (long long)x * x % p, k >>= 1)
if (k & 1) ans = (long long)ans * x % p;
return ans % p;
}
inline int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a % b);
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d%d%d", &q, &a, &b, &p);
printf("%d\n", (pwr(q, gcd(a, b)) - 1 + p) % p);
}
return 0;
}http://csp.ac/contest/42/problem/286
暴力做法是记录每种糖果数的袋子数量，然后每次查询直接找倍数。可以加一个类似于 Dinic 中的当前弧优化的优化，记录一下每个数最近一次找到的倍数是多少，然后下次直接从这个倍数开始找，复杂度$O(n+m)$。
#include<cstdio>
int n, m, cnt[1000100], cur[1000100], k, ans[1000100], maxa;
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
cnt[x]++;
maxa = max(maxa, x);
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int x; scanf("%d", &x);
int j = cur[x];
while (j <= maxa && !cnt[j]) j += x;
if (j > maxa) break;
cnt[j]--;
cur[x] = j;
ans[++k] = j;
}
printf("%d\n", k);
for (int i = 1; i <= k; i++) printf("%d ", ans[i]);
return 0;
}http://csp.ac/contest/42/problem/287
我在考场上写的做法是把式子拆开，然后分治计算，和之前求和那题思路是一样的，因为带修所以还需要树状数组维护，总复杂度$O(m\log^2n)$，直接 TLE 和暴力同分。
更优的做法是利用拉格朗日恒等式：
$$\left(\sum_{i=1}^na_i^2\right)\left(\sum_{i=1}^nb_i^2\right)=\left(\sum_{i=1}^na_ib_i\right)^2+\sum_{1\le i<j\le n}(a_ib_j-a_jb_i)^2$$
因此直接维护区间 a 平方和，b 平方和，ab 之积即可。
#include<cstdio>
const int MOD = 998244353;
int n, q, a[500100], b[500100];
struct ft {
int a[500100];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int v) { for (; x <= n; x += lowbit(x)) a[x] = (a[x] + v) % MOD; }
inline int query(int x) {
int ans = 0;
for (; x >= 1; x -= lowbit(x)) ans = (ans + a[x]) % MOD;
return ans;
}
inline int query(int l, int r) { return (query(r) - query(l - 1) + MOD) % MOD; }
}a2, b2, ab;
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) {
a2.add(i, (long long)a[i] * a[i] % MOD);
b2.add(i, (long long)b[i] * b[i] % MOD);
ab.add(i, (long long)a[i] * b[i] % MOD);
}
while (q--) {
int opt; scanf("%d", &opt);
if (opt == 1) {
int l, r; scanf("%d%d", &l, &r);
int t = ab.query(l, r);
printf("%lld\n", ((long long)a2.query(l, r) * b2.query(l, r) % MOD - (long long)t * t % MOD + MOD) % MOD);
}
else if (opt == 2) {
int x, va, vb; scanf("%d%d%d", &x, &va, &vb);
a2.add(x, ((long long)va * va % MOD - (long long)a[x] * a[x] % MOD + MOD) % MOD);
b2.add(x, ((long long)vb * vb % MOD - (long long)b[x] * b[x] % MOD + MOD) % MOD);
ab.add(x, ((long long)va * vb % MOD - (long long)a[x] * b[x] % MOD + MOD) % MOD);
a[x] = va; b[x] = vb;
}
}
return 0;
}https://www.luogu.com.cn/problem/P5375
直接模拟四种数据结构即可。
#include<cstdio>
#include<queue>
#include<stack>
int n;
bool ans[4];
std::queue<int> q1;
std::stack<int> stk;
std::priority_queue<int> q2;
std::priority_queue<int, std::vector<int>, std::greater<int> > q3;
int main() {
ans[0] = ans[1] = ans[2] = ans[3] = true;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int opt, v; scanf("%d%d", &opt, &v);
if (opt == 1) {
if (ans[0]) q1.push(v);
if (ans[1]) stk.push(v);
if (ans[2]) q2.push(v);
if (ans[3]) q3.push(v);
}
else if (opt == 2) {
if (ans[0]) {
if (q1.empty() || q1.front() != v) ans[0] = false;
q1.pop();
}
if (ans[1]) {
if (stk.empty() || stk.top() != v) ans[1] = false;
stk.pop();
}
if (ans[2]) {
if (q2.empty() || q2.top() != v) ans[2] = false;
q2.pop();
}
if (ans[3]) {
if (q3.empty() || q3.top() != v) ans[3] = false;
q3.pop();
}
}
}
for (int i = 0; i < 4; i++) {
if (ans[i]) printf("Yes\n");
else printf("No\n");
}
return 0;
}https://www.luogu.com.cn/problem/P2671
由题意可得满足条件的 x 和 z 奇偶性和颜色都相同，那么可以把所以奇偶性和颜色相同的位置存在一起，问题就变为了求放在一起的所有数之间两两数对分数之和。
$$\sum_{1\le x<z\le n}(x+z)(w[x]+w[z])\\=\sum_{x=1}^n\left((n-x)x\cdot w[x]+x\sum_{z=x+1}^nw[z]+w[x]\sum_{z=x+1}^nz+\sum_{z=x+1}^nz\cdot w[x]\right)$$
于是可以预处理前缀和$O(n)$计算。总复杂度$O(n+m)$。
注意特判 x 是否等于 n。
#include<cstdio>
#include<vector>
#include<utility>
const int MOD = 10007;
int n, m, w[100100], c[100100], ans;
std::vector<std::pair<int, int> > a[100100][2];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
for (int i = 1; i <= n; i++) a[c[i]][i & 1].push_back(std::make_pair(i % MOD, w[i] % MOD));
for (int i = 1; i <= m; i++) {
for (int j = 0; j < 2; j++) {
int sumz = 0, sumwz = 0, sumzwz = 0;
for (int k = 0; k < (int)a[i][j].size(); k++)
sumz = (sumz + a[i][j][k].first) % MOD, sumwz = (sumwz + a[i][j][k].second) % MOD, sumzwz = (sumzwz + a[i][j][k].first * a[i][j][k].second % MOD) % MOD;
for (int k = 0; k < (int)a[i][j].size(); k++) {
int x = a[i][j][k].first, wx = a[i][j][k].second;
sumz = (sumz - x + MOD) % MOD, sumwz = (sumwz - wx + MOD) % MOD, sumzwz = (sumzwz - x * wx % MOD + MOD) % MOD;
if (k != (int)a[i][j].size() - 1) ans = (ans + x * wx % MOD * ((int)a[i][j].size() - 1 - k) % MOD + x * sumwz % MOD + wx * sumz % MOD + sumzwz) % MOD;
}
}
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2875
设$dp[i]$表示前 i 个位置最少要删几个字母，那么可以对于每个状态枚举单词，然后计算当这个单词从后往前匹配最少要删的字母数，如果能匹配直接转移即可。
#include<cstdio>
#include<iostream>
#include<cstring>
int m, n, dp[310], len[610];
char s[310], dic[610][30];
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d%d", &m, &n);
scanf("%s", s + 1);
for (int i = 1; i <= m; i++) scanf("%s", &dic[i][1]), len[i] = strlen(&dic[i][1]);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
for (int j = 1; j <= m; j++) {
int k = len[j], cur = i, cnt = 0;
for (; k && cur > 0; k--, cur--)
while (cur && s[cur] != dic[j][k]) cur--, cnt++;
if (!k) dp[i] = min(dp[i], dp[cur] + cnt);
}
}
printf("%d\n", dp[n]);
return 0;
}https://www.luogu.com.cn/problem/P1412
不难想到用$dp[i]$表示前 i 个星球的最大收入，但这样做，当前做出的决策会影响到以后的决策，并且当前最优解并不一定推出后面的状态的最优解。当前做出的决策会使后面所有状态的钻头能力值乘上一个常数。那么正难则反，可以反过来用$dp[i]$表示$[i,n]$的星球的最大收入，这样就满足了无后效性和最优子结构。有：
$$dp[i]=\begin{cases}\max(dp[i+1],(1-0.01k)dp[i+1]+a[i])&type[i]=1\\\max(dp[i+1],(1+0.01k)dp[i+1]-a[i])&type[i]=2\end{cases}$$
其实本质上是满足了拓扑序，使得当前决策影响到的状态和当前状态所依赖的状态"同向"。
#include<cstdio>
int n, k, c, w, type[100100], a[100100];
double dp[100100];
inline double max(double a, double b) { return a > b ? a : b; }
int main() {
scanf("%d%d%d%d", &n, &k, &c, &w);
for (int i = 1; i <= n; i++) scanf("%d%d", &type[i], &a[i]);
for (int i = n; i >= 1; i--) {
if (type[i] == 1) dp[i] = max(dp[i + 1], dp[i + 1] * (1 - 0.01 * k) + a[i]);
else if (type[i] == 2) dp[i] = max(dp[i + 1], dp[i + 1] * (1 + 0.01 * c) - a[i]);
}
printf("%.2lf\n", dp[1] * w);
return 0;
}https://www.luogu.com.cn/problem/P1439
同时交换两个序列的相同位置，最长公共子序列的长度不会变化。于是可以多次同时交换两个序列的相同位置使得序列 B 成为上升序列。这时对于序列 A，它的任意一个上升子序列都在 B 中存在，于是问题就巧妙地转化为了最长上升子序列问题，可以用各种$O(nlogn)$做法解决。
我喜欢树状数组。
#include<cstdio>
int n, a[100100], p[100100];
inline int max(int a, int b) { return a > b ? a : b; }
struct ft {
int ft[100100];
inline int lowbit(int x) { return x & -x; }
inline void assign(int x, int v) { for (; x <= n; x += lowbit(x)) ft[x] = max(ft[x], v); }
inline int query(int x) {
int ans = 0;
for (; x >= 1; x -= lowbit(x)) ans = max(ans, ft[x]);
return ans;
}
}ft;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
p[x] = i;
}
for (int i = 1; i <= n; i++) ft.assign(p[a[i]], ft.query(p[a[i]] - 1) + 1);
printf("%d\n", ft.query(n));
return 0;
}https://www.luogu.com.cn/problem/P3146
设$dp[i][j]$表示区间$[i,j]$最大能合并成几。若为 0 则表示区间不能合并为一个数。那么有：
$$dp[i][j]=\max_{k=i}^{j-1}{dp[i][k]+1\ |\ dp[i][k]=dp[k+1][j]}$$
#include<cstdio>
int n, a[250], dp[250][250], ans;
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &dp[i][i]);
for (int l = 2; l <= n; l++)
for (int i = 1; i + l - 1 <= n; i++) {
int j = i + l - 1;
for (int k = i; k < j; k++)
if (dp[i][k] == dp[k + 1][j]) dp[i][j] = max(dp[i][j], dp[i][k] + 1);
ans = max(ans, dp[i][j]);
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6509
设$f[i][j]$表示前 i 位加起来是 j 最少要添加几个加号，若为$\inf$则表示没有可行方案。
注意直接把一段连续的 0 划分给右侧的数不一定是最优的，因此还要枚举划分几个 0 ，这样转移就变成了$O(n)$的，不行。可以再次发扬预处理精神，设$g[i][j]=\min_{k=x}^if[k][j]$，其中 x 是从位置 i 往左第一个非 0 位置。这样转移就变成$O(1)$的了。然后还要记录方案，注意 g 也要记录方案，总之非常绕，把我绕晕了，调了好几个小时。
总之不知道怎么转移时，先问问自己把定义搞清楚了没。理清定义对此很有帮助。
#include<cstdio>
#include<cstring>
int b, df[1010][5010], dg[1010][5010], n, m, f[1010][5010], g[1010][5010];
char s[1010];
inline int bit(int x) {
int ans = 0;
for (; x; x /= 10) ans++;
return ans;
}
inline int toint(int l, int r) {
int ans = 0;
for (int i = l; i <= r; i++) ans = ans * 10 + s[i] - '0';
return ans;
}
void print(int x, int k) {
if (!x) return;
print(df[x][k] - 1, k - toint(df[x][k], x));
for (int i = df[x][k]; i <= x; i++) printf("%c", s[i]);
if (x ^ n) printf("+");
else printf("=%d\n", b);
}
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%[^=]=%d", s + 1, &b);
n = strlen(s + 1); m = bit(b);
memset(f, 0x3f, sizeof f); memset(g, 0x3f, sizeof g);
f[0][0] = g[0][0] = 0;
dg[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int k = 0; k <= b; k++) {
for (int j = max(1, i - m + 1); j <= i; j++) {
int d = toint(j, i);
if (k < d) continue;
if (f[j - 1][k - d] + 1 < f[i][k]) f[i][k] = f[j - 1][k - d] + 1, df[i][k] = j;
if (g[j - 1][k - d] + 1 < f[i][k]) f[i][k] = g[j - 1][k - d] + 1, df[i][k] = dg[j - 1][k - d];
}
if (s[i] == '0') {
if (g[i - 1][k] < f[i][k]) g[i][k] = g[i - 1][k], dg[i][k] = dg[i - 1][k];
else g[i][k] = f[i][k], dg[i][k] = i + 1;
}
else g[i][k] = f[i][k], dg[i][k] = i + 1;
}
}
print(n, b);
return 0;
}https://www.luogu.com.cn/problem/P4054
二维树状数组模板题。不到十分钟写完，一遍过。
#include<cstdio>
int n, m, q, a[310][310];
struct ft {
int ft[310][310];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int y, int v) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j)) ft[i][j] += v;
}
inline int query(int x, int y) {
int ans = 0;
for (int i = x; i >= 1; i -= lowbit(i))
for (int j = y; j >= 1; j -= lowbit(j)) ans += ft[i][j];
return ans;
}
}ft[101];
inline int query(int x1, int y1, int x2, int y2, int c) { return ft[c].query(x2, y2) - ft[c].query(x2, y1 - 1) - ft[c].query(x1 - 1, y2) + ft[c].query(x1 - 1, y1 - 1); }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int x; scanf("%d", &x);
a[i][j] = x;
ft[x].add(i, j, 1);
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int opt; scanf("%d", &opt);
if (opt == 1) {
int x, y, c; scanf("%d%d%d", &x, &y, &c);
ft[a[x][y]].add(x, y, -1);
ft[c].add(x, y, 1);
a[x][y] = c;
}
else if (opt == 2) {
int x1, x2, y1, y2, c; scanf("%d%d%d%d%d", &x1, &x2, &y1, &y2, &c);
printf("%d\n", query(x1, y1, x2, y2, c));
}
}
return 0;
}https://www.luogu.com.cn/problem/P2647
看到这个问题，我不禁想起了 01 背包。这个问题和 01 背包的区别在于当前决策对后面的状态有影响。若选择了物品 i ，且后来又选了 n 个物品，那么这个物品对答案产生的贡献为$in$。
其实我是看洛谷日报上讲排序不等式找到这道题的。
排序不等式是说：有两个长度为 n 的从小到大排列的有序序列 a 和 b，若 p 是任意一个长度为 n 的排列，则有：
$$\sum_{i=1}^na_ib_{n-i+1}\le\sum_{i=1}^na_ib_{p_i}\le\sum_{i=1}^na_ib_i$$
回到本题，对于某个选择物品的方案，选的物品个数是确定的，那么将所有选的物品的$r_i$看作一个序列，每个物品的$r_i$影响的物品个数是递减的，那么由排序不等式可以得出，不管最后的方案是什么，把物品按照$r_i$从小到大排序总是优的。
那么先把物品排一遍序。因为当前决策对后面的状态有影响，所以正难则反，可以和经营与开发那道题一样倒着 DP，设$dp[j]$表示选了 j 个物品时的最大收益，那么有：
$$dp[j]=\max(dp[j],dp[j-1]+w[i]-(j-1)r[i])$$
#include<cstdio>
#include<algorithm>
int n, dp[3010], ans;
struct item {
int w, r;
bool operator < (const item &b) const { return r < b.r; }
}itm[3010];
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &itm[i].w, &itm[i].r);
std::sort(itm + 1, itm + n + 1);
for (int i = n; i >= 1; i--)
for (int j = n - i + 1; j >= 1; j--)
dp[j] = max(dp[j], dp[j - 1] + itm[i].w - itm[i].r * (j - 1));
for (int i = 0; i <= n; i++) ans = max(ans, dp[i]);
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1687
题意不清，实际上题目要求能量要按顺序获取，因此贪心是不对的。那么可以设$f[i][j]$表示前 i 个位置拿了 j 个需要的最少天数，$g[i][j]$表示前 i 个位置拿了 j 个且天数最少时最后一天的最少占用时间。然后分情况讨论即可，理清思路：对于每个状态有三种决策，分别是不取、合并到前一天和划分到新的一天。然后想好这三种决策对应的转移。
另外注意特判两种决策的所需最少天数相同时，要比较占用时间，取占用时间更少的决策。当这个位置可以合并到前一天时，划分到新的一天一定不优，因此只需要比较合并到前一天和不选两种决策；当这个位置不能合并到前一天时，只需要比较划分到新一天和不选两种决策。
#include<cstdio>
#include<cstring>
int n, k, a[3010], f[3010][3010], g[3010][3010], ans = 0x3fffffff;
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
memset(f, 0x3f, sizeof f);
for (int i = 0; i <= n; i++) f[i][0] = 0, g[i][0] = 119;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) {
if (119 - g[i - 1][j - 1] >= a[i]) {
if (f[i - 1][j - 1] < f[i - 1][j] || (f[i - 1][j - 1] == f[i - 1][j] && g[i - 1][j - 1] + a[i] < g[i - 1][j])) f[i][j] = f[i - 1][j - 1], g[i][j] = g[i - 1][j - 1] + a[i];
else f[i][j] = f[i - 1][j], g[i][j] = g[i - 1][j];
}
else if (a[i] <= 119) {
if (f[i - 1][j - 1] + 1 < f[i - 1][j] || (f[i - 1][j - 1] + 1 == f[i - 1][j] && a[i] < g[i - 1][j])) f[i][j] = f[i - 1][j - 1] + 1, g[i][j] = a[i];
else f[i][j] = f[i - 1][j], g[i][j] = g[i - 1][j];
}
else f[i][j] = f[i - 1][j], g[i][j] = g[i - 1][j];
}
for (int i = 1; i <= n; i++) ans = min(ans, f[i][k]);
if (ans ^ 0x3f3f3f3f) printf("%d\n", ans);
else printf("You can't do it.\n");
return 0;
}