标签 组合数学 下的文章

「Codeforces 1204E」Natasha, Sasha and the Prefix Sums

题目链接：Codeforces 1204

Natasha 最喜欢的数字是 $n$ 和 $1$，Sasha 最喜欢的数字是 $m$ 和 $-1$。某一天他们写下了长度为 $n + m$ 且包含恰好 $n$ 个 $1$ 和 $m$ 个 $-1$ 的所有可能的序列。对于每一个序列计算出它的最大前缀和（允许为空）；形式化地，我们定义 $f(a)$ 表示序列 $a_{1, \dots, l}(l \le 0)$ 的最大前缀和，那么有：

$$ f(a) = \max \left (0, \max _ {i = 1} ^ {l} \sum _ {j = 1} ^ {i} a_{j} \right ) $$

现在他们想要对于所有满足条件的序列，求出 $f(a)$ 的总和。答案对 $998244853$ 取模。

数据范围：$0 \le n, m \le 2000$。

「SPOJ 16607」IE1 - Sweets

题目链接：SPOJ 16607

John 有 $n$ 个水果罐子，每个罐子都装有不同种类的糖果，第 $i$ 个罐子里有 $m_i$ 个糖果。John 决定吃一些糖果，并且打算至少吃 $a$ 个，至多吃 $b$ 个，求一共有多少种吃法。答案对 $2004$ 取模。

数据范围：$1 \le n \le 10$，$0 \le a \le b \le 10 ^ 7$，$0 \le m_i \le 10 ^ 7$。

「ARC 102C」Stop. Otherwise...

题目链接：ARC 102C

Takahashi 有 $n$ 个骰子，每个骰子有 $k$ 个面分别标号为 $1$ 到 $k$。对于每个 $i = 2, 3, \dots, 2k$，求满足以下条件的方案数对 $998244353$ 的值。

• 投掷这 $n$ 个骰子，没有任何两个不同骰子的数字之和为 $i$。

注意骰子之间是相同的。也就是说，当存在整数 $k$ 使得两个方案数数字 $k$ 的骰子数量不同，那么这两个方案被认为是不同的。

数据范围：$2 \le n \le 2000$，$1 \le k \le 2000$。

「Codeforces 1113F」Sasha and Interesting Fact from Graph Theory

题目链接：Codeforces 1113F

在本题中，树是一个加权连通图，由 $n$ 个节点和 $n-1$ 条边组成，边的权值为 $1$ 到 $m$ 的整数。一棵树是美丽的，当且仅当对于给定的节点 $a$ 和 $b$，他们的距离恰好为 $m$。

请你求出有多少棵树是美丽的，答案对 $10^9+7$ 取模。两棵树是不同的，当且仅当一棵树上有一条边，而另一棵树上没有这条边。

数据范围：$2\le n\le 10^6$，$1\le m\le 10^6$，$1\le a,b\le n$，$a\neq b$。