计数学习小记(Counting learning notes)-其他

计数学习小记(Counting learning notes)

（Polya以后再更新）

基本方法

• dp
• 组合数学
• 多项式
• 其他

$$dp$$应该是比较早接触也是花样最多的一类方法，一般需要考虑到状态的设立和优化，方程的转移等部分。

不重

• 无标号计数：这种一般来说这种是很难的问题，因为一般的计数都需要有一个基准，而这很经常是标号。
• 统计的不是形成方案的方法，而是方案：很多的生成方法是会生成重复的方案的，当然这个生成方法可能是你自己决定的或者题目给出的。

容斥

$$n$$个点之间两两配对，要求配对点之间的路径覆盖整棵树，求方案数对$$10^9+7$$取模
$$1\leq n\leq 5000$$

$$n$$个点之间两两配对，要求配对点之间的路径覆盖整棵树，求方案数对$$10^9+7$$取模
$$1\leq n\leq 5000$$

奇偶染色

$$1\leq N\leq 10^7$$

$$1\leq N\leq 10^7$$

组合数$$\rightarrow$$矩阵乘法

$\left(\sum_{i=0}^\infty \binom{nk}{ik+r}\right)\% p$$$1\leq n\leq 10^9,0\leq r<k\leq 50$$

$$1\leq n\leq 10^9,0\leq r<k\leq 50$$

期望X计数

$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -$$不是我就对了

$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -$$不是我就对了

幂次

$$1\leq n,m\leq 500$$

$$1\leq n,m\leq 500$$

统计

• 使用$$dp$$统计：考虑方程是否会存在让某个状态的所有方案的加值的情况，那么此时需要额外记录一个方案数的数组。
• 组合意义考虑：比如上面的幂次小结中便是用组合意义转化为了一般计数题。
• 单独考虑单个东西产生的贡献。

好题

