猜猜为什么四五天没更博了？攒了个大的。
非常好 OpenCup，10 个 998244353，爱来自陶瓷❤
快写死我了，终于写完了。
十道题里只有三道题是自己做出来的。我好废物。
A. Ascending Matrix
开 幕 雷 击。
首先考虑没有限制怎么做。由于优秀的单调性，我们可以对于每一个数 \(v\) 考虑将 \([1, v]\) 与 \([v + 1, n]\) 的数划分开，划分的形状一定是从 \((n, 0)\) 到 \((0, m)\) 的一条路径。我们发现，每一种矩阵可以用这样的方式与 \(k-1\) 条从 \((n, 0)\) 到 \((0, m)\) 的互不穿过的路径进行对应，那么我们相当于统计这样的路径的数量。容易想到 LGV 引理，所以考虑将路径向右下平移，将第 \(i\) 条路径平移至 \((n + i, i) \to (i, m + i)\)，这样问题就转化成了互不相交的 \(k-1\) 条路径计数，直接 LGV 引理即可。
考虑 \(a_{r, c} = v\) 的限制。令点 \(p=(r+v-2, c+v-2)\)，那么我们的限制相当于是第 \(v\) 条路径必须在点 \(p\) 下方，第 \(v-1\) 条路径必须在点 \(p\) 上方，且没有路径经过点 \(p\)。我们可以通过加入一个元 \(x\) 来刻画这个限制，对于在 \(p\) 上方的路径，我们给权值乘上一个 \(x\)，这样我们的限制就变成了求路径权值和的 \(v-1\) 次系数。具体来讲，我们给 \(p\) 点所在的对角线上的每一个点乘上一个权值，\(p\) 上方的点乘 \(x\)，\(p\) 乘 \(0\)，\(p\) 下方的点乘 \(1\)。计算方案数时，我们枚举经过这条对角线上的哪个点，然后乘上相应的权值即可计算。
当然我们肯定不能直接算多项式行列式，我们可以带 \(k+1\) 个点值进去然后再把多项式插出来，复杂度 \(O(k^4)\)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305, P = 998244353;
int n, m, k, r, c, v;
int fac[MAXN << 1], inv[MAXN << 1];
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % P;
inv[n] = qpow(fac[n], P - 2);
for (int i = n; i >= 1; i--)
inv[i - 1] = 1ll * inv[i] * i % P;
assert(inv[0] == 1);
}
int C(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return 1ll * fac[n] * inv[m] % P * inv[n - m] % P;
}
int calc(int x1, int y1, int x2, int y2) {
return C(x1 - x2 + y2 - y1, x1 - x2);
}
int f[MAXN][MAXN], fx[MAXN][MAXN];
int a[MAXN][MAXN];
int y[MAXN];
int det() {
int ans = 1;
for (int i = 0; i < k; i++) {
int p = -1;
for (int j = i; j < k; j++) if (a[j][i]) {
p = j;
break;
}
if (p == -1) return 0;
if (p != i) ans *= -1, swap(a[i], a[p]);
for (int j = i + 1; j < k; j++) {
int inv = 1ll * a[j][i] * qpow(a[i][i], P - 2) % P;
for (int l = i; l < k; l++) {
a[j][l] = (a[j][l] - 1ll * inv * a[i][l] % P + P) % P;
}
}
}
for (int i = 0; i < k; i++)
ans = 1ll * ans * a[i][i] % P;
return (ans + P) % P;
}
int p[MAXN], q[MAXN];
int main() {
init(600);
scanf("%d%d%d%d%d%d", &n, &m, &k, &r, &c, &v);
r += v - 2, c += v - 2, k--;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
f[i][j] = calc(n + i, i, j, m + j);
for (int d = 0; r - d >= 0 && c - d >= 0; d++) {
int x = 1ll * calc(n + i, i, r - d, c - d) * calc(r - d, c - d, j, m + j) % P;
f[i][j] = (f[i][j] - x + P) % P;
if (d) fx[i][j] = (fx[i][j] + x) % P;
}
}
}
for (int i = 0; i <= k; i++) {
memset(a, 0, sizeof a);
for (int x = 0; x < k; x++) {
for (int y = 0; y < k; y++) {
a[x][y] = (f[x][y] + 1ll * fx[x][y] * i) % P;
}
}
y[i] = det();
}
int ans = 0;
for (int i = 0; i <= k; i++) {
memset(p, 0, sizeof p);
p[0] = y[i];
for (int j = 0; j <= k; j++) if (j != i) {
int inv = qpow(j - i, P - 2);
memset(q, 0, sizeof q);
for (int l = 0; l <= k; l++) {
q[l] = (q[l] + 1ll * j * inv % P * p[l] % P + P) % P;
if (l) q[l] = (q[l] - 1ll * inv * p[l - 1] % P + P) % P;
}
memcpy(p, q, sizeof q);
}
ans = (ans + p[v - 1]) % P;
}
printf("%d\n", ans);
return 0;
}
B. Bit Operation
好像是签到题。
分析操作性质，发现假如有两个 \(0\)，最后得到的一定是 \(0\)，假如两个 \(1\)，最后得到的一定是 \(1\)，否则得到的是 \(0\) 或者 \(1\)。发现这其实等价于从两个数中选一个删除。
那么我们就可以枚举最后剩下的那个 \(1\)，然后统计方案数。注意到只有两端的数有一种选择方案，其它数都有两种选择方案，所以答案形如 \(1 \times 3 \times 5 \times \cdots\)，两边组合数合并起来即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005, P = 998244353;
int n, a[MAXN];
int fac[MAXN], inv[MAXN];
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % P;
inv[n] = qpow(fac[n], P - 2);
for (int i = n; i >= 1; i--)
inv[i - 1] = 1ll * inv[i] * i % P;
assert(inv[0] == 1);
}
int f[MAXN];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
init(n);
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = 1ll * f[i - 1] * (2 * i - 1) % P;
}
int ans = 0;
for (int i = 1; i <= n; i++) if (a[i] == 1) {
ans = (ans + 1ll * fac[n - 1] * inv[i - 1] % P * inv[n - i] % P * f[i - 1] % P * f[n - i]) % P;
}
printf("%d\n", ans);
return 0;
}
C. Count Min Ratio
solution version 2. 第一版因为停电被吃掉了。气死了。
首先考虑题目要求的式子其实就是：
\[\sum_{i=0}^b \sum_{j=0}^r \binom{i+j}{i} \binom{b-i+r-j}{b-i} \min\left(\left\lfloor\frac{j}{i}\right\rfloor, \left\lfloor\frac{r-j}{b-i}\right\rfloor\right) \]考虑把后面那个东西拆了。底函数有经典的将值转为条件的方法，具体来讲：
\[\begin{aligned} &\min\left(\left\lfloor\frac{j}{i}\right\rfloor, \left\lfloor\frac{r-j}{b-i}\right\rfloor\right)\\ =&\sum_{x=1}^{\infty} \left[x \le \left\lfloor\frac{j}{i}\right\rfloor, \left\lfloor\frac{r-j}{b-i}\right\rfloor\right]\\ =&\sum_{x=1}^{\infty} \left[xi \le j \land x(b-i) \le r - j\right]\\ =&\sum_{x=1}^{\infty} \left[xi \le j \le r - xb + xi\right]\\ \end{aligned} \]容易发现 \(x\) 有一个上界 \(\left\lfloor\dfrac{r}{b}\right\rfloor\)，我们设它为 \(n\)。现在右面变成了一个关于 \(j\) 的条件，我们考虑调换求和顺序：
\[\begin{aligned} & \sum_{i=0}^b \sum_{j=0}^r \binom{i+j}{i} \binom{b-i+r-j}{b-i} \min\left(\left\lfloor\frac{j}{i}\right\rfloor, \left\lfloor\frac{r-j}{b-i}\right\rfloor\right)\\ =& \sum_{x=1}^n \sum_{i=0}^b \sum_{j = xi}^{r - xb + xi} \binom{i+j}{i} \binom{b-i+r-j}{b-i} \\ =& \sum_{x=1}^n \sum_{p = 0}^{r - xb}\sum_{i=0}^b \binom{i+j}{i} \binom{b-i+r-j}{b-i} & (j := xi + p)\\ \end{aligned} \]可以使用广义二项级数化简，然后做完了。 代数推导太过于困难，考虑组合意义。
我们发现，这个东西本质上在枚举从 \((0, 0) \to (b, r)\) 的每条路径上的每一个点。而 \(j=xi+p\) 的条件相当于求所有路径中经过 \(y=xi+p\) 这条直线的点数的和。
我们先考虑一个问题：从 \((0, 0) \to (n, kn+p)\) 的路径上，不穿过 \(y=kn+p\) 这条直线，路径数有多少？我们记这个东西的答案为 \(f(n, k, p)\)。发现当 \(k=1\) 时这是经典的卡特兰数，所以我们用类似的方法去计数。考虑 \((0, 0) \to (n, kn + p)\) 和 \((0, 0) \to (n - 1, kn + p + 1)\) 的两种路径，后者一定穿过直线。
先考虑第一种路径，枚举是否穿过直线，以及第一次穿过直线的位置，那么下一步一定是向上走，可以得到：
\[\binom{(k + 1) n + p}{n} = f(n, k, p) + \sum_{i=0}^{n - 1} f(i, k, p) \binom{n - i + (kn + p) - (ki - p) - 1}{n - i} \]再考虑第二种路径，一定穿过直线，直接枚举穿过直线的位置，可得：
\[\begin{aligned} &\binom{(k + 1) n + p}{n - 1} = \sum_{i=0}^{n - 1} f(i, k, p) \binom{n - 1 - i + (kn + p + 1) - (ki - p) - 1}{n - 1 - i}\\ =&\binom{(k + 1) n + p}{n - 1} = \frac{1}{k} \sum_{i=0}^{n - 1} f(i, k, p) \binom{n - i + (kn + p) - (ki - p) - 1}{n - i} \end{aligned} \]对比两个式子，容易得出：
\[f(n, k, p) = \binom{(k + 1) n + p}{n} - k \binom{(k + 1) n + p}{n - 1} \]于是这个问题就解决了。
再次考虑原来的问题，设从 \((0, 0) \to (w, h)\) 的所有路径中经过 \(y = kx + p\) 这条直线的点的总数为 \(g(w, h, k, p)\)，那么首先有一个显然的式子，就是枚举每个点，计算经过它的方案数，可以得到：
\[g(w, h, k, p) = \sum_{i = 0}^w \binom{i + ki+p}{i} \binom{w - i + h - ki - p}{w - i} \]考虑想办法凑出 \(f(n, k, p)\)，我们计算 \(g(w, h, k, p) - k \cdot g(w - 1, h + 1, k, p)\)：
\[\begin{aligned} &g(w, h, k, p) - k \cdot g(w - 1, h + 1, k, p)\\ =&\sum_{i=0}^w\binom{(k+1)i + p}{i} \left(\binom{w - i + h - ki - p}{w - i} - k \binom{w - i + h - ki - p}{w - i - 1}\right)\\ =&\sum_{i=0}^w\binom{(k+1)i + p}{i} f(w - i, k, h - wi - p)\\ \end{aligned} \]考虑这个东西的组合意义。我们相当于在枚举一个点，前面随意走，然后从这个点开始一直在 \(y=kx+p\) 直线的上方的方案数。假如说我们钦定在这个点往上走一步，那么就变成了枚举最后一次经过 \(y=kx+p\) 的点，然后之后一直不经过 \(y=kx+p\) 的方案数，这实际上统计了所有 \((0, 0) \to (w, h + 1)\) 的路径数。于是我们可以得到答案等于 \(\dbinom{w + h + 1}{w}\)。
我们知道了 \(g(w, h, k, p) - k \cdot g(w - 1, h + 1, k, p) = \dbinom{w + h + 1}{w}\)，暴力展开即可得到：
\[g(w, h, k, p) = \sum_{i=0}^w \binom{w + h + 1}{i} k^{w - i} \]这个式子与 \(p\) 都无关。那么直接代回原来的式子就能化简了。
容易得到原式等于：
\[\sum_{i=0}^b \binom{r+b+1}{i} \sum_{x=1}^n (r-bx+1) x^{b-i} \]我们只需要预处理出自然数幂和即可快速计算这个式子。注意到上标 \(n\) 不变，所以考虑用伯努利数计算。（直接写出来 EGF 也行，就是 \(\dfrac{e^{(n + 1)x} - 1}{e^x - 1} - 1\)）
int main() {
long long r; int b;
scanf("%lld%d", &r, &b);
init(b + 3);
Polynomial F(b + 1), G(b + 1);
int n = (r / b) % P;
for (int i = 0; i <= b + 1; i++) {
F[i] = inv[i + 1];
G[i] = 1ll * qpow(n + 1, i + 1) * inv[i + 1] % P;
}
F = (G * F.inv(b + 2) - 1).set(b + 1);
for (int i = 0; i <= b + 1; i++) {
F[i] = 1ll * F[i] * fac[i] % P;
}
int ans = 0, tmp = 1;
for (int i = 0; i <= b; i++) {
ans = (ans + 1ll * tmp * inv[i] % P * (
(r + 1) % P * F[b - i] % P - 1ll * b * F[b - i + 1] % P + P
)) % P;
tmp = 1ll * tmp * ((r + b + 1 - i) % P) % P;
}
printf("%d\n", ans);
return 0;
}
D. Do Use FFT
观察式子，发现 \(i\) 和 \(j\) 是完全独立的，所以考虑把 \(i, j\) 分离开。简单推式子：
\[\begin{aligned} f_k &= \sum_{i = 1}^n c_i \prod_{j=1}^k (a_i + b_j)\\ &= \sum_{i = 1}^n c_i \sum_{p = 0}^k a_i^{k - p} [x^p] \prod_{j=1}^k (1 + b_j x)\\ &= \sum_{p = 0}^k \sum_{i = 1}^n c_i a_i^{k - p} [x^p] \prod_{j=1}^k (1 + b_j x)\\ \end{aligned} \]我们令 \(\displaystyle G(x) = \sum_{k \ge 0} \sum_{i = 1}^n c_i a_i^k x^k\)，显然有 \(\displaystyle G(x) = \sum_{i = 1}^n \frac{c_i}{ 1 - a_i x}\)，这部分可以分治乘法 \(O(n \log^2 n)\) 求出。
然后原问题就转化成了：
\[f_k = [x^k] G(x) \prod_{i = 1}^k (1 + b_i x) \]首先有一个很暴力的做法：直接分块重构，设一个阈值 \(B\)，当后面的次数大于 \(B\) 时直接与前面的 \(G(x)\) 乘起来，这样一定是一个 \(B\) 次多项式乘一个 \(n\) 次多项式，可以在 \(O(B)\) 复杂度内求单项，总复杂度 \(O(\frac{n}{B} n \log n + nB)\)，令 \(B = \sqrt{n \log n}\) 可得 \(O(n \sqrt{n \log n})\) 的复杂度，由于时限 10s，完全可以通过。
int n, a[MAXN], b[MAXN], c[MAXN];
pair<Polynomial, Polynomial> solve(int l, int r) {
if (l == r) {
return { Polynomial{ c[l] }, Polynomial{ 1, P - a[l] } };
}
int mid = (l + r) >> 1;
auto L = solve(l, mid), R = solve(mid + 1, r);
return { L.first * R.second + L.second * R.first, L.second * R.second };
}
int main() {
scanf("%d", &n);
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++)
scanf("%d", &c[i]);
auto p = solve(1, n);
auto g = (p.first * p.second.inv(n + 1)).set(n);
auto tmp = Polynomial{1};
const int B = 2200;
for (int i = 1; i <= n; i++) {
if (i % B == 0) {
g = (g * tmp).set(n);
tmp = Polynomial{1};
}
tmp.set(tmp.len + 1);
for (int j = tmp.len; j >= 1; j--) {
tmp[j] = (tmp[j] + 1ll * b[i] * tmp[j - 1]) % P;
}
int ans = 0;
for (int j = 0; j <= tmp.len && j <= i; j++) {
ans = (ans + 1ll * tmp[j] * g[i - j]) % P;
}
printf("%d\n", ans);
}
return 0;
}
略微精细点：发现求的次数与后面的式子的区间是连续的，尝试分治计算这个东西，考虑先计算出左区间的乘积，然后在把当前的乘积递归给右边计算。发现，对于右区间 \([mid + 1, r]\)，第 \(mid + i\) 个位置的答案是左区间的 \(G(x) \prod (1+b_i x)\) 乘上一个 \(i\) 次多项式，那么前面那个多项式有用的次数为 \([mid, mid + i]\)。也就是说，左面的答案仅有 \([mid, r]\) 这些项是有用的，我们只保留这些项然后往下递归。不难发现对于每一个区间，保留的多项式长度都是区间的长度，所以复杂度为 \(T(n) = 2T\left(\dfrac{n}{2}\right) + O(n \log n)\)，即 \(T(n) = O(n \log^2 n)\)。大常数导致跑的和 \(O(n \sqrt{n \log n})\) 差不多。
常数至少能砍 \(\frac{1}{3}\)，不过反正能过，懒得优化了。
int n, a[MAXN], b[MAXN], c[MAXN];
pair<Polynomial, Polynomial> solve(int l, int r) {
if (l == r) {
return { Polynomial{ c[l] }, Polynomial{ 1, P - a[l] } };
}
int mid = (l + r) >> 1;
auto L = solve(l, mid), R = solve(mid + 1, r);
return { L.first * R.second + L.second * R.first, L.second * R.second };
}
int ans[MAXN];
Polynomial solve2(Polynomial G, int l, int r) {
if (l == r) {
ans[l] = (1ll * G[0] * b[l] + G[1]) % P;
return Polynomial{ 1, b[l] };
}
int mid = (l + r) >> 1;
auto L = solve2(G, l, mid);
return L * solve2((G * L).shift(mid - l + 1).set(r - mid), mid + 1, r);
}
int main() {
scanf("%d", &n);
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++)
scanf("%d", &c[i]);
auto p = solve(1, n);
auto g = (p.first * p.second.inv(n + 1)).set(n);
solve2(g, 1, n);
for (int i = 1; i <= n; i++) {
printf("%d ", ans[i]);
}
printf("\n");
return 0;
}
题解给出了一个多点求值做法，我们直接扔掉。
E. Edge Subsets
怎么感觉见过类似的套路，但是还是一点也不会，哈哈。
令 \(g = \gcd(a, b)\)，那么我们可以按照点 \(\bmod g\) 的值分成若干组，答案等于它们的乘积，于是就转化成了 \(\gcd(a, b) = 1\) 的情况。
考虑按照 \(b\) 再将点进行排列，根据裴蜀定理，可以得知 \(ka \bmod b\) 互不相同。于是我们将这些点排列成一个方针，令 \(p\) 的坐标为 \((x, y)\)，则满足 \(x = \left\lfloor\dfrac{p}{b}\right\rfloor, yA \equiv p \pmod b\)。容易发现，这样进行排列后，\(+b\) 的边就是向下连边，\(+a\) 的边就是向右 / 向右下 / 向下一行的第一个数连边。
然后大概会连成一个这样的图：
我们现在考虑统计匹配数。这种东西看起来就像是状压一类的东西。可以使用轮廓线 DP（插头 DP）统计答案，复杂度 \(O(n 2^b)\)，复杂度过高。但是注意到这张图的总点数是 \(O(n)\) 的，于是可以类似很多状压的套路，每次将较小的那一边进行状压。但是如果转过来做，我们需要先枚举最后一列向第一列连的边的选择方案，然后再 DP，这样复杂度为 \(O(n 4^{\frac{n}{b}})\)。平衡一下，可以得到 \(O(n 2^{\sqrt{2n}})\)，可以通过。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205, MAXM = 405, P = 998244353;
int n, m, a, b;
int x[MAXN], y[MAXN];
bool edge[MAXN][MAXN][3];
void add(int &a, int b) {
a += b;
if (a >= P) a -= P;
}
#define BIT(j) (1 << (j))
#define MASK(j) (S ^ BIT(j))
namespace Solution1 {
int f[2][1 << 21];
int solve(int n, int m) {
int o = 0;
int S = (1 << (m + 1)) - 1;
memset(f[o], 0, sizeof f[o]);
f[o][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
memset(f[o ^ 1], 0, sizeof f[o ^ 1]);
for (int s = 0; s <= S; s++) if (f[o][s]) {
if (s >> (j + 1) & 1) {
add(f[o ^ 1][s & MASK(j + 1)], f[o][s]);
} else {
add(f[o ^ 1][s & MASK(j + 1)], f[o][s]);
if (edge[i][j][0]) {
if (!(s >> j & 1)) {
add(f[o ^ 1][s | BIT(j) & MASK(j + 1)], f[o][s]);
}
}
if (edge[i][j][1]) {
if (!(s >> (j + 2) & 1)) {
add(f[o ^ 1][s | BIT(j + 2)], f[o][s]);
}
}
if (edge[i][j][2]) {
if (j == m - 1) {
if (!(s & 1)) {
add(f[o ^ 1][s | BIT(0)], f[o][s]);
}
} else {
add(f[o ^ 1][s | BIT(j + 1)], f[o][s]);
}
}
}
}
o ^= 1;
}
memset(f[o ^ 1], 0, sizeof f[o ^ 1]);
for (int s = 0; s <= S; s++) if (f[o][s]) {
add(f[o ^ 1][(s << 1 & S)], f[o][s]);
}
o ^= 1;
}
int ans = 0;
for (int s = 0; s <= S; s++) {
add(ans, f[o][s]);
}
return ans;
}
}
namespace Solution2 {
int f[2][1 << 11];
int solve(int n, int m) {
int S = (1 << (n + 1)) - 1;
int ans = 0;
for (int t = 0; t < (1 << n); t++) {
bool flag = true;
for (int i = 0; i < n; i++) if (t >> i & 1) {
if (!edge[i][m - 1][2]) {
flag = false;
break;
}
}
if (!flag) continue;
int o = 0;
memset(f[o], 0, sizeof f[o]);
f[o][t << 2] = 1;
for (int i = 0; i < m - 1; i++) {
for (int j = 0; j < n; j++) {
memset(f[o ^ 1], 0, sizeof f[o ^ 1]);
for (int s = 0; s <= S; s++) if (f[o][s]) {
if (s >> (j + 1) & 1) {
add(f[o ^ 1][s & MASK(j + 1)], f[o][s]);
} else {
add(f[o ^ 1][s & MASK(j + 1)], f[o][s]);
if (edge[j][i][1]) {
if (!(s >> j & 1)) {
add(f[o ^ 1][s | BIT(j) & MASK(j + 1)], f[o][s]);
}
}
if (edge[j][i][0]) {
if (!(s >> (j + 2) & 1)) {
add(f[o ^ 1][s | BIT(j + 2)], f[o][s]);
}
}
if (edge[j][i][2]) {
add(f[o ^ 1][s | BIT(j + 1)], f[o][s]);
}
}
}
o ^= 1;
}
memset(f[o ^ 1], 0, sizeof f[o ^ 1]);
for (int s = 0; s <= S; s++) if (f[o][s]) {
add(f[o ^ 1][(s << 1 & S)], f[o][s]);
}
o ^= 1;
}
memset(f[o ^ 1], 0, sizeof f[o ^ 1]);
for (int s = 0; s <= S; s++) if (f[o][s]) {
add(f[o ^ 1][s >> 1], f[o][s]);
}
o ^= 1;
for (int j = 0; j < n; j++) {
memset(f[o ^ 1], 0, sizeof f[o ^ 1]);
for (int s = 0; s <= S; s++) if (f[o][s]) {
if (s >> j & 1) {
add(f[o ^ 1][s], f[o][s]);
} else {
add(f[o ^ 1][s], f[o][s]);
if (edge[j][m - 1][0]) {
if (!(s >> (j + 1) & 1)) {
add(f[o ^ 1][s | BIT(j) | BIT(j + 1)], f[o][s]);
}
}
}
}
o ^= 1;
}
for (int s = 0; s <= S; s++) if ((s & t) == 0) {
add(ans, f[o][s]);
}
}
return ans;
}
}
vector<pair<int, int>> e[MAXN];
int mp[MAXN];
int solve(vector<pair<int, int>> e, int n) {
memset(edge, 0, sizeof edge);
for (auto p : e) {
int u = p.first, v = p.second;
if (x[u] == x[v]) edge[x[u]][y[u]][1] = 1;
else if (y[u] == y[v]) edge[x[u]][y[u]][0] = 1;
else edge[x[u]][y[u]][2] = 1;
}
if (b <= sqrt(2 * n)) return Solution1::solve((n + b - 1) / b, b);
else return Solution2::solve((n + b - 1) / b, b);
}
int main() {
scanf("%d%d%d%d", &n, &m, &a, &b);
int g = __gcd(a, b);
a /= g, b /= g;
for (int i = 0; i < b; i++) {
mp[i * a % b] = i;
}
for (int i = 0; i < n; i++) {
x[i] = i / b, y[i] = mp[i % b];
}
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
u--, v--;
e[u % g].push_back({ u / g, v / g });
}
int ans = 1;
for (int i = 0; i < g; i++) {
ans = 1ll * ans * solve(e[i], (n + g - 1) / g) % P;
}
printf("%d\n", ans);
return 0;
}
F. Find the LCA
首先考虑一个问题，我们尝试计算出对于某一个大小 \(k\)，有多少树满足 \(\mathrm{lca}(k - 1, k) = 1\)。可以证明，当 \(n \ge 3\) 时，答案等于 \(\dfrac{(n-1)!}{2}\)。证明考虑建立每两棵树的双射关系，假设现在我们有 \(l = \mathrm{lca}(k - 1, k), l \ne 1\)，那么可以考虑将 \(l\) 与除了 \(k\) 子树外的所有子树同时剥去，整个子树接在 \(1\) 上，这样一定能够构造出一棵 \(\mathrm{lca}(k - 1, k) = 1\) 的树。同理，对于任意一棵 \(\mathrm{lca}(k - 1, k) = 1\) 的树，我们可以找到 \(1\) 的子树中包含 \(k - 1\) 的那一个，将其插入至 \(1 \to k\) 的路径中，由于有堆的性质，插入的位置唯一。于是可以证明双射关系成立。
那么考虑如何计算答案。有三种情况：
- \(\mathrm{lca}(n - 1, n) = n - 1\)；
- \(\mathrm{lca}(n - 1, n) = 1\)；
- \(\mathrm{lca}(n - 1, n) \in [2, n - 2]\)。
三种情况答案分别是：
- \((n-2)! a_{n - 1} a_n\)；
- \(\displaystyle \dfrac{(n-1)!}{2} \times \prod_{i=1}^n a_i\)；
- \(\displaystyle \sum_{i=3}^{n - 2} \dfrac{(i-1)!}{2} (n - i - 1)! \sum_{j = 2}^{n - 2} f_{i - 2, j}\)；
其中 \(f_{i, j}\) 表示第 \(j\) 个节点所在子树大小为 \(i\) 的所有 \(\prod a_i\) 之和。
考虑怎么计算 \(f_{i, j}\)，显然可以使用多项式刻画，发现：
\[f_{i, j} = [x^i] (j - 1) a_j x \prod_{k = j + 1}^{n - 2} (1 + a_k x) \]那么我们只需要计算出 \(F = \sum_{j = 2}^{n - 2} (j - 1) a_j x \prod_{k = j + 1}^{n - 2} (1 + a_k x)\) 即可快速计算答案。这个东西相当于求每一个后缀积的和，显然可以分治乘法维护。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400005, P = 998244353, G = 3, GI = 332748118;
const int INV2 = (P + 1) / 2;
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
struct Polynomial { ... };
int n;
int a[MAXN];
int fac[MAXN], inv[MAXN];
pair<Polynomial, Polynomial> solve(int l, int r) {
if (l > r) return {{}, {}};
if (l == r) {
return { Polynomial{ 0, 1ll * (l - 1) * a[l] % P }, Polynomial{ 1, a[l] } };
}
int mid = (l + r) >> 1;
auto L = solve(l, mid), R = solve(mid + 1, r);
return { L.first * R.second + R.first, L.second * R.second };
}
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % P;
inv[n] = qpow(fac[n], P - 2);
for (int i = n; i >= 1; i--)
inv[i - 1] = 1ll * inv[i] * i % P;
assert(inv[0] == 1);
}
int f(int n) {
return 1ll * fac[n - 1] * INV2 % P;
}
int main() {
scanf("%d", &n);
init(n);
int prod = 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (i <= n - 2) prod = 1ll * prod * a[i] % P;
}
int ans = (fac[n - 2] + 1ll * f(n) * prod) % P;
auto p = solve(2, n - 2).first;
for (int i = 3; i < n; i++) {
ans = (ans + 1ll * fac[n - i - 1] * f(i) % P * p[i - 2]) % P;
}
ans = 1ll * ans * a[n - 1] % P * a[n] % P;
printf("%d\n", ans);
return 0;
}
G. Games
首先题目给出的是 k - nim 游戏，结论为将所有数进行二进制表示，当每一位上 \(1\) 的个数模 \((k + 1)\) 等于 \(0\) 时先手必败。证明与 Nim 游戏类似。
这个题实际上是一个 \(6\) - nim，不难发现我们实际上要做的就是一个 \(7\) 进制异或 FWT。简单来讲，就是我们定义 \(k\) 维异或为每一位加起来模 \(k\)，这东西是一个循环卷积，所以考虑直接用 DFT 转移。打个表发现模意义下的 \(7\) 次单位根存在，所以不需要写啥分圆多项式，直接跑 FWT 即可。
高维 FWT 详见 command_block's blog。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005, G = 14553391, P = 998244353;
int n;
long long k;
int qpow(int a, long long b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
const int GI = qpow(G, P - 2);
int a[MAXN];
int base[10];
int tmp[7];
void fwt(bool rev) {
for (int mid = 1; mid < base[7]; mid *= 7) {
for (int l = 0; l < base[7]; l += mid * 7) {
for (int i = 0; i < mid; i++) {
int step = 1;
for (int k = 0; k < 7; k++, step = 1ll * step * (rev ? GI : G) % P) {
int w = 1;
tmp[k] = 0;
for (int q = 0; q < 7; q++, w = 1ll * w * step % P) {
tmp[k] = (tmp[k] + 1ll * a[l + i + q * mid] * w) % P;
}
}
for (int k = 0; k < 7; k++) {
a[l + i + k * mid] = tmp[k];
}
}
}
}
if (rev) {
int inv = qpow(base[7], P - 2);
for (int i = 0; i < base[7]; i++) {
a[i] = 1ll * a[i] * inv % P;
}
}
}
int main() {
scanf("%d%lld", &n, &k);
base[0] = 1;
for (int i = 1; i <= 7; i++) {
base[i] = 7 * base[i - 1];
}
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
int y = 0;
for (int j = 0; j < 7; j++) {
y += (x >> j & 1) * base[j];
}
a[y]++;
}
fwt(false);
for (int i = 0; i < base[7]; i++) {
a[i] = qpow(a[i], k);
}
fwt(true);
printf("%d\n", a[0]);
return 0;
}
H. Harsh Comments
这个加权随机非常烦人啊！考虑把它去了。
有一个经典随机算法叫拒绝采样，我们可以用相同的方法放宽限制。考虑假如每个数被选后不删除，仍然可以继续选，如果选了之前已经选过的数就重新选，这样首先每个数被选择的概率就确定了，而且不难证明每一种选择顺序的概率是不变的。
然后就可以根据期望的线性性，我们考虑将答案转化为每一个 \(b_i\) 的选择顺序在所有 \(a_i\) 的选择顺序之后的概率之和，这些 \(b_i\) 是不需要被选的，所以用 \(n+m\) 减去这个概率之和就是答案。
看起来还是不好计算，考虑容斥，枚举一个集合一定在 \(b_i\) 之后选，其它的不变。设这个集合的概率和为 \(q\)，选择 \(b_i\) 的概率为 \(p_i\)，那么概率为 \(\sum_{i \ge 1} p_i (1-p_i-q)^{i - 1} = \dfrac{p_i}{p_i + q}\)。考虑到这里只关心选中的集合的大小，所以可以先用一个背包统计出每种集合和的容斥系数之和，然后直接计算答案即可。
这个做法是和 猎人杀 一模一样的，不过那个题需要写一个分治 NTT，不能直接背包。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005, MAXM = 10005, P = 998244353;
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % P;
a = 1ll * a * a % P;
b >>= 1;
}
return ans;
}
int n, m;
int a[MAXN], b[MAXN];
int f[MAXM];
int main() {
scanf("%d%d", &n, &m);
int sum = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
for (int i = 1; i <= m; i++) {
scanf("%d", &b[i]);
sum += b[i];
}
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 10000; j >= a[i]; j--) {
f[j] = (f[j] - f[j - a[i]] + P) % P;
}
}
int ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= 10000; j++) {
ans = (ans + 1ll * f[j] * b[i] % P * qpow(b[i] + j, P - 2)) % P;
}
}
ans = (n + m - ans + P) % P;
printf("%d\n", ans);
return 0;
}
I. Inverse Problem
好像是签到题。
首先观察到一个性质，就是这个序列中第 \(i\) 个数一定出现在 \([1, n - m + i]\) 内，而如果序列中存在一个数比前面的数小，说明这个数一定是在 \(n - m + i\) 的位置，否则肯定优先选它。那么这个数以及后面的数的位置就全部固定了。
考虑前面的数，如果有一个数没有被固定，且没有出现在序列中，那么它肯定要在序列中比它大的数的前面。那么我们考虑从小到大依次填入这几个数，然后统计一下当前有多少位置可以放即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005, P = 998244353;
int n, m;
int a[MAXN];
int vis[MAXN];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
}
bool flag = false;
int top;
for (int i = 1; i <= m; i++) {
if (a[i] < a[i - 1]) {
flag = true;
}
if (flag)
vis[a[i]] = 2;
else
vis[a[i]] = 1, top = a[i];
}
int ans = 1;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (vis[i] == 0)
ans = 1ll * ans * (cnt + (i > top)) % P, cnt++;
if (vis[i] == 1)
cnt++;
}
printf("%d\n", ans);
return 0;
}
J. Japanese Knowledge
首先有一个结论：设 \(f_k(a_1, a_2, \cdots, a_n)\) 为 \(k\) 时的答案，\(g(a_1, a_2, \cdots, a_n)\) 为没有限制时的答案，那么可以得到 \(f_k(a_1, a_2, \cdots, a_n) = g(a_{k + 1} - 1, a_{k + 2} - 1, \cdots, a_n - 1)\)。
证明考虑建立两者之间的双射：
- 对于任意一种方案，将所有 \(x_i = a_i\) 的列删去，即可得到一个长度为 \(n - k\) 的序列，且满足每个 \(x_i < a_{i + k}\)；
- 对于一个满足每个 \(x_i < a_{i + k}\) 的长为 \(n - k\) 的序列，我们考虑从小往大填，每次将最小的一个数填入第一个 \(a_j > x_i\) 的 \(j\) 位置。最后剩下的没有填的位置就都填 \(x_i = a_i\)，即可得到一个长为 \(n\) 的序列，满足 \(x_i \le a_i\)。
于是我们相当于要对每个后缀计算出答案。我们首先可以将序列转化成路径数，那么答案可以看做是从一个阶梯状格子的右边界任意一个位置进入，然后从某个下边界出去的路径数。这个可以使用多项式分治计算。
具体的，我们用 \(solve(l, r, F, d)\) 计算 \([l, r]\)，底边为 \(d\)，右边界进入的方案数为 \(F\) 时从下边界的每个点出去的方案数。我们从 \(mid\) 处将其分作三部分，首先计算右上角的部分，然后可以使用卷积计算到左下角的右边界的方案数，最后计算所有点到下边界的方案数即可。右下角的部分可以使用组合数直接计算，且式子可以卷积优化。所以直接分治做即可。
（图从别的博搬的，把下边界和右边界反过来了，意思差不多）
Polynomial solve(Polynomial F, int l, int r, int d) {
if (l == r) {
Polynomial way;
for (int i = 0; i <= a[l] - d; i++) {
way[0] = (way[0] + F[i]) % P;
}
return way;
}
int mid = (l + r) >> 1;
int llen = mid - l + 1, rlen = r - mid;
int x = a[mid] - d;
if (x < 0) return solve(F, mid + 1, r, d).shift(-llen);
auto R = solve(F.shift(x + 1), mid + 1, r, d + x + 1);
Polynomial tmp(x);
for (int i = 0; i <= x; i++)
tmp[i] = C(rlen - 1 + x - i, rlen - 1);
auto rlway = (F.set(x) * tmp).shift(x);
tmp = Polynomial(x + rlen);
for (int i = 0; i <= x + rlen; i++)
tmp[i] = fac[x + rlen - i];
auto R2 = R;
for (int i = 0; i < rlen; i++)
R2[i] = 1ll * R2[i] * inv[i] % P;
auto ulway = (R2 * tmp).shift(rlen).set(x);
for (int i = 0; i <= x; i++)
ulway[i] = 1ll * ulway[i] * inv[x - i] % P;
auto L = solve(rlway + ulway, l, mid, d);
tmp = Polynomial(rlen);
for (int i = 0; i <= rlen; i++)
tmp[i] = C(x + rlen - i, x);
auto udway = (R * tmp).shift(rlen);
tmp = Polynomial(x + rlen);
for (int i = 0; i <= x + rlen; i++)
tmp[i] = fac[x + rlen - i];
F.set(x);
for (int i = 0; i <= x; i++)
F[i] = 1ll * F[i] * inv[i] % P;
auto rdway = (F * tmp).shift(x + 1).set(rlen - 1);
for (int i = 0; i <= rlen - 1; i++)
rdway[i] = 1ll * rdway[i] * inv[rlen - 1 - i] % P;
return L + (udway + rdway).shift(-llen);
}
int main() {
scanf("%d", &n);
init(500000);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
Polynomial F(a[n] - 1);
for (int i = 0; i < a[n]; i++)
F[i] = 1;
auto ans = solve(F, 1, n, 1);
for (int i = 0; i < n; i++) {
printf("%d ", ans[i]);
}
printf("1\n");
return 0;
}