CSP-S 模拟 191102

$n\le 2333$ 将最后形成的三元组分类 三个一样的，两个一样的，三个都不一样的分别计算就比较方便 三个一样的和两个一样的可以 $O(n)$ 三个都不一样显然枚举两个然后算出另一个

---

关于手写一些可以实现$map$功能的东西 可以用一个类似邻接表的东西存

int first[Mod], nxt[N], to[N], val[N], tot; int ask(int p){ int x = p % Mod; for(int i = first[x]; i; i = nxt[i]) if(to[i] == p) return val[i]; return 0; } void add(int p, int v){ int x = p % Mod; for(int i = first[x]; i; i = nxt[i]){ if(to[i] == p) {val[i] += v; return;} } nxt[++tot] = first[x], first[x] = tot, to[tot] = p, val[tot] = v; }

也可以冲突就暴力挪位

struct MAP{ static cs int Mod = 1e7+9; int key[Mod], val[Mod]; Map(){ memset(key, -1, sizeof(key)); } int pos(int k){ int h = k % Mod; while(key[h] != -1 && key[h] != k) h = h+1 == Mod ? 0 : h+1; return h; } void ins(int k){ int h = pos(k); if(key[h] == -1) key[h] = k, val[h] = 1; else val[h]++; } int find(int k){ int h = pos(k); return key[h] == -1 ? 0 : val[h]; } };

也可以离散化然后暴力二分

struct MAP{ int b[N], siz, val[N]; void build(){ sort(b + 1, b + siz + 1); siz = unique(b + 1, b + siz + 1) - (b + 1); } int find(int x){ int l = 1, r = siz; while(l < r){ int mid = (l+r) >> 1; if(b[mid] >= x) r = mid; else l = mid + 1; } return l; } void add(int x){ val[find(x)]++; } int ask(int x){ int l = find(x); if(b[l] == x) return val[l]; return 0; } };

---

然后发现快速幂的复杂度是满的 $log(1e9)$，可以改成常数更小的 $exgcd$ 还可以预处理逆元，然后 $n^2$ 枚举的时候就不用快速幂只剩下一个常数很小的二分 复杂度 $O(n^{2}log(n))$

#include<bits/stdc++.h> #define cs const using namespace std; namespace IO{ inline char gc(){ static cs int Rlen = 1 << 22 | 1; static char buf[Rlen], *p1, *p2; return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, Rlen, stdin), p1 == p2) ? EOF : *p1++; } int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)) { ch = gc(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt * 10 + (ch-'0'), ch = gc(); return cnt * f; } } using namespace IO; typedef long long ll; cs int N = 2500; int n, p, a[N], b[N], siz, inv[N]; ll ans; int add(int a, int b){ return a + b >= p ? a + b - p : a + b; } int mul(int a, int b){ return 1ll * a * b % p; } int ksm(int a, int b){ int ans=1; for(;b;b>>=1, a=mul(a,a)) if(b&1) ans=mul(ans,a); return ans; } bool vis[N]; int ps[N], tim[N]; struct MAP{ int b[N], siz; int val[N]; void build(){ sort(b + 1, b + siz + 1); siz = unique(b + 1, b + siz + 1) - (b + 1); } int find(int x){ int l = 1, r = siz; while(l < r){ int mid = (l+r) >> 1; if(b[mid] >= x) r = mid; else l = mid + 1; } return l; } void add(int x){ val[find(x)]++; } int ask(int x){ int l = find(x); if(b[l] == x) return val[l]; return 0; } }bin, sum; int main(){ n = read(), p = read(); for(int i = 1; i <= n; i++){ a[i] = read(); bin.b[++bin.siz] = a[i]; sum.b[++sum.siz] = a[i] % p; b[++siz] = a[i]; inv[i] = ksm(a[i] % p, p - 2); } sort(b + 1, b + siz + 1); siz = unique(b + 1, b + siz + 1) - (b + 1); bin.build(); sum.build(); for(int i = 1; i <= n; i++) ps[i] = bin.find(a[i]); for(int i = 1; i <= n; i++){ if(!tim[ps[i]]) sum.add(a[i] % p); tim[ps[i]]++; } // three of them are the same for(int i = 1; i <= n; i++){ if(tim[ps[i]] >= 3 && !vis[ps[i]]){ vis[ps[i]] = true; if(mul(inv[i], mul(inv[i], inv[i])) == 1) ++ans; } } // two of them are the same memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++){ if(tim[ps[i]] >= 2 && !vis[ps[i]]){ vis[ps[i]] = true; int nx = mul(inv[i], inv[i]); ans += sum.ask(nx); if(a[i] % p == nx) ans--; } } // each of them is different memset(vis, 0, sizeof(vis)); ll ret = 0; for(int i = 1; i <= siz; i++) inv[i] = ksm(b[i] % p, p - 2); for(int i = 1; i <= siz; i++){ for(int j = i + 1; j <= siz; j++){ int ni = b[i] % p, nj = b[j] % p; int nx = mul(inv[i], inv[j]); ret += sum.ask(nx); if(ni == nx) ret--; if(nj == nx) ret--; } } cout << ans + ret / 3; return 0; }