• P6499-[COCI2016-2017#2]Burza
• 51nod1667-概率好题
• 51nod1597-有限背包计数问题
• [AGC013E]Placing Squares
• CF1286D-LCC
————————

preface

Idle boring, too lazy to do questions, it’s better to have a blog.

Although he has always been a perceptual question player, the rational level is indeed a very important method to analyze the preliminary practice of the question.

Well, it won’t involve specific knowledge points, but just summarize the more ingenious methods encountered when doing questions.

Please forgive me for chaotic typesetting

Also, I am sorry for the mistakes or imperfections in the dishes / KK

(Polya to update later)

Basic method

In terms of the basic method of counting, it can be roughly summarized into several categories

• dp
• Combinatorial mathematics
• polynomial
• other

$$DP$$ should be a kind of method with early contact and the most patterns. Generally, it is necessary to consider the establishment and optimization of States, the transfer of equations and so on.

Combinatorial mathematics is mainly obtained by finding out the combinatorial meaning or formula of the problem.

Polynomials generally need to use generating functions, or they may be simple convolution.

However, in addition to the above common counting, there are some other flexible methods. Such problems can generally spread the overall counting problem to some small statistics: for example, the process of Sam counting substrings.

Of course, it may also be false counting (for example, the number of schemes that may actually be legal can be enumerated).

However, the above methods will not be repeated here, because this is only a water blog to summarize experience, not a blog to teach people to count.

Not heavy

The duplication problem should be the most easily encountered problem in normal counting. The statistical duplication scheme has a great impact on the practice, for example:

• Unlabeled counting: Generally speaking, this is a difficult problem, because general counting requires a benchmark, which is often labeled.
• Statistics are not the method of forming a scheme, but the scheme: many generation methods will generate duplicate schemes. Of course, this generation method may be determined by yourself or given by the topic.

These two cases are common. When our count is repeated, we need to consider changing methods to remove the duplicate or ignore the duplicate part.

Tolerance and exclusion

Ah, it’s another big topic. Of course, tolerance and exclusion have two functions: one is to remove repetition, and the other is to ensure the legitimacy of restrictions.

For example, the classic mismatch problem:
We can enumerate at least how many locations we have are illegal (set to \ (K \), and then the illegal locations are fixed. The answer is

It is not difficult to find that one advantage of exclusion is that we do not need to count < strong > exactly < / strong >, but to fix some < strong > at least < / strong >, which can remove some troublesome restrictions, which is a very common use.

Another advantage of inclusion and exclusion is that our inclusion and exclusion coefficient can be directly multiplied in the scheme to save a lot of states (\ (DP \).

For example, take the title [arc101c] ribbons on tree:

\Pairing between (n \) points requires that the path between pairing points covers the whole tree, and the number of schemes is calculated to take the modulus of \ (10 ^ 9 + 7 \)
$$1\leq n\leq 5000$$

\Pairing between (n \) points requires that the path between pairing points covers the whole tree, and the number of schemes is calculated to take the modulus of \ (10 ^ 9 + 7 \)
$$1\leq n\leq 5000$$

Well, look at our restrictions. Each edge is covered at least once. Then, let’s say that if the specified \ (K \) edge cannot be covered, the tolerance and exclusion coefficient is \ ((- 1) ^ k \).
If we violently cut off the edges that do not need to be covered, let \ (f_{i, J, K} \) represent the scheme when the current connection block size in the subtree with \ (I \) as the root is \ (J \) and \ (K \) edges have been cut off.
Obviously, when cutting an edge, the tolerance and exclusion coefficient becomes a \ (- 1 \), so we don’t need to record it with state, but directly maintain the current scheme × The sum state of the inclusion exclusion coefficient is reduced to two dimensions.

As for a lot of inversion, I don’t think it needs to be introduced too much in this article.

Find benchmark

Benchmark is an indispensable thing in counting.

In terms of the simplest problem of crossing the river, the route number of soldiers we asked is actually an absolute path in space and time (that is, the order of walking).

If the question can be changed into asking how many different shapes the path of the river pawn can have (rotation or mirror image can also be regarded as repetition), then part of the datum is removed.

In some problems, the benchmark will not be given obviously, so normal counting may lead to a large number of heavy leaks. At this time, we need to find a good benchmark to count.

Take the number of unmarked roots as an example. The principle that we will not calculate the weight is that we sort all subtrees according to a certain law. At this time, we determine a benchmark.

For example, you can see p7888.

Model transformation

A big topic, most of the difficult counting problems will have some very complex conditions. We need to find a relatively simple condition to replace the original condition.

Of course, after the transformation, it is inevitable to calculate the weight according to the new conditions. At this time, it needs to be analyzed in detail.

Odd even dyeing

For a sequence containing \ (a, B, C \), you can select two adjacent sequences at a time, except for the deletion of \ (AB \) and \ (BA \).
Find how many sequences with length \ (n \) can be deleted.
$$1\leq N\leq 10^7$$

For a sequence containing \ (a, B, C \), you can select two adjacent sequences at a time, except for the deletion of \ (AB \) and \ (BA \).
Find how many sequences with length \ (n \) can be deleted.
$$1\leq N\leq 10^7$$

In the classic odd even coloring, the inversion of even positions is changed into deletion \ (AA / BB \), and then it is well counted.

Combinatorial number \ (\ rightarrow \) matrix multiplication

The most classic should be https://www.luogu.com.cn/problem/P3746

$\left(\sum_{i=0}^\infty \binom{nk}{ik+r}\right)\% p$$$1\leq n\leq 10^9,0\leq r<k\leq 50$$

seek

$$1\leq n\leq 10^9,0\leq r<k\leq 50$$

In fact, it is to select \ (x \) items from \ (NK \) items, which requires \ (x \% k = R \) and direct matrix multiplication.

Most problems can convert combinatorial meaning and DP into fast matrix multiplication.

Expected x count

Finite expectation questions are counting
$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ –$$ it’s not me

Finite expectation questions are counting
$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ –$$ it’s not me

But sometimes using the idea of expectation will make the problem easier.

Of course, normal counting is also feasible at this time, but generally speaking, when the total number of schemes in < strong > each step is uncertain but the probability can be determined, we might as well calculate the expectation first, and then multiply it by the total number of schemes to get the answer.

There was an example, but I couldn’t find it. / CY

power

Sometimes we need to count the sum of the power of the answer. Suppose it is \ (n ^ k \), we can convert it into an orderly and repeatable \ (K \) number among the \ (n \) numbers. At this time, we will convert a power problem into a more complex count.

Such as [noi2009] pipeline bead taking

Give a stack of size \ (n \) and a stack of size \ (m \), select one stack at a time to pop up the top of the stack, and then record this letter to find the quadratic sum of the pop-up schemes of all pop-up sequences.
$$1\leq n,m\leq 500$$

Give a stack of size \ (n \) and a stack of size \ (m \), select one stack at a time to pop up the top of the stack, and then record this letter to find the quadratic sum of the pop-up schemes of all pop-up sequences.
$$1\leq n,m\leq 500$$

The square of the scheme can be regarded as the scheme in which two people choose the same sequence.
Then \ (DP \) can be transferred.

Statistics

Sometimes counting questions not only need to count the number of schemes, but also the sum of a certain value under each scheme.

At this time, we generally have the following solutions

• Use \ (DP \) statistics: consider whether the equation will add value to all schemes in a certain state, then an additional array of schemes needs to be recorded at this time.
• Consideration of combinatorial meaning: for example, in the power summary above, the combinatorial meaning is transformed into a general counting problem.
• Consider the contribution of a single thing alone.

Good question

I don’t know what to write. Remember some good questions

• P6499-[COCI2016-2017#2]Burza
• 51nod1667 – good question of probability
• 51nod1597 finite knapsack counting problem
• [AGC013E]Placing Squares
• CF1286D-LCC