题解
排列组合范德蒙德卷积计数容斥原理
Koxia and Sequence
题面
给定非负整数 $n,x,y$ ，对于所有满足 $\sum_{i=1}^n a_i=x,\text{OR}_{i=1}^n a_i=y$ ，的序列 $\{a_n\}$ 。求 $\bigoplus_{i=1}^n a_i$ 的异或和。
$1 \leq n < 2^{40} , 0 \leq x < 2^{60} , 0 \leq …
Jayun 发布于 2024-02-28 22:00:46
00
最小割最大流SPFA
题面
有 $n$ 个变量 $w[1]\sim w[n]$ ，每个变量的值为 $W$ 或 $-W$ 。
有 $p$ 个公式 $f(i)=a_i|w[x_i]-w[y_i]|+b_i|w[y_i]-w[z_i]|+c_i|w[z_i]-w[x_i]|+d_i(w[x_i]-w[y_i])+e_i(w[y_i]-w[z_i])+f_i(w[z_i]-w[x_i])$ 。 其中 $ …
Jayun 发布于 2024-02-28 20:20:20
00
数学推导杂项线性动态规划（线性 DP）
[AGC020C] Median Sum
题面
给定由 $n$ 个正整数 $a _ {1, 2, \cdots, n}$ 组成的可重集合，请求出它的非空子集的和的中位数。
$1\ \leq\ n\ \leq\ 2000, 1\ \leq\ A_i\ \leq\ 2000$
题解
发现重要性质，非空子集的和在值域上是对称的。bitset 背包即可。
代码
const int N = 20 …
Jayun 发布于 2024-02-28 18:37:23
00
数学推导杂项计数
题面
有一个 $1\sim n$ 的排列 $\{p_i\}$ ，对应了 $i$ 条有向边为 $(i,p_i)$ 的图。由于 $p_i$ 是排列，可以证明图由若干个环组成。你希望知道有多少种可能的排列 $\{p_i\}$ ，使得图中每一个环长度都为偶数，答案对 $998244353$ 取模。其中一部分 $p_i$ 已经给定。
$n\leq 10^5$ 。
题解
特 …
Jayun 发布于 2024-02-28 18:33:50
00
Polya 定理数学推导杂项
题面
题解
Polya 计数。旋转 2 个置换，翻转 3 个置换，单位置换 1 个。
旋转的循环就是每层（？）3 个转，反转就是对角线外两两转。
代码
const int N = 0, bN = 210;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < …
Jayun 发布于 2024-02-28 17:31:25
00
Polya 定理线性动态规划（线性 DP）
题意
摆。
题解
用背包维护不定点，套 Burside 引理。
代码
const int N = 30, M = 70;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == …
Jayun 发布于 2024-02-28 15:59:44
00
Polya 定理
题目
给定一个 $n$ 个点， $n$ 条边的环，有 $n$ 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 $10^9+7$ 取模
$n \leq 10^9,t \leq 10^3$
题解
对于一个置换 $\tau_k=\begin{pmatrix}
1 & 2 & \dots & n-k & n-k+1 & n-k+2 …
Jayun 发布于 2024-02-28 08:02:32
00
组合意义计数排列组合
题意
$n$ 个盒子，总共 $S$ 个球，初始状态 $\{a_i\}$ ，盒子之间边权 $w_i$ 表示一个球经过这条边的花费。问对于所有状态花费之和。
$n\leq5\times10^5, S\leq2\times10^6$ 。
题解
这种题就要考虑小贡献，对于每条边的贡献，插板法易得
$$\begin{aligned}
&\sum\limits_{i=1}^{n-1}\ …
Jayun 发布于 2024-02-27 20:42:16
00
快速数论变换（NTT）数学推导杂项指数生成函数普通生成函数
[清华集训2016] 如何优雅地求和
题目描述
有一个多项式函数 $f(x)$ ，最高次幂为 $x^m$ ，定义变换 $Q$ ：
$$Q(f,n,x)=∑_{k=0}^{n}f(k)\binom nkx^k(1−x)^{n−k}
$$
现在给定函数 $f$ 和 $n,x$ ，求 $Q(f,n,x)\bmod998244353$ 。
题解
copy大佬的。
和组合数问题长好像，看到组合 …
Jayun 发布于 2024-02-26 19:11:42
00
快速数论变换（NTT）
题解
经典结论
$$x^k=\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}x^{\underline i}
$$
代入
$$\sum_{k=0}^{n-1}a_kx^k=\sum_{k=0}^{n-1}\sum_{i=0}^ka_k\begin{Bmatrix}k\\i\end{Bmatrix}x^{\underline i}=\sum_{i=0}^n\l …
Jayun 发布于 2024-02-26 09:47:27
00