---

$n\le 1e5$ 考场的垃圾做法： 发现物品按 $w$ 排序就是选一个 $v$ 的最长不下降序列并且满足选出来的每一个 $w$ 在另一边都有一个 $\ge$ 它的映射，另一边也排个序，$f_{i,j}$ 表示这边选到 $i$另一边选到 $j$ 的最长长度 $f_{i,j}=max(f_{p,k})(v_p\le v_i,k\le j-1)$，二维树状数组优化转移

---

正解：考虑贪心，显然如果最后的长度是 $len$ 的话选最大的 $len$ 个一定是最优的 考虑对每一个 $i$ 求出它向后的最长长度 $len$ 并且求出可以装下 $i$ 的个数 $cnt$，那么合法的最长长度就是 $min(len,cnt)$，从后向前 $dp$，动态维护装的下的个数，树状数组优化转移即可 有时候不能莽起 dp，还是要从贪心的角度考虑

#include<bits/stdc++.h> #define cs const using namespace std; int read(){ int x = 0, f = 1; char c = 0; while(!isdigit(c)){ c = getchar(); if(c == '-')f = -1;} while(isdigit(c)) x = x*10 + (c-'0'), c = getchar(); return x * f; } typedef long long ll; cs int N = 1e5 + 5; int T, n, m, t[N], b[N], siz; struct BAG{ int w, v;}a[N]; bool cmp(BAG a, BAG b){ return a.w < b.w || (a.w == b.w && a.v < b.v); } struct BIT{ int c[N]; void clear(){ memset(c, 0, sizeof(c)); } void add(int x, int v){ for(;x;x-=x&-x) c[x] = max(c[x], v); } int ask(int x){ int ans=0; for(;x<=siz;x+=x&-x) ans = max(ans, c[x]); return ans; } }bit; void Solve(){ bit.clear(); siz = 0; n = read(); for(int i = 1; i <= n; i++){ a[i].w = read(); a[i].v = read(); b[++siz] = a[i].v; } sort(a + 1, a + n + 1, cmp); reverse(a + 1, a + n + 1); sort(b + 1, b + siz + 1); siz = unique(b + 1, b + siz + 1) - (b + 1); m = read(); for(int i = 1; i <= m; i++){ t[i] = read(); } sort(t + 1, t + m + 1); reverse(t + 1, t + m + 1); int ans = 0, p = 0; for(int i = 1; i <= n; i++){ while(p + 1 <= m && t[p + 1] >= a[i].w) ++p; int x = lower_bound(b + 1, b + siz + 1, a[i].v) - b; int f = min(bit.ask(x) + 1, p); bit.add(x, f); ans = max(ans, f); } cout << ans << '\n'; } int main(){ T = read(); while(T--) Solve(); return 0; }

---

$n\le 500$

---

考场的垃圾做法： $f_{siz,dep}$ 表示大小和深度为 $siz,dep$ 的方案数，暴力枚举拆分，以及拆分出来的深度 $f_{siz,dep}={\sum }_{i=1}^{siz-1}{\sum }_{j=1}^{siz-i-1}{f}_{siz-i-1,j}{\sum }_{k=1}^i{f}_{i,k}[max(j,k+1)=1]$ 然后还要重新分配编号，考场上思维不严谨的我写的 $\left(\genfrac{}{}{0ex}{}{siz-1}{k}\right)$ 请睁大眼睛看一下我的预处理

c[0][0] = 1; for(int i = 1; i <= n; i++){ c[i][i] = 1; for(int j = 1; j <= i; j++){ c[i][j] = add(c[i-1][j], c[i-1][j-1]); } }

手玩一下发现这样预处理正好把杨辉三角挪了一位，所以实际上乘的系数是 $\left(\genfrac{}{}{0ex}{}{siz-2}{k-1}\right)$ 而 $std$ 正好成的是 $\left(\genfrac{}{}{0ex}{}{siz-2}{k-1}\right)$，然后我就歪打正着了（雾） 言归正传，钦定是原来的取到 $dep$ 还是后来拼接的取到 $dep$ 就可以前缀和优化转移

