AT_arc106_e [ARC106E] Medals
先考虑判定 \(x\) 天时能否满足条件。
看成一个二分图，左部点有 \(nk\) 个，有不点有 \(x\) 个。对于第 \(i\) 个人的第 \(j\) 个关联点，向右部点中满足 \(1 \le j \bmod 2A_i\le A_i\) 的点连边。那么当该二分图存在完美匹配时有解。
考虑根据 Hall 定理判定有解。如果存在 \(|N(S)|<|S|\)，那么一定存在 \(S'\)，使得 \(S'\) 中每个人的所有关联点都在 \(S'\) 内也满足 \(|N(S)|<|S|\)。因为每个人的关联点邻域相同，这么做只会使 \(|S|\) 增大而不会使 \(|N(S)|\) 增大。
考虑答案上界。如果依次颁奖，那么是 \(\sum \frac{k}{a_i}2a_i = 2nk\) 的。
考虑求 \(|N(S)|\)。对于每个右部点 \(x\)，维护 \(s_{x}\) 为其左部点编号集合。那么当 \(S \cap s_x =\empty\) 时 \(x \notin N(s)\)。则对 \(s_x\) 的补集的子集加，查询 \(N(S)\) 的时候就已知 \(N(S)\) 补集的大小了。
时间复杂度 \(O((n2^n + n^2k)\log (nk))\)。预处理 \(s_x\) 做到 \(O(n2^n\log(nk)+n^2k)\)。
P11173 「CMOI R1」We Want To Run / Nilpotent
如果 \(A_{i,j}\ne 0\)，那么 \(i\) 向 \(j\) 连一条有向边。则当 \((A^x)_{i,j}\ne 0\) 时，一定存在一条 \(i\) 到 \(j\) 经过 \(x-1\) 条边的路径。
那么 \(f(A)\) 应该是最小的正整数 \(x\)，使得对于任意 \((i,j)\)，都不存在一条 \(i\) 到 \(j\) 经过 \(x-1\) 条边的路径。
显然 \(f(A)\ne 0\) 首先需要满足图是 DAG。那么问题变成，对于一个 DAG，记 \(m\) 为其边数，\(k\) 为其最长链长度（边数）。求所有 DAG 的 \((a-1)^{m}(k+1)\) 的和。
DAG 是加 \(0\) 入度点的过程。定义状态函数 \(f_{i,j,k}\) 表示当前最长链长度为 \(i\)，有 \(j\) 个 \(0\) 入度点（同时也是最长链起点），剩下 \(k\) 个点不在图上的价值和。
考虑新加进来 \(x\) 个点：\(f_{i,x,k-x}\gets f_{i-1,j,k}\binom{k}{x}(a^{n-k}-a^{n-k-j})^x\)。
也就是：\(f_{i,x,k}=\binom{x+k}{x}\sum\limits_{j=1}^{n}(a^{n-k-x-j})^xf_{i-1,j,x+k}(a^j-1)^x\)。答案为 \(\sum (i+1)f_{i,j,0}\)。
把 \((i+1)\) 拆到转移里，相当于在这 \((i+1)\) 个时刻里选一个时刻然后求和。那么只需要定义 \(f_{i,j}\) 表示当前有 \(j\) 个 \(0\) 入读点，剩下 \(k\) 个点的价值和，再定义 \(g_{i,j}\) 为已经选定时刻的价值和。 转移为：
答案为 \(\sum g_{i,0}\)。时间复杂度 \(O(n^3)\)。
AT_arc156_d [ARC156D] Xor Sum 5
记 \(cnt_i\) 为 \(X_j = i\) 的数量。
那么在已知 \(cnt\) 的情况下对答案的贡献应该是 \((\sum A_icnt_i)(\binom{k}{cnt_1,cnt_2,\dots,cnt_k}\bmod 2)\)。
如果 \(\prod\limits_{i=1}^{k}\binom{k-\sum\limits_{j=1}^{i-1}cnt_j}{cnt_i}\bmod 2 = 1\)，需要满足对于 \(1 \le i \le k\)，\(cnt_i\) 在二进制下是 \(k - \sum\limits_{j=1}^{i-1}cnt_j\) 的子集。
由于 \(cnt_i\) 二进制下是 \(k - \sum\limits_{j=1}^{i-1}cnt_j\) 的子集，\((k-\sum\limits_{j=1}^{i-1}cnt_j) - cnt_i\) 是不会有借位的情况的。
那么相当于是把 \(k\) 二进制下的 \(1\) 分给这 \(n\) 个 \(cnt_i\)。
拆位，对于每一位看最后异或和是 \(0\) 还是 \(1\)。
我们在二进制下从低往高给 \(k\) 的这些 \(1\) 分配。由于 \(0 \le A_i\le 1000\)，在考虑二进制下第 \(x\) 位前满足： \(\sum A_icnt_i \le 10^3 \sum cnt_i < 2^{10+x}\)。又因为我们只在意第 \(x\) 位往上的状态，所以只需要存二进制下 \([x,x+9]\) 这些位的具体值。
定义状态函数 \(f_{x,s}\) 表示考虑到二进制下第 \(x\) 位，当前 \(\sum A_i cnt_i\) 二进制下 \([x,x+10]\) 这些位的值是 \(s\) 的方案数。转移枚举当前这一位分配给哪个 \(cnt\)，时间复杂度 \(O(\log V 2^{\alpha}n),\alpha = 10\)。