- 白王正在挑选容器。
标签：#
组合数学
「JXOI2018」游戏
她长大以后创业了，开了一个公司。 但是管理公司是一个很累人的活，员工们经常背着可怜偷懒，可怜需要时不时对办公室进行检查。
可怜公司有 n 个办公室，办公室编号是 l 到 l+n-1，可怜会事先制定一个顺序，按照这个顺序依次检查办公室。一开始的时候，所有办公室的员工都在偷懒，当她检查完编号是 i 的办公室时候，这个办公室的员工会认真工作，并且这个办公室的员工通知所有办公室编号是 i 的倍数的办公室，通知他们老板来了，让他们认真工作。因此，可怜检查完第 i 个办公室的时候，所有编号是 i 的倍数(包括 i )的办公室的员工会认真工作。
「HDU 6296」代码派对
比特镇的算法竞赛选手们应邀来到了小Q家中参加盛大的"代码派对"。小Q计划在家中举行一场ACM赛制的联谊赛，3个人为一队进行比赛。
「HDU 6397」Character Encoding
In computer science, a character is a letter, a digit, a punctuation mark or some other similar symbol. Since computers can only process numbers, number codes are used to represent characters, which is known as character encoding. A character encoding system establishes a bijection between the elements of an alphabet of a certain size n and integers from 0 to n−1. Some well known character encoding systems include American Standard Code for Information Interchange (ASCII), which has an alphabet size 128, and the extended ASCII, which has an alphabet size 256.
「CodeForces 1261D」Wrong Answer on test 233
This is the harder version of the problem. In this version, 1≤𝑛≤2⋅105. You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems.
The problem is to finish 𝑛 one-choice-questions. Each of the questions contains 𝑘 options, and only one of them is correct. The answer to the 𝑖-th question is ℎ𝑖, and if your answer of the question 𝑖 is ℎ𝑖, you earn 1 point, otherwise, you earn 0 points for this question. The values ℎ1,ℎ2,…,ℎ𝑛 are known to you in this problem.
「HDU 6184」Counting Stars
Little A is an astronomy lover, and he has found that the sky was so beautiful!
So he is counting stars now!
There are n stars in the sky, and little A has connected them by m non-directional edges.
It is guranteed that no edges connect one star with itself, and every two edges connect different pairs of stars.
组合数学公式
组合数
Cnm=n!m!(n−m)!C^m_{n} = \frac{n!}{m!(n-m)!}
Cnm=m!(n−m)!n!
多重集合排列数
n!a1!a2!a3!⋯ak!\frac{n!}{a_1! a_2! a_3! \cdots a_k!}
a1!a2!a3!⋯ak!n!
多重集合组合数(任意ni>=rn_i >= rni>=r)
Ck+r−1k−1C^{k-1}_{k+r-1}
Ck+r−1k−1
多重集合组合数
Ck+r−1k−1−∑i=1kCk+r−ni−2k−1+∑i=1kCk+r−ni−2k−1+⋯+(−1)k+1Ck+r−∑i=1kni−(k+1)k−1C_{k+r-1}^{k-1} - \sum_{i=1}^{k} C_{k+r-n_i-2}^{k-1} + \sum_{i=1}^{k} C_{k+r-n_i-2}^{k-1}+\cdots + (-1)^{k+1} C^{k-1}_{k+r -\sum_{i=1}^{k}n_i - (k+1)}
Ck+r−1k−1−i=1∑kCk+r−ni−2k−1+i=1∑kCk+r−ni−2k−1+⋯+(−1)k+1Ck+r−∑i=1kni−(k+1)k−1
卢卡斯定理
Cnm≡C(n mod p)(m mod p)×Cn/pm/p( mod p)C_{n}^{m} \equiv C_{(n \text{ mod } p)}^{(m \text{ mod } p)} \times C_{n / p}^{m / p} ( \text{ mod } p)
Cnm≡C(n mod p)(m mod p)×Cn/pm/p( mod p)
Catalan
Catn=C2nnn+1Cat_n = \frac{C_{2n}^{n}}{n+1}
Catn=n+1C2nn
错排方案数
d[i]=(i−1)∗(d[i−1]+d[i−2])d[i] = (i-1) * ( d[i-1] + d[i-2])
d[i]=(i−1)∗(d[i−1]+d[i−2])
N∗4N * 4N∗4 格子中用 1∗21 * 21∗2 或 2∗12 * 12∗1 填充的方案数
f(n)=f(n−1)+5⋅f(n−2)+f(n−3)−f(n−4)f(n) = f(n-1) + 5 \cdot f(n-2) + f(n-3) - f(n-4)
f(n)=f(n−1)+5⋅f(n−2)+f(n−3)−f(n−4)
N∗4N * 4N∗4 格子中用 1∗11 * 11∗1 或 2∗22 * 22∗2 填充的方案数
f(n)=2⋅f(n−1)+3⋅f(n−2)−2⋅f(n−3)f(n) = 2 \cdot f(n-1) + 3 \cdot f(n-2) - 2 \cdot f(n-3)
f(n)=2⋅f(n−1)+3⋅f(n−2)−2⋅f(n−3)
Read More ~
「HDU 6185」Covering
Bob's school has a big playground, boys and girls always play games here after school.
To protect boys and girls from getting hurt when playing happily on the playground, rich boy Bob decided to cover the playground using his carpets.
Meanwhile, Bob is a mean boy, so he acquired that his carpets can not overlap one cell twice or more.
「CodeForces 407C」 Curious Array
You've got an array consisting of n integers: a[1], a[2], ..., a[n]. Moreover, there are m queries, each query can be described by three integers li, ri, ki. Query li, ri, ki means that we should add to each element a[j], where li ≤ j ≤ ri.
Record means the binomial coefficient, or the number of combinations from y elements into groups of x elements.
You need to fulfil consecutively all queries and then print the final array.
「AtCoder 133E」 Virus Tree 2
You are given a tree with N vertices and N−1 edges. The vertices are numbered 1 to N, and the i-th edge connects Vertex ai and bi.
You have coloring materials of K colors. For each vertex in the tree, you will choose one of the K colors to paint it, so that the following condition is satisfied:
If the distance between two different vertices x and y is less than or equal to two, x and y have different colors.
How many ways are there to paint the tree? Find the count modulo 1 000 000 007.