---

说一下乘 $\left(\genfrac{}{}{0ex}{}{siz-1}{k}\right)$ 为什么有问题，因为当前拼接的子树很有可能是跟之前的同构，显然会算重 我们直接钦定当前拼接上去的子树的根是次小，这样相当于对儿子进行了排序，这样就不会算重了 既然钦定了根是最小，当前子树的根是次小，那么方案数就是将剩下的重新排列的方案数即 $\left(\genfrac{}{}{0ex}{}{siz-2}{k-1}\right)$ 然后发现前缀和非常丑，直接按套路把状态定义为大小为 $siz$ 深度 $\le dep$ 的方案数 $$f_{siz,dep}=\sum _{i=1}^{siz-1}{f}_{siz-i-1,dep}\ast f_{i,dep-1}\ast \left(\genfrac{}{}{0ex}{}{siz-2}{i-1}\right)$$

---

考虑直接枚举子树的拼接，枚举子树个数以及每个子树的大小 $$f[d][n]=\sum _{k=1}^{n-1}\frac{1}{k!}\sum _{{\sum }_{i=1}^k{b}_i=n-1}\frac{(n-1)!}{\prod b_i!}\prod _{i=1}^{k}f[d-1][b_i]$$ $$\frac{f[d][n]}{(n-1)!}=\sum _{k=1}^{n-1}\frac{1}{k!}\sum _{{\sum }_{i=1}^k{b}_i=n-1}\frac{1}{\prod b_i!}\prod _{i=1}^{k}f[d-1][b_i]$$ 注意到后面一坨的组合意义是集合间带标号的拼接，上指数型生成函数 令 $f_d(x)={\sum }_{i=0}^{\infty }\frac{f[d][i]}{i!}{x}^i$ $$\sum _{n=0}^{\infty }\frac{f[d][n]}{(n-1)!}{x}^{n-1}=\sum _{n=0}^{\infty }\sum _{k=1}^{n-1}\frac{1}{k!}\sum _{{\sum }_{i=1}^k{b}_i=n-1}\prod _{i=1}^k\frac{f[d-1][b_i]}{b_i!}{x}^{b_i}$$ $$=\sum _{k=1}^{\infty }\frac{1}{k!}\sum _{b_i=0}^{\infty }\prod _{i=1}^k\frac{f[d-1][b_i]}{b_i!}{x}^{b_i}$$ $$=\sum _{k=1}^{\infty }\frac{1}{k!}\prod _{i=1}^k\sum _{b_i=0}^{\infty }\frac{f[d-1][b_i]}{b_i!}{x}^{b_i}$$ $$=\sum _{k=1}^{\infty }\frac{1}{k!}{f}_{d-1}(x{)}^k=exp(f_{d-1}(x))$$ 而 $$\sum _{n=0}^{\infty }\frac{f[d][n]}{(n-1)!}{x}^{n-1}=f_d(x{)}^{\prime }=exp(f_{d-1}(x))$$ 所以 $$f_d(x)=\int exp(f_{d-1}(x))dx$$ 多项式全家桶

---

