在讨论《警示后人》回复：

谢谢你qwq

划分数是一个非常常见的问题。 给定一个整数 $n$，求有多少种划分方式。 如 $4=3+1=2+1+1$。 ## 一、$O(n^2)$ 算法 设把 $i$ 划分成 $j$ 个数有 $f(i,j)$ 种分法。 ### 1.完全背包 直接 DP 每个数字取了多少次 $f(i,j)=f(i-k,j-1)$ 由于我们并不在意具…

## AT_joisc2018_d 修行 ### 题意 求有多少个长为 $N$ 排列 $P$ 满足： $$N-K=\sum\limits_i[P_i >n>>k; fac[0]=1; for(int i=1;i<=n+1;i++)fac[i]=fac[i-1]*i%mod; for(int i=1;i<=k;i++)a…

公式中的 `(x=y=0)` 应改为 `x=0 或 y=0`

```cpp #include #define lowbit(x) (x&-x) #define pii pair #define mp make_pair #define A first #define B second using namespace std; const int N=1e5+10; int n,c…

在讨论《本题可能存在简单的单log解法》回复：

%%%

在讨论《如果你50pts》回复：

谢谢

$n$ 不会爆 int，但 $n+1$ 会，所以写循环时注意开 longlong。

## 前言 基础容斥，建议降绿 ## 题解 根据容斥原理，答案为：保留 $4$ 条边的方案数-保留 $3$ 条边的方案数+保留 $2$ 条边的方案数-保留 $1$ 条边的方案数+保留 $0$ 条边的方案数，组合数计算即可。 注意 $1e6+7=29\times 34483$。 ## 代码 ```cpp #include…

## UVA12633 Super Rooks on Chessboard ### 前言 这有黑？纯纯细节题。 ### 题解 很容易想到容斥。设能被行攻击的格子集合为 $R$，能被列攻击的格子集合为 $C$，能被对角线攻击的格子集合为 $D$，那么答案就为 $n\times m-|R|-|C|-|D|+|R\cap C…

## 你能在不会虚数的情况下通关 FFT 吗？ ### 0.前言 本文主要是为了萌新 OIer 快速入门 FFT 而准备的，所以大部分证明将会跳过，想看证明请去别的文章。 众所周知 OI 不考证明。如果你觉得能在考场写出 FFT 并正确使用就够了，并不想了解详细证明，那么这篇文章可能适合你。 前置知识：[多项式与生成函…

## [ABC231G] Balls in Boxes ### 题解 我们记 $b_i$ 为 $i$ 被选中的次数，那么期望得分为 $$\frac{1}{n^k}\sum\limits_{b_1+b_2+\dots+b_n=k}\dbinom{n}{b_1,b_2,\dots,b_n}\prod\limits_{i=1…

本文着重讲解三元环计数问题。 ## 三元环计数 ### 题意 给你 $n$ 个点 $m$ 条边的无向图，求三元环的个数。$m\le 2\times10^5$。 ### 题解 先考虑暴力。 枚举三元环中的其中一个点 $u$，再枚举 $u$ 邻域中的一个点 $v$，再枚举 $v$ 邻域中的一个点 $w$，判断 $w$ 是否…

当一个三元环的三个点度数相等时，可能会将三个点连成环，这样无法统计到这个环。 正确做法是当两个点度数相等时，将编号小的连向编号大的。

## [ARC078F] Mole and Abandoned Mine ### 前言 看了前两篇题解，一篇时间复杂度不对，一篇排版太乱根本不可读，于是我打算写一篇更好的题解。 ### 题意 $n$ 个点 $m$ 条边的简单带权无向连通图，要求割掉若干条边，使 $1$ 到 $n$ 只有 $1$ 条路径，问割掉的边权和最…

翻译不符合 $\LaTeX$ 格式，且明显是机翻。 翻译如下： 给你一棵 $n$ 个点的树，你需要选择若干个点将其染成黑色，染一个点费用为 $k$。对于每个点，他的花费为离它最近的点的距离。求最小总花费，求出其中一种方案。 ``` 给你一棵 $n$ 个点的树，你需要选择若干个点将其染成黑色，染一个点费用为 $k$。 对…

在讨论《请求修改翻译》回复：

修正： ``` 给你一棵 $n$ 个点的树，你需要选择 $k$ 个点将其染成黑色。对于每个点，他的花费为离它最近的黑点的距离。求最小总花费，求出其中一种方案。 ```

在讨论《请求修改翻译》回复：

@10circle @minstdfx

样例不符合 $\LaTeX$ 格式标准，且明显是机翻。 以下是我的翻译： 给你一棵 $n$ 个点的树，你需要选择 $k$ 个点将其染成黑色。对于每个点，他的花费为离它最近的点的距离。求最小总花费，求出其中一种方案。 ``` 给你一棵 $n$ 个点的树，你需要选择 $k$ 个点将其染成黑色。对于每个点，他的花费为离它最近…

在讨论《【集中处理】升学/换校快速处理》回复：

367521 华南师范大学附属中学

## 题意 给你一个 $N$ 个数的数组 $a$，$Q$ 个区间和一个整数 $M$。你最多能选 $M$ 个 $a$ 的数使它变成 $0$，求 $\sum\limits_{i=1}^Q\max\limits_{j=l_i}^{r_i}a_j$ 的最小值。 ## 题解 对于每个区间，我们只关注最大值，所以我们从大到小考虑每…

对于每个区间，我们只关注最大值，所以我们考虑从大到小填数。 当我们填了一个数时，由于是从大到小填，所以可以立刻处理所有跨过这个点的区间。那么此时就能将问题分裂为两个子问题。 举个例子：当我们处理 $[l,r]$ 中的问题时，当我们在位置 $x$ 填了一个数 $y$，那么就能分裂为两个子问题：$[l,x-1]$ 中填 $…

在讨论《【11.22 更新】CSP-J/S 2024 年奖项认证分数线测定》回复：

$7$ 级已经没含金量了（悲 盲猜很快金钩含金量也会掉

众所周知，当一棵树求出 DFS 序后，可以将子树拍成区间。这时，BIT 就能处理很多树上问题。 1. 单点加，子树求和 - 其实就是单点加，区间求和。 2. 单点加，链求和 - 维护每个点到根的和，那么单点加相当于子树加。 - 链求和拆成到根的链（下同），那么链求和相当于单点查。 3. 子树加，单点查 - 其实就是区间…

在讨论《求估 GD S 组一等线》回复：

180(如果按【前20%一等】算的话)

在讨论《哪位大神补充一下我的代码，AC必关》回复：

意思是让我们帮你写代码吗

在讨论《警示后人》回复：

太恶心了

在讨论《建议升紫》回复：

zc

在讨论《请求降黄》回复：

@[cly312](/user/437243) @[SuperAlex4](/user/179187) 刚刚开的

在讨论《请求降黄》回复：

感谢管理员开放题解通道