XXI Open Cup named after E.V. Pankratiev. Grand Prix of Tokyo
Grand Prix of 998244353
A. Ascending Matrix
先不考虑 $a_{r,c}=v$ 的限制。
我们将 $\le i$ 和 $>i$ 的数用一个折线分开，那么这条折线就是一个从 $(m,0)$ 到 $(0,n)$ 的折线，需要使得这 $k-1$ 条折线不互相穿过。
将第 $i$ 条折线向右上平移 $i-1$ 格后，使用LGV引理解决。
考虑原来的问题， $a_{r,c}=v$ 相当于有 $v-1$ 条折线恰好从 $p$ 的左下方（不包含p）经过。
对于第 $v$ 条折线，他最多只能恰好经过 $p$，而在平移后，就是不经过 $p$ 点。
那么新开一个 $x$，表示经过的是下方，而常数表示从 $p$ 的上方经过。
那么LGV引理中的每一项就是一个多项式。答案为这个多项式的 $x^{v-1}$ 的系数。
由于这个矩阵大小为 $k-1$ ，因此行列式最多为 $k-1$ 次的多项式。
拉格朗日插值，插 $k$ 次即可。
时间复杂度 $O(k^4+k^2(n+m))$。
B. Bit Operation
可以将操作变为：每次选择一个数，然后删掉左/右其中一个。
剩下的就很好统计了，时间复杂度 $O(n)$。
D. Do Use FFT
设 $F_k(x)=\prod_{i=1}^k(x+B_i)$。
$\forall k\in[1,n]$，需要求 $\sum_{i=1}^nC_iF_k(A_i)$。
我们设 $F_k(x)=f_0+f_1x^1+\cdots+f_kx^k$。
那么答案就是 $\sum_{j=0}^kf_j\sum_{i=1}^nC_iA_i^j$
设 $G(x)=\sum_{i=1}^nC_iA_i^jx^j=\sum_{i=1}^n\frac{C_i}{1-A_ix}$，答案就是 $[x^0]G(x)F_k(\frac{1}{x})$。
$G(x)$ 可通过简单的分治FFT，暴力通分后求出分母和分子，然后对分母求逆即可。
对于 $F_{l,r}(\frac{1}{x})=\prod_{i=l}^r\frac{1+B_ix}{x}$，我们仅需要求出 $[x^{r-l}]G(x)\prod_{i=l}^r(1+B_ix)$。
分治，先求 $[l,mid]$，对于 $[mid+1,r]$ 的答案，可以先求出 $G(x)\prod_{i=l}^{mid}(1+B_ix)$，然后去掉前面 $mid-l+1$ 位，当做除了一个 $x^{mid-l+1}$，然后传参递归处理右边即可。
时间复杂度 $T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log ^2n)$。
E. Edge Subsets
神仙题。
首先，显然有一个 $n\times 2^B$ 的状压DP做法。
考虑将 $V_i-U_i=A$ 或 $V_i-U_i=B$ 简化。
不妨设 $(A,B)=1$ 且 $A<B$（否则分成 $\gcd(A,B)$ 个图进行处理，然后乘法原理乘起来）。
那么将 $V_i-U_i=B$ 的排成一行。严格地说，将点 $v$ 排在一个网格内，其坐标 $(x,y)$ 满足 $x=\lfloor \frac{v}{B} \rfloor,yA\equiv v\pmod B$。
那么每一行的点都会互相连。$(x,i)$ 连向 $(x,i+1)$ 或 $(x+1,i+1)$，特别地，$(x,B-1)$ 会连向 $(x+1,0)$。
考虑从下往上进行状压DP。与 $O(n\times 2^B)$ 普通状压不同的是，我们需要记录最下面一层的情况。DP的时候看起来需要枚举两层的节点。但实际上可以做一个高维前缀和后就不需要了。时间复杂度是 $O(n\times 4^{\frac{n}{B}})$。
当 $B\le 20$ 时，选择第一种，否则选择第二种，即可得到 $O(n2^{\sqrt{2n}})$ 复杂度的算法。
1 |
|
F. Find the LCA
G. Games
取石子问题的变种。先手必败当且仅当把 $a_i$ 转换成二进制后，二进制每一位相加为 $7$ 的倍数。
也就是在 $n$ 个数里面可重复选择 $k$ 个，看有多少符合上述情况。
定义七进制不进位加法，那么答案相当于求 $[x^0]F^k(x)$。
使用七进制FWT即可，刚好 $7$ 的原根在模 $998244353$ 意义下存在。
H. Harsh Comments
注意到 $a_i$ 很小，也就是总和不超过 $10000$。
最大值不好算，最小值好算。使用Min-Max容斥，有：$E(max(S))=\sum_{T\subseteq S,T\neq \varnothing}(-1)^{|T|-1}E(min(T))$。
计算 $min(T)$，也就是一堆石子里第一次取出 $T$ 内任意一个的概率。这是，$T$ 内的石子就可以合并成一个，总和记为 $sum$。
根据期望的线性性，有 $min(T)=\sum_{i\in B\or i\in {\complement_ST}}\frac{sum}{sum+i}+1$。
这个 $+1$ 在容斥以后就没啥用了。$i\in B$ 的情况也比较容易，在背包里面计算容斥系数即可。对于 $i\in \complement_ST$，此时可以枚举每个 $i$，然后强制 $i$ 不在 $T$ 内时，剩下的 $n-1$ 个点的方案数，这相当于一个回退的背包。
时间复杂度 $O(n^3\log mod)$。假设 $n,m,a$ 同阶。可以通过一些简单的方法优化掉求逆的 $\log mod$。
I. Inverse Problem
注意到，我们只需要考虑 $p$ 的最长递增前缀，后面的不需要管它。
对于该前缀，$(p_i,p_{i+1})$ 内还没确定的数只能放在 $p_i$ 前面，那么一个个放，一直乘起来即可。
时间复杂度 $O(n)$。