Solutions

题面 有一个 $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 计数。旋转 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

题意 摆。 题解 用背包维护不定点，套 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

题目 给定一个 $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

[清华集训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

题解 经典结论 $$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

[省选联考 2020 A 卷] 组合数问题 题目描述 给定整数 $n$ , $x$ , $p$ ，一个 $m$ 次多项式 $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$ ，计算 $$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p $$ $1\le n, …

Jayun 发布于 2024-02-23 10:25:17

00

题意 给定一棵树，在树上选 3 个点，要求两两距离相等，求方案数。 $n\leq5000$ 。 题解 枚举中间点，设 $f_i,g_i,h_i$ 分别表示深度 $i$ 时扫过的子树中选 1、2 个点的方案数和当前子树选一个点的方案数。 代码 const int N = 5010; inline ll Read() { ll x = 0, f = 1; char c = getcha …

Jayun 发布于 2024-02-22 21:38:27

00

[ARC114F] Permutation Division 题面 给定一个 $1\sim n$ 的排列。 Alice 要把它分成 $k$ 段，Bob 要把这 $k$ 段重排使得字典序最大。 问 Alice 的所有划分方式中最终得到的字典序最小的排列是什么。 $k\le n\le 2\times10^5$ 。 题解 让原排列和新排列 LCS 尽量长。二分之，在 $[1,x]$ 内 …

Jayun 发布于 2024-02-22 20:31:15

00