标签 组合数学 下的文章
- 首页
- 组合数学
「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$。