sx题解
name
签到题。原题为 ARC210A。
显然考虑用差分数组来刻画严格单调的条件，具体而言差分数组每一位都要求大于等于 \(1\) 那么此序列单调递增。在 \(p\) 位置增加 \(v\) 相当于将当前的差分数组 \(c_p\gets c_p + v, c_{p+1}\gets c_{p+1} - v\)。很容易想到对着这个流程模拟，如果不够的话就在一开始加。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6;
int n, q, c[N + 10], d[N + 10];
signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int ans = 0;cin >> n >> q;for(int i = 1; i <= n; i++) d[i] = c[i] = 1;for(int i = 1, a, b; i <= q; i++) {cin >> a >> b;if(a == n) {//特判c[a] += b;continue;}if(c[a + 1] - b < 1) {//如果不够int delt = b - c[a + 1] + 1;c[a + 1] += delt, d[a + 1] += delt;//给原来的加}c[a] += b;c[a + 1] -= b;}for(int i = 1; i <= n; i++)d[i] += d[i - 1], ans += d[i];cout << ans << '\n';
}
song
签到题，原题为 ARC157C。
对于平方考虑组合意义为随便选两个缝隙，所以设 \(f[x, y, S]\) 为走到 \((x, y)\) 位置，目前选择缝隙状态为 \(S\)。直接转移。
#include <bits/stdc++.h>
using namespace std;
const int N = 2000, Mod = 998244353;
void upd(int &x, int y) {x = ((x + y >= Mod) ? (x + y - Mod) : (x + y));
}
const int dx[2] = {0, 1};
const int dy[2] = {1, 0};
char ch[N + 10][N + 10];
int f[N + 3][N + 3][4], n, m;
int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> ch[i][j];f[1][1][0] = 1;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {for(int S = 0; S < 4; S++) {for(int d = 0; d < 2; d++) {int xx = i + dx[d], yy = j + dy[d];if(xx > n || yy > m) continue;if(ch[i][j] == 'Y' && ch[xx][yy] == 'Y') {for(int T = 0; T < 4; T++) {if(S & T) continue;upd(f[xx][yy][S | T], f[i][j][S]);}}else upd(f[xx][yy][S], f[i][j][S]);}}}}cout << f[n][m][3] << '\n';
}
recall
非常好的题目，但是确实也算是典中典，原题 P4448
原题放了 \(O(n^3)\) 做法过，我个人认为 \(O(n^3)\) 做法对于 dp 状态的设计是相当值得学习的，但是似乎没有 \(O(n^2)\) 做法好想？
考虑容斥，钦定 \(k\) 个位置颜色相同。放到每个颜色里面去，如果这个颜色 \(i\) 贡献出 \(t\) 个钦定的颜色相同段，那么提供 \((-1)^{a_i - t }\) 的容斥系数，划分方式有 \(a_i!\binom{a_i - 1}{t - 1}\)。最终颜色贡献 \(t_1, t_2, \dots t_m\) 的颜色段，那么总贡献为 \(\binom{t_1 + t_2 + \dots + t_m}{t_1, t_2, \dots, t_m}\)。直接 dp，设 \(f[i, j]\) 为前 \(i\) 种颜色，\(t\) 之和为 \(j\)。上下界做好就是 \(O(n^2)\) 的。
#include <bits/stdc++.h>
using namespace std;
const int N = 2000, Mod = 998244353;
int fac[N + 10], invf[N + 10];
int qpow(int n, int m) {int res = 1;while(m) {if(m & 1) res = 1ll * res * n % Mod;n = 1ll * n * n % Mod;m >>= 1;}return res;
}
int C(int n, int m) {return 1ll * fac[n] * invf[m] % Mod * invf[n - m] % Mod;
}
void upd(int &x, int y) {x = ((x + y >= Mod) ? (x + y - Mod) : (x + y));
}
int f[N + 3][N + 3], a[N + 10], m;
int main() {fac[0] = 1; for(int i = 1; i <= N; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;invf[N] = qpow(fac[N], Mod - 2); for(int i = N - 1; i >= 0; i--) invf[i] = 1ll * invf[i + 1] * (i + 1) % Mod;cin >> m;for(int i = 1; i <= m; i++) cin >> a[i];f[0][0] = 1;int lim = 0;for(int i = 0; i < m; i++) {for(int j = 0; j <= lim; j++) {for(int t = 1; t <= a[i + 1]; t++) {int w = (((a[i + 1] - t) % 2 == 0) ? (1) : (Mod - 1));upd(f[i + 1][j + t], 1ll * w * fac[a[i + 1]] % Mod * C(a[i + 1] - 1, t - 1) % Mod * invf[t] % Mod * f[i][j] % Mod);}}lim += a[i + 1];}int sum = 0;for(int i = 0; i <= lim; i++) upd(sum, 1ll * f[m][i] * fac[i] % Mod);cout << sum << '\n';
}
article
一条显然的性质：固定开头的前缀，前缀或最多只有 \(O(\log V)\) 种。
考虑分治，对于区间 \([l, r]\) 拆成 \([l, mid]\) 和 \([mid + 1, r]\)，如果固定开头或者结尾，可能成为答案的 \(l, r\) 就都只有 \(O(\log V)\) 种，对于一个 \(mid\) 就是 \(O(\log^2 V)\) 种，利用分治可以拆分出所有这样的区间。（不用分治也行，可以直接枚举分界点 \(mid\)，用 set 存储每个二进制位出现的位置，也是 \(O(n\log^2 V)\) 种可能的区间）显然答案只可能在其中产生。设 \(t_i\) 为长度小于等于 \(i\) 的最大区间或。在上面二分即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5, M = 2e6;
int read() {int k = 0; char ch = getchar();while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9') {k = k * 10 + ch - '0';ch = getchar();}return k;
}
void write(int x) {if(!x) {putchar('0');return ;}int tmp[30], len = 0;while(x) tmp[++len] = x % 10, x /= 10;for(int i = len; i >= 1; i--) putchar(char(tmp[i] + '0'));
}struct node {int len, val;
};
int t[N + 10], a[N + 10], n, q;
void solve(int l, int r) {if(l == r) {t[1] = max(t[1], a[l]);return ;}int mid = (l + r) >> 1;int asum = 0, bsum = 0;vector <node> sa, sb;for(int i = mid; i >= l; i--) {if((asum | a[i]) > asum) {asum |= a[i];sa.push_back((node){i, asum});}}for(int i = mid + 1; i <= r; i++) {if((bsum | a[i]) > bsum) {bsum |= a[i];sb.push_back((node){i, bsum});}}for(int i = 0; i < sa.size(); i++) {for(int j = 0; j < sb.size(); j++)t[sb[j].len - sa[i].len + 1] = max(t[sb[j].len - sa[i].len + 1], (sb[j].val | sa[i].val));}solve(l, mid);solve(mid + 1, r);
}
namespace bit {int lowbit(int x) {return x & (-x);}int cmax[N + 10];void upd(int pos, int val) {while(pos <= n)cmax[pos] = max(cmax[pos], val), pos += lowbit(pos);}int qry(int k) {int pos = 0, rest = 0;for(int i = 17; i >= 0; i--)if(pos + (1 << i) <= n && max(rest, cmax[pos + (1 << i)]) < k)rest = max(rest, cmax[pos + (1 << i)]),pos += (1 << i);return pos + 1;}
}
int main() {// freopen("read.in", "r", stdin);n = read(), q = read();for(int i = 1; i <= n; i++)a[i] = read();solve(1, n);for(int i = 1; i <= n; i++)t[i] = max(t[i], t[i - 1]),bit::upd(i, t[i]);for(int i = 1; i <= q; i++) {int k; k = read();int ans = bit::qry(k);if(ans == n + 1) puts("DUDUDU");else write(ans), putchar('\n');}
}