#include<bits/stdc++.h> #define cs const using namespace std; int read(){ int x = 0, f = 1; char c = 0; while(!isdigit(c)){ c = getchar(); if(c == '-')f = -1;} while(isdigit(c)) x = x*10 + (c-'0'), c = getchar(); return x * f; } typedef long long ll; cs int N = 505; int n, k, L, R; cs int Mod = 998244353; int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; } int mul(int a, int b){ return 1ll * a * b % Mod; } void Add(int &a, int b){ a = add(a, b); } int c[N][N]; bool ban[N]; int f[N][N]; int main(){ n = read(); k = read(); for(int i = 1; i <= k; i++) ban[read()] = true; L = read(); R = read(); c[0][0] = 1; for(int i = 1; i <= n; i++){ c[i][0] = 1; for(int j = 1; j <= i; j++){ c[i][j] = add(c[i-1][j], c[i-1][j-1]); } } f[1][1] = ban[1] ? 0 : 1; for(int dep = 2; dep <= n; dep++){ for(int siz = 1; siz <= n; siz++){ if(siz == 1){ f[siz][dep] = 1; continue; } for(int k = 1; k < siz; k++){ Add(f[siz][dep], mul(c[siz - 2][k - 1], mul(f[siz - k][dep], f[k][dep - 1]))); } } for(int siz = 1; siz <= n; siz++) if(ban[siz]) f[siz][dep] = 0; } for(int i = L; i <= R; i++) cout << add(f[n][i], Mod - f[n][i-1]) << " "; return 0; } #include<bits/stdc++.h> #define cs const using namespace std; int read(){ int x = 0, f = 1; char c = 0; while(!isdigit(c)){ c = getchar(); if(c == '-')f = -1;} while(isdigit(c)) x = x*10 + (c-'0'), c = getchar(); return x * f; } typedef long long ll; cs int N = 505; int n, k, L, R; cs int Mod = 998244353; int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; } int mul(int a, int b){ return 1ll * a * b % Mod; } void Add(int &a, int b){ a = add(a, b); } int ksm(int a, int b){ int ans = 1; for(;b;b>>=1, a = mul(a, a)) if(b&1) ans = mul(ans, a); return ans; } int a[N]; #define poly vector<int> poly f[N]; cs int K = 13; poly w[K + 1]; int inv[1 << K | 5]; int bit, up, rev[1 << K | 5]; void prework(){ for(int i = 1; i <= K; i++) w[i].resize(1 << i - 1); int wn = ksm(3, (Mod-1)/(1<<K)); w[K][0] = 1; for(int i = 1; i < (1 << K-1); i++) w[K][i] = mul(w[K][i-1], wn); for(int i = K-1; i; i--) for(int j = 0; j < (1 << i-1); j++) w[i][j] = w[i + 1][j << 1]; inv[0] = inv[1] = 1; for(int i = 2; i <= (1 << K); i++) inv[i] = mul(Mod-Mod/i, inv[Mod%i]); } void init(int len){ bit = 0; up = 1; while(up < len) up <<= 1, bit++; for(int i = 0; i < up; i++) rev[i] = (rev[i>>1]>>1) | ((i&1)<<(bit-1)); } void NTT(poly &a, int typ){ for(int i = 0; i < up; i++) if(i < rev[i]) swap(a[i], a[rev[i]]); for(int i = 1, l = 1; i < up; i <<= 1, l++) for(int j = 0; j < up; j += (i << 1)) for(int k = 0; k < i; k++){ int x = a[k + j], y = mul(w[l][k], a[k + j + i]); a[k + j] = add(x, y); a[k + j + i] = add(x, Mod - y); } if(typ == -1){ reverse(a.begin() + 1, a.end()); for(int i = 0; i < up; i++) a[i] = mul(a[i], inv[up]); } } poly operator * (poly a, poly b){ int len = a.size() + b.size() - 1; init(len); a.resize(up); b.resize(up); NTT(a, 1); NTT(b, 1); for(int i = 0; i < up; i++) a[i] = mul(a[i], b[i]); NTT(a, -1); a.resize(len); return a; } poly Inv(poly a, int lim){ int n = a.size(); poly c, b(1, ksm(a[0], Mod-2)); for(int len = 4; (len >> 2) < lim; len <<= 1){ init(len); c.resize(len >> 1); for(int i = 0; i < (len >> 1); i++) c[i] = i < n ? a[i] : 0; c.resize(up); b.resize(up); NTT(c, 1); NTT(b, 1); for(int i = 0; i < up; i++) b[i] = mul(b[i], add(2, Mod - mul(b[i], c[i]))); NTT(b, -1); b.resize(len >> 1); } b.resize(lim); return b; } poly deriv(poly a){ for(int i = 0; i+1 < a.size(); i++) a[i] = mul(a[i + 1], i + 1); a.pop_back(); return a; } poly integ(poly a){ a.push_back(0); for(int i = a.size() - 1; i; i--) a[i] = mul(a[i - 1], inv[i]); a[0] = 0; return a; } poly ln(poly a, int len){ a = integ(deriv(a) * Inv(a, len)); a.resize(len); return a; } poly exp(poly a, int len){ int n = a.size(); poly c, b(1, 1); for(int i = 2; (i >> 1) < len; i <<= 1){ c = ln(b, i); c[0] = add(c[0], Mod-1); for(int j = 0; j < i; j++) c[j] = add(j < n ? a[j] : 0, Mod - c[j]); b = b * c; b.resize(i); } b.resize(len); return b; } int main(){ prework(); n = read(); k = read(); for(int i = 1; i <= k; i++) a[i] = read(); L = read(); R = read(); f[1].resize(n + 1); f[1][1] = 1; f[0].resize(n + 1); for(int i = 2; i <= n; i++){ f[i] = integ(exp(f[i - 1], n + 1)); f[i].resize(n + 1); for(int j = 1; j <= k; j++) f[i][a[j]] = 0; } int fac = 1; for(int i = 1; i <= n; i++) fac = mul(fac, i); for(int i = L; i <= R; i++) cout << mul(fac, add(f[i][n], Mod - f[i - 1][n]))<< " "; return 0; }