计数学习小记(Counting learning notes)

前言

闲的无聊懒得做题不如来水点博客。

虽然一直作为一个感性做题的选手,但是理性层面上确实是分析题目初步做法的一个十分重要的方法。

额不会涉及具体的知识点,只是总结点自己做题的时候遇到的比较巧妙的方法。

混沌排版请见谅

还有我也很菜有错误或者不完善的地方见谅/kk

(Polya以后再更新)

正题

基本方法

计数的基本方法来说的话大致能总结为几类

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

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

组合数学的话主要通过找出题目的组合意义或者推式子得到。

而多项式一般都是需要使用生成函数,也有可能是简单的卷积。

然而除了上面常见的计数,存在一些其他灵活性的方法,这类的题目一般都能够将整体的计数问题分散到一些小的统计上:比如说SAM进行子串计数的过程。

当然也有可能是假计数(比如实际上可能合法的方案数能够枚举完的)。

不过这里不会赘述上面的几种方法,因为这只是个总结经验的水博客,不是教人计数的博客。

不重

重复问题应该是在正常的计数中最容易遇到的问题,统计重复的方案对做法造成的影响很大,比如来说:

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

比较常见的应该就这两种情况了,当我们的计数出现重复的时候就需要考虑换方法来去掉重复或者不计重复的部分。

容斥

啊又是一个很大的专题,当然容斥是有两种作用的,一种是来去掉重复,一种是保证限制的合法。

比如经典的错排问题:
我们可以枚举我们至少有多少个位置是不合法的(设为\(k\)个),那么不合法的位置就固定了,答案就是

不难发现容斥的一个好处是我们不需要去统计恰好,而是去固定一些至少,这样可以去掉一些麻烦的限制,这是一个很常见的用处。

容斥还有一个好处是我们的容斥系数可以直接乘在方案中以节省很多的状态(\(dp\)来说)。

比如以题目[ARC101C] Ribbons on Tree来说:

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

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

额看看我们的限制,每条边都被覆盖至少一次,那么我们容斥来说就是如果钦定\(k\)条边不能被覆盖,容斥系数就是\((-1)^k\)。
我们暴力切断不需要覆盖的边,那么设\(f_{i,j,k}\)表示以\(i\)为根的子树中目前联通块大小为\(j\),已经切断了\(k\)条边时的方案。
显然的切断一条边的时候容斥系数成了个\(-1\),那么我们完全没有必要用状态记录它,而是直接维护目前的方案×容斥系数的和状态就缩成两维了。

至于很多的反演我认为这不需要在此篇中过多介绍。

寻找基准

基准是一个计数中不可或缺的东西。

拿最简单的过河卒问题来讲,我们询问的兵的路线数量实际上是一个绝对的空间和时间(也就是走的顺序)的路径。

如果问题可以变为询问过河卒的路径能有多少种不同的形状(旋转或者镜像得到的也算重复),那么就是去掉了部分的基准。

而有的问题中基准并不会明显的给出,所以可能正常的计数会导致大量的重漏,此时我们需要寻找一个好的基准来计数。

拿无标号有根数的计数来讲,我们不会算重的原理就是说我们将所有的子树按照一定的规律进行了排序,此时就是确定了一个基准。

例题的话可以看P7888。

模型转换

一个很大的话题,大部分的难的计数题都是会有一些十分复杂的条件的,需要找到一个比较简单的条件来替换掉原来的条件。

当然的变换之后不可避免地会有按照新的条件来计的话算重的可能性,此时就需要具体分析了。

奇偶染色

比如[AGC040C]Neither AB nor BA:

一个包含\(A,B,C\)的序列,每次可以选择相邻的两个除了\(AB\)和\(BA\)的删去。
求有多少个长度为\(N\)的序列可以删完。
\(1\leq N\leq 10^7\)

一个包含\(A,B,C\)的序列,每次可以选择相邻的两个除了\(AB\)和\(BA\)的删去。
求有多少个长度为\(N\)的序列可以删完。
\(1\leq N\leq 10^7\)

经典的奇偶染色,把偶数位置的取反就变为了删除\(AA/BB\)然后就很好统计了。

组合数\(\rightarrow\)矩阵乘法

最经典的应该是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\)

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

其实就是在\(nk\)个物品中选出\(x\)个物品,要求\(x\%k=r\),直接矩阵乘法即可。

而大部分问题可以将组合意义和dp相互转换来转换成快速的矩阵乘法。

期望X计数

有限的期望题都是计数
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -\)不是我就对了

有限的期望题都是计数
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -\)不是我就对了

但是有时候运用期望的思想会让问题更加的简单。

当然一般这种时候正常的计数也是可行的,只不过一般来说在每一步的总方案数不确定但是概率能确定的情况下我们不妨先算出期望再乘上总共的方案数就能得到答案。

原本有道例题的,但是找不到了/cy

幂次

有时候我们会需要统计答案幂次的和,假设是\(n^k\),我们可以将转换为在\(n\)个数中选出有序可重的\(k\)个数,此时我们就将一个幂次的问题转换为了一个较为复杂的计数。

如[NOI2009]管道取珠

给出一个大小为\(n\)和一个大小为\(m\)的栈,每次选择一个栈弹出栈顶然后记录这个字母,求所有弹出序列的弹出方案的二次方和。
\(1\leq n,m\leq 500\)

给出一个大小为\(n\)和一个大小为\(m\)的栈,每次选择一个栈弹出栈顶然后记录这个字母,求所有弹出序列的弹出方案的二次方和。
\(1\leq n,m\leq 500\)

方案的平方可以视为两个人选出同一个序列的方案。
然后\(dp\)转移即可。

统计

有的时候计数题不仅需要统计方案数,而是每个方案下某个值的和。

此时我们一般有以下解决方案

  • 使用\(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)

Topic

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

比如[AGC040C]Neither AB nor BA:

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