CF865G tutorial

Now all the tutorial I can find is to use GF and the poly multiplication. I can provide a slower but more beginner-friendly solution.

Hint

How would you naively count the number of ways to get exactly​ $$$K$$$ chocolates in a basket?

There is a classic technique to optimize them.

Note $$$c_i$$$ is small but $$$p_i$$$ is big.

Note $$$F$$$ and $$$B$$$ are small.

Step 1

A straightforward way to compute ways to get exactly $$$K$$$ chocolates in a basket is to write dp.

Let $$$f[i]$$$ be the number of ways to get exactly $$$i$$$ chocolates.

Let $$$b[i]$$$ the number of boxes whose length is $$$i$$$.

We can enumerate the last size of boxes to get a transition.

$$$f[i]=\sum_j b[j]f[i-j]$$$

Use matrix exponentiation​ to speed up th procudure if the maximum chocolate count we need is not too large.

Step 2

Note that $$$p_j\leq 10^9,n\leq 10^18$$$ and we cannot use the previous method to compute.

We change the perspective: instead of tracking total petals, we track the number of bouquets. Let $$$g[i][j]$$$ be the number of ways to collect $$$i$$$ bonquets already but $$$j$$$ extra chocolates. Then we can transition it by enumerate the next flower and use the previous $$$f$$$.

And we can also speed up it by matrix exponentiation​.

Step 3

But this get TLE. Why?

1. use % less
2. add constant optimize everywhere ,especially matrix exponentiation​
3. use #pragma

code

目前我能找到的所有题解都使用了生成函数（GF）和多项式乘法。我将提供一个虽然较慢，但对初学者更友好的解法。

Hints

如何用朴素的方法计算**恰好**得到 $$$K$$$ 块巧克力的方案数？

这里有一个经典的优化技巧。

注意：$c_i$ 很小，但 $$$p_i$$$ 很大。 注意 $$$F$$$ 和 $$$B$$$ 也很小。

Step 1

计算恰好得到 $$$K$$$ 块巧克力方案数的一个直接方法是动态规划（DP）。

设 $$$f[i]$$$ 为恰好得到 $$$i$$$ 块巧克力的方案数。

设 $$$b[i]$$$ 为长度为 $$$i$$$ 的盒子的数量。

我们可以枚举最后一个盒子的尺寸来进行状态转移。

$$$f[i]=\sum_j b[j]f[i-j]$$$

如果我们需要计算的最大巧克力数量不是特别大，可以使用矩阵快速幂来加速这个过程。

Step 2

注意 $p_j\leq 10^9, n\leq 10^{18}$，我们不能直接使用之前的方法计算。

我们转换一下思路：不再追踪总花瓣数，而是追踪花束的数量。设 $$$g[i][j]$$$ 为已经收集了 $$$i$$$ 个花束，但还额外剩下 $$$j$$$ 块巧克力的方案数。然后，我们可以通过枚举下一朵花，并利用之前计算好的 $$$f$$$ 来进行状态转移。

同样，我们可以用矩阵快速幂来加速。

Step 3

但这可能会超时（TLE）。为什么？

1. 减少取模运算（%）的使用
2. 在所有地方添加常量优化，特别是矩阵快速幂部分
3. 使用 #pragma 编译优化指令

code

Tutorial for CF1167G

English Version

Hints

What stops the rotation?

A brute-force solution is straightforward, but how can we optimize it?

Step 1

There are two cases in which the rotation stops:

1. the ray touches the building
2. the building touches another building.

In the second case, write the left building is $$$x$$$ sway from the bending point and the right one is $$$y$$$ away from the bending point.

With some geometry knowledge, the angle is

$ \alpha=\begin{cases} \tan^{-1}(\frac{1}{x}) & x=y\ \tan^{-1}(\frac{1}{\max(x,y)}) & |x-y|=1\ \textrm{useless} & \textrm{otherwise} \end{cases} $

In the third case , they won't reach each other.

So we can easily write a brute force $$$O(nm)$$$.

code

Step 2

The crucial idea is that if $$$|x| \gt 7000$$$, we don't need to calculate it.

It's because, due to the "not sparse" condition that two buildings have already touched each other , or a building has already touched the ray.

Now it comes down to $$$O(md)$$$.

Step 3

If we can represent the state before and after rotation using arrays, we only need to find positions where both values are equal to $$$1$$$.It's easy to speed up it with bitset.

Note: some buildings may be included in the bitset but are not actually activated. A set is used to check whether a building is valid.

$$$O(\frac{md}{w})$$$

code

Step 4

Handwrite bitset !

code

Reference

https://mirror.codeforces.com/blog/entry/67058

https://www.cnblogs.com/yijan/p/bitset.html

中文版

Hint

是什么阻止了旋转？

暴力解法是显然的，但该如何优化？

Step 1

旋转停止有两种情况：

1. 射线碰到某一栋建筑；
2. 一栋建筑碰到了另一栋建筑。

在第二种情况下，设左边的建筑距离转折点为 $x$，右边的建筑距离转折点为 $y$。

利用一些几何知识，可以得到停止时的角度：

$ \alpha= \begin{cases} \tan^{-1}\left(\frac{1}{x}\right) & x = y \ \tan^{-1}\left(\frac{1}{\max(x,y)}\right) & |x — y| = 1 \ \text{无意义} & \text{其他情况} \end{cases} $

在第三种情况下，两栋建筑不会相互接触。

因此，我们可以很容易地写出一个时间复杂度为 $$$O(nm)$$$ 的暴力算法。

代码

Step 2

关键的观察是：当 $$$|x| \gt 7000$$$ 时，我们不需要再进行计算。

这是因为在“不稀疏”的条件下，更近的两栋建筑已经发生接触，或者某一栋建筑已经先接触到了射线。

因此，时间复杂度可以降低到 $O(md)$。

Step 3

如果我们能用数组表示旋转前后的状态，那么只需要找到前后状态都为 (1) 的位置即可。

使用 bitset 可以很容易地对这一过程进行加速。

注意：有些建筑可能被计入 bitset 中，但实际上并未被激活，因此需要使用一个集合来判断其有效性。

时间复杂度为：

$ O\left(\frac{md}{w}\right) $

代码

Step 4

手写 bitset！

代码

参考资料

https://mirror.codeforces.com/blog/entry/67058

https://www.cnblogs.com/yijan/p/bitset.html

English version

Hints

How to choose the edges greedily?

In which cases does the greedy method fail?

How can we find the extra non-tree edges?

Solution

Step1

First, sort the edges by weight.

If the first $$$n-1$$$ edges don't form a tree, they already form the minimum spanning tree (MST) -- that's the answer.

Step2

If the first $$$n-1$$$ edges form a tree,consider adding a extra edge with weight $$$w$$$ outside the tree that creates a cycle. Remove a edge with weight $$$w_0$$$ from the tree, keeping the cycle, increasing the answer by $$$w-w_0$$$.

The problem reduces to finding the maximum weight of the edge outside path $$$(u,v)$$$ (i.e. $$$\max\limits_{e\in E,e\not \in path(u,v)}w(e)$$$).

This can be done efficiently using binary lifting, taking care of corner cases at the LCA (Lowest Common Ancestor).

Step3

If more than $$$2$$$ edges are removed from the tree, we can show that replace $$$e_{n-1},e_{n-2}$$$ with $$$e_{n+1},e_{n}$$$ is the case to consider.

Step4

Putting everything together, we obtain a $$$O(n\log n)$$$ approach, which is efficient and clean.

Code

Code

Reference

Codeforces Round 1069 Editorial

中文版本

Hints

如何贪心地选择边？

贪心方法在哪些情况下会失败？

我们如何找到额外的非树边？

Step1

首先，按权重对边进行排序。

如果前 $$$n-1$$$ 条边不构成一棵树，那么它们已经构成了最小生成树（MST）——这就是答案。

Step2

如果前 $$$n-1$$$ 条边构成了一棵树，考虑添加一条权重为 $$$w$$$ 的树外额外边，这会创建一个环。从树中移除一条权重为 $$$w_0$$$ 的边，同时保留环结构，使得答案增加 $w — w_0$。

问题转化为寻找路径 $$$(u, v)$$$ 外部的边的最大权重（即 $\max\limits_{e \in E, e \notin \text{path}(u,v)} w(e)$）。

这可以通过使用**树上倍增**来高效完成，并注意 LCA 处的边界情况。

Step3

如果从树中移除超过 $$$2$$$ 条边，我们可以考虑用 $$$e_{n+1}$$$ 和 $$$e_n$$$ 替换 $$$e_{n-1}$$$ 和 $$$e_{n-2}$$$ 的情况。

Step4

将所有部分结合起来，我们得到了一个 $$$O(n \log n)$$$ 的方法，该方法高效且清晰。

代码

Code

参考

Codeforces Round 1069 题解

Two language versions are available in order to serve both codeforces and luogu community.

English Version

Hints

• What's the necessary condition for $$$a_1^\prime\replacedVerb {&}a_2^\prime\cdots\replacedVerb {&}a_n^\prime=X$$$ to hold?

• How can we ensure $$$a_1^\prime\replacedVerb {&}a_2^\prime\cdots\replacedVerb {&}a_n^\prime$$$ is exactly equal to $$$X$$$?

• Pay attention to some corner cases.

• How can we optimize the procedure?

Solution

Step 1

We begin by considering a straightforward $$$O(nq)$$$ approach.

A necessary condition for $$$a_1^\prime\replacedVerb {&}a_2^\prime\cdots\replacedVerb {&}a_n^\prime=X$$$ to hold is that each modified value $$$a_i^\prime$$$ must satisfy $$$a_i^\prime\replacedVerb {&}X=X$$$.

So define $$$up_X(a_i)$$$ is the minimum non-negative integer such that $$$(a_i+up_X(a_i))\replacedVerb {&}X=X$$$. Let $$$b_i=a_i+up_X(a_i)$$$. To compute $$$up_X(x)$$$,we locate the highest bit $$$B$$$ (if any) where the binary representations of $$$x$$$ and $$$X$$$ differ.Then set it to $$$1$$$ and keep the lower bits conform to $$$X$$$.

After adjustment,let $$$Y=b_1\replacedVerb {&}b_2\cdots\replacedVerb {&}b_n$$$. It satisfies that $$$Y\replacedVerb {&}X=X$$$.

Next, we need to ensure that $$$Y$$$ is exactly equal to $$$X$$$. Similarly, locate the highest bit $$$B$$$ (if any) and turn it to $$$0$$$. If $$$b_k$$$ is modified to turn $$$B$$$ bit to $$$0$$$. It can be shown that optimally, only one operation on a single element is sufficient to correct all lower differing bits as well.

When $$$n\ge 2$$$, a potential issue arises: if we modify $$$b_k$$$ on a bit where every element except $$$b_k$$$ is $$$1$$$ , $$$Y\neq X$$$ again. To avoid this, it is generally optimal to operate on an element other than the one that would cause such a conflict.

Based on this, we can easily write a $$$O(nq)$$$ code and submit.

Code for reference.

Step 2

After we get $$$Y$$$, we try to speed up the procedure.

Let the bits of $$$X$$$ be denoted as $$$x_1,x_2\cdots x_k$$$ in descending order.

We process the bits from the highest to the lowest. At the $$$i$$$-th time,all $$$a_i$$$ which contains $$$x_1,x_2\cdots,x_{i-1}$$$ but not $$$x_i$$$ are processed. It can be calculated by AND Fast Walsh-Hadamard Transform (FWT) and the Principle of Inclusion-Exclusion (PIE).

Code for reference.

Step 3

To make $$$Y$$$ exactly $$$X$$$, we identify the highest bit $$$B$$$ where $$$X$$$ and $$$Y$$$ differ. We then look for an element $$$a_k$$$ such that modifying it minimizes the number of operations required and it won't add new bits to $$$Y$$$.

Let $$$b$$$ be the highest bit changed in Step 2. We enumerate $$$[b+1,20]$$$. If at digit $$$i$$$, $$$0$$$ exists at least twice,find the number with with the largest value in the lower $$$i$$$ bits (i.e. $$$a_k\replacedVerb {&}(2^i-1)$$$) and compute it in $$$O(1)$$$ time.

Note the special case where $$$X=Y$$$.

Code for reference.

中文版本

Hint

• 要使 $$$a_1^\prime\replacedVerb {&}a_2^\prime\cdots\replacedVerb {&}a_n^\prime=X$$$ 成立的必要条件是什么？

• 如何确保 $$$a_1^\prime\replacedVerb {&}a_2^\prime\cdots\replacedVerb {&}a_n^\prime$$$ 恰好等于 $X$？

• 注意一些边界情况。

• 如何加速操作过程？

Solution

Step 1

我们首先考虑一个直接的 $$$O(nq)$$$ 方法。

要使 $$$a_1^\prime\replacedVerb {&}a_2^\prime\cdots\replacedVerb {&}a_n^\prime=X$$$ 成立的一个必要条件是每个修改后的值 $$$a_i^\prime$$$ 必须满足 $a_i^\prime\verb|&|X=X$。 因此定义 $$$up_X(a_i)$$$ 是满足 $$$(a_i+up_X(a_i))\replacedVerb {&}X=X$$$ 的最小非负整数。令 $$$b_i=a_i+up_X(a_i)$$$。为了计算 $$$up_X(x)$$$，我们找到 $$$x$$$ 和 $$$X$$$ 的二进制表示中不同的最高位 $B$（如果存在）。然后将其设置为 $1$，并将低位调整为符合 $X$。

调整后，令 $Y=b_1\verb|&|b_2\cdots\verb|&|b_n$。它满足 $Y\verb|&|X=X$。

接下来，我们需要确保 $$$Y$$$ 恰好等于 $$$X$$$。类似地，找到不同的最高位 $$$B$$$（如果存在）并将其变为 $$$0$$$。如果修改 $$$b_k$$$ 将 $$$B$$$ 位变为 0。可以证明，最优情况下，只需对单个元素进行一次操作即可同时纠正所有较低的不同位。

当 $$$n \ge 2$$$ 时，可能会出现一个问题：如果我们在某个位上修改 $$$b_k$$$，而除了 $$$b_k$$$ 之外的所有元素在该位上都是 1，那么 $$$Y \neq X$$$ 会再次出现。为了避免这种情况，通常最优的操作是选择一个不会引起这种冲突的元素。

基于此，我们可以轻松编写 $$$O(nq)$$$ 的代码并提交。

参考代码

Step 2

得到 $$$Y$$$ 后，我们尝试加速该过程。

将 $$$X$$$ 的位按降序表示为 $x_1,x_2\cdots x_k$。

我们从高位到低位处理这些位。在第 $$$i$$$ 次处理时，所有包含 $$$x_1,x_2\cdots,x_{i-1}$$$ 但不包含 $$$x_i$$$ 的 $$$a_i$$$ 将被处理。这可以通过卷积加容斥解决。

参考代码

Step 3

为了使 $$$Y$$$ 恰好等于 $$$X$$$，我们找到 $$$X$$$ 和 $$$Y$$$ 不同的最高位 $$$B$$$。然后我们寻找一个元素 $$$a_k$$$，使得修改它所需的操作次数最少，并且不会向 $$$Y$$$ 添加新的位。

令 $$$b$$$ 为第二步中改变的最高位。我们枚举 $$$[b+1,20]$$$。如果在第 $$$i$$$ 位，0 至少出现两次，则找到低 $$$i$$$ 位中值最大的数（即 $$$a_k\replacedVerb {&}(2^i-1)$$$）并在 $$$O(1)$$$ 时间内计算。

注意 $$$X=Y$$$ 的特殊情况。

参考代码

Reference

Pinely Round 5 editorial

Code with Vector

Code with Array

Observation

Based on my testing, arrays are significantly faster than vectors in this scenario—specifically, around 14 to 15 times faster.

Revelation

For parameter lists with fixed lengths, use arrays for better performance. When dealing with dynamic lengths, vectors are more efficient for faster coding. However, performance can still be optimized using pointers in either case.

Set algorithm Part I

Sometimes we may meet with some functions $$$S\rightarrow V$$$(S is a set,V is a value),and we need to handle some transformations on it.

The article is for beginners whick is much easy, and I may continously update the article.

There are some features.

First the problem always give small $$$n$$$,such as $$$n\leq 15,n\leq20$$$.

Second,the time complexity is always $$$O(n2^n),O(3^n),O(n^22^n)$$$.

Let's do some assumption:

The values form a ring and they contain ring operations like addition,substraction,multification or division in constant time.

FWT/FMT

The most classical one is FWT/FMT.

Problem

Define $$$a(S),b(S)(S\subseteq U)$$$ on a set.

Get all $$$c(S)=\sum\limits_{i \oplus j=S}a_ib_j\qquad \oplus \text{is} \ \textrm{and,or,xor}$$$

The general idea:
Let $$$a, b, c$$$ be maps (functions) from a set $$$S$$$ to a value domain $$$V=(N/Q/C\cdots)$$$. We define a transformation $$$\text{FWT}$$$ (Fast Walsh Transform) as a map from the space of such functions to itself, i.e.,

with the following properties:

1. Invertibility: $$$\text{FWT}$$$ has an inverse map $$$\text{FWT}^{-1}$$$.

2. Efficiency: $$$\text{FWT}$$$ can be computed in $$$O(n \log n)$$$ time.

3. Pointwise product property: For all $$$i \in S$$$,

Calculating $$$\mathrm{FWT(a),FWT(b)}$$$,then pointwise product between them and do the $$$\mathrm{FWT}^{-1}$$$,it's $$$c$$$.

I like cpp,so I use | for $$$\textrm{or}$$$,& for $$$\textrm{and}$$$,^ for $$$\textrm{xor}$$$.

OR FMT

a.k.a Zeta Transform,SOS DP,Yate's DP,Mobius Transform

The calculation is like this.

for(int o=1;o*2<=n;o<<=1)
    for(int i=0;i<n;i+=o<<1)
        for(int j=0;j<o;++j)
            a[i+j+o]=a[i+j+o]+a[i+j];

We first split the $$$a$$$ correspond to the current bit to $$$a_0,a_1$$$.Assume we are process the x-th bit,in the $$$a_k$$$ the x-th bit is $$$k$$$.We do a divide and conquer.Then

We difine the addition on $$$(S\rightarrow V)$$$ is addition on each on single element.

And its invertion transform is easy to find.

$$$\textrm{FWT}^{-1}$$$ a.k.a inverse Mobius Transform.

And verify the Pointwise product property.

Afterwards,I will omit some details.

AND FMT

for(int o=1;o*2<=n;o<<=1)
    for(int i=0;i<n;i+=o<<1)
        for(int j=0;j<o;++j)
            a[i+j]=a[i+j]+a[i+j+o];

It's the same as OR,because we can flip all the bits at the beginning and flip them back at the end.

XOR FWT

define $$$W(x,i)=popcount(x\wedge i)\bmod 2$$$

which satisfy $$$W(x,i\wedge j)=W(x,i)\wedge W(x,j)$$$

for(int o=1;o*2<=n;o<<=1)
    for(int i=0;i<n;i+=o<<1)
        for(int j=0;j<o;++j){
            ll x=f[i+j],y=f[i+j+o];
            f[i+j]=(x+y);
            f[i+j+o]=(x-y);
        }

Subset Sum Convolution

Problem

Define $$$a(S),b(S)(S\subseteq U)$$$ on a set.

Get all $$$c(S)=\sum\limits_{i\subseteq S}a(i)b(S\setminus i)$$$

The general idea by Intuition:

for $$$S$$$,calculate sum $$$a_ib_j$$$ of for all $$$i,j(|i|+|j|=S)$$$.

and only if $$$|i\cap j|=|S|$$$, it's valid. So do apply inclusion-exclusion principle on it,we can get the result.

Ranked Mobius Transform and inversion

define

the inverse

Fast Subset Convolution

define

one can show that

for(int mask = 0; mask < (1 << n); mask++) {
    fa[__builtin_popcount(mask)][mask] = a[mask];
    fb[__builtin_popcount(mask)][mask] = b[mask];
}
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        for(int mask = 0; mask < (1 << n); mask++) {
            if((mask & (1 << j)) != 0) {
                fa[i][mask] += fa[i][mask ^ (1 << j)];
                fb[i][mask] += fb[i][mask ^ (1 << j)];
            }
        }
    }
}
for(int mask = 0; mask < (1 << n); mask++) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            d[i][mask] += fa[j][mask] * fb[i - j][mask];
        } 
    }
}
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        for(int mask = 0; mask < (1 << n); mask++) {
            if((mask & (1 << j)) != 0) {
                h[i][mask] -= h[i][mask ^ (1 << j)];
            }
        }
    }
}
for(int mask = 0; mask < (1 << n); mask++)  c[mask] = h[__builtin_popcount(mask)][mask];

In the $$$\sum_{i\subseteq S}(-1)^{|S|-|i|}\sum_j \hat{a}(x,i)\hat{b}(|i|-x,i)$$$. for exact $$$S$$$, a pair of $$$U,V$$$ in $$$\hat{a},\hat{b}$$$ is calculated for

times.

So it's right.

Online Convolution (Luogu4221)

Let begin with the problem. P4221 [WC2018] 州区划分 — 洛谷

We can quickly solve the problem by DP.

The transitions are like $$$f(S)=\sum_{T\sub S} f(T)g(S-T)$$$,where $$$g$$$ is fixed.

The new transition need the previous transition, so how to transition quickly enough?

Add a dimension $$$i=|S|$$$,and use the subset convolution online. We can solve the problem.

Exercise

CF1713F

reorder $$$a_i=a_{n-i}$$$

get the diagnal c_i.

$$$a\rightarrow c \rightarrow b$$$ is a series of transforms ,so just do the inverse.

and calculate the contribution

code

QOJ13083

We see if $$$f(P)$$$ is certain,the mask of $$$P$$$ is easier to describe.

now the $$$f(P),f(Q)$$$ is limited by $$$S,T$$$,so enumerate $$$S,T$$$.

Do the FWT convolution (OR) $$$\hat{f}\times \hat{f}$$$

and handle some details.

code

Counting on the graph

Counting Tree Subgraph (No problem,compared with Matrix-Tree)

Given a simple undirected graph, count how many subgraph of it is a tree.

Obviously, we can use Matrix-Tree Theorem to solve it.

Input:

$$$n$$$ is number of vertixs, $$$m$$$ is the number of edges,and note the points are 1-indexed,output the $$$ans \bmod 992844353$$$.

The Matrix-Tree One

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

ll mod_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll mod_inv(ll a) {
    return mod_pow(a, MOD - 2);
}

ll det_mod(vector<vector<ll>> &mat, int n) {
    ll res = 1;
    for (int i = 0; i < n; i++) {
        int p = -1;
        for (int j = i; j < n; j++) {
            if (mat[j][i]) {
                p = j;
                break;
            }
        }
        if (p == -1) return 0;
        if (p != i) {
            swap(mat[i], mat[p]);
            res = (MOD - res) % MOD;
        }
        res = res * mat[i][i] % MOD;
        ll inv = mod_inv(mat[i][i]);
        for (int j = i; j < n; j++)
            mat[i][j] = mat[i][j] * inv % MOD;
        for (int j = i + 1; j < n; j++) {
            if (!mat[j][i]) continue;
            ll f = mat[j][i];
            for (int k = i; k < n; k++)
                mat[j][k] = (mat[j][k] - f * mat[i][k] % MOD + MOD) % MOD;
        }
    }
    return res;
}

ll countST(int n, const vector<pair<int, int>> &e) {
    if (n <= 1) return 1;
    vector<vector<ll>> L(n, vector<ll>(n, 0));
    vector<int> deg(n, 0);
    for (auto [u, v] : e) {
        u--, v--;
        deg[u]++, deg[v]++;
    }
    for (int i = 0; i < n; i++)
        L[i][i] = deg[i] % MOD;
    for (auto [u, v] : e) {
        u--, v--;
        L[u][v] = (L[u][v] - 1 + MOD) % MOD;
        L[v][u] = (L[v][u] - 1 + MOD) % MOD;
    }
    vector<vector<ll>> sub(n - 1, vector<ll>(n - 1, 0));
    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++)
            sub[i - 1][j - 1] = L[i][j];
    return det_mod(sub, n - 1);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; i++)
        cin >> e[i].first >> e[i].second;
    cout << countST(n, e) << endl;
    return 0;
}
//Generated by Deepseek

How can we do it manually?

It makes sense to set a root to better transition.

$$$dp[i][S]$$$ means the number of trees rooted at $$$i$$$ in the subgraph $$$S$$$ .

Enumerate $$$T\sub S$$$ with the lowest bit in $$$S\oplus 2^{i}$$$as a subtree from $$$i$$$ and make transition.

#include<bits/stdc++.h>
using namespace std;

int n,m;
int e[20][20];
typedef long long ll;
ll f[20][(1<<20)+123];
const int P=998244353;
void madd(ll &x,ll y){x=(x+y)%P;}
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        e[u-1][v-1]=e[v-1][u-1]=1;
    }
    for(int i=0;i<n;++i)f[i][1<<i]=1;
    for(int mask=0;mask<1<<n;++mask)
        for(int i=0;i<n;++i)if(mask>>i&1){
            int smask=mask^(1<<i);
            int lb=smask&(-smask);
            for(int j=smask;j;j=(j-1)&smask){
                if(!(j&lb))continue;
                for(int k=0;k<n;++k)if((j>>k&1)&&e[i][k]){
                    madd(f[i][mask],f[k][j]*f[i][mask^j]);
                }
            }
        }
    printf("%lld\n",f[0][(1<<n)-1]);
    return 0;
}

Observing that a tree can be rooted anywhere , we can only use $$$dp[S]$$$.

#include<bits/stdc++.h>
using namespace std;

int n,m;
int e[20][20];
typedef long long ll;
ll f[(1<<20)+123];
const int P=998244353;
void madd(ll &x,ll y){x=(x+y)%P;}
ll inv[21];
int main(){
    inv[1]=1;for(int i=2;i<=20;++i)inv[i]=P-inv[P%i]*(P/i)%P;
    cin>>n>>m;
    for(int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        e[u-1][v-1]=e[v-1][u-1]=1;
    }
    for(int i=0;i<n;++i)f[1<<i]=1;
    for(int mask=0;mask<1<<n;++mask)
        for(int i=0;i<n;++i)if(mask>>i&1){
            int smask=mask^(1<<i);
            int lb=smask&(-smask);
            for(int j=smask;j;j=(j-1)&smask){
                if(!(j&lb))continue;
                for(int k=0;k<n;++k)if((j>>k&1)&&e[i][k]){
                    madd(f[mask],f[j]*f[mask^j]%P*inv[__builtin_popcount(j)]%P*inv[__builtin_popcount(mask^j)]);
                }
            }
        }
    printf("%lld\n",f[(1<<n)-1]*inv[n]%P);
    return 0;
}

Time complexity: $$$O(n^23^n)$$$.

Space complexity: $$$O(n2^n)$$$ or $$$O(2^n)$$$.

Counting Cactus (QOJ7412)

It becomes more tricky.

$$$f[i][S]$$$ means $$$i$$$ is the root, $$$i$$$ is connect to only one vertex or only in one cycle, the subtree is state $$$S$$$.

$$$g[i][j]$$$ means there is a path from $$$i$$$ to $$$j$$$ ,the subtree is state $$$S$$$.

$$$h[i][j]$$$ means $$$i$$$ is the root, the subtree is state $$$S$$$.

Transition:

1. $$$f\leftarrow h$$$ , a root connected to a tree
2. $$$f\leftarrow g$$$ a cycle is closed.
3. $$$g\leftarrow h$$$ extend the chain
4. $$$h\leftarrow f$$$ add cycles or subtrees to the root.

The final ans is $$$h[x][S]$$$.

Overall time complexity $$$O(n^23^n)$$$.

It's not good to delete the root dimension.

code

Counting SCC (Luogu P11714)

Consider PIE, calculate the number of DAG of scc which size is larger than $$$2$$$.

If there is $$$cnt$$$ scc which has $$$0$$$ in-degree, give it $$$(-1)^{cnt}$$$ coef.

$$$dp[S]$$$ means the subproblem for subgraph $$$S$$$.

Handle some transition and it's done.

code

Set algorithm Part II

The first part has talked about some algorithm and its basic practice. But they are not organized. SPS solves it.

The topic: Set power series.

We have former power series (i.e. generating function) to describe a integer sequence. But if we want to handle the map from a set to a value, we need set power series.

It's not something new, just to wrap all the things above up.

Note

Single uppercase letter means a set.

Single lowercase letter means a power series.

$$$x$$$ is the variable.

The global set $$$U={1,2,\cdots,n}$$$.

$$$2^X={Y|Y\subseteq X}$$$

Definition

Set power series is a function $$$f: 2^U \rightarrow F$$$ where F is a field ($$$C,R,Q$$$).

Addition

$$$f,g$$$ are power series , $$$h=f+g$$$, then $$$h_i=f_i+g_i$$$.

Subtraction

$$$f,g$$$ are power series , $$$h=f-g$$$, then $$$h_i=f_i-g_i$$$.

We note $$$cx^S$$$ as a power series where $$$f_S=c$$$ and other coefficents are zero.

$$$f=\sum_S f_Sx^S$$$

Multiplication

Take a binary operation $$$\ast$$$ that satisfy $$$X\ast Y=Y\ast X,(X\ast Y)\ast Z=X\ast (Y\ast Z),X\ast \varnothing=X$$$.

Define $$$h=f\ast g$$$, $$$h=\sum_S h_S x^S=\sum_X\sum_Yf_Xg_Y x^{X\ast Y}$$$.

We have $$$f\ast g=f\ast g,(f\ast g)\ast h=f\ast (g\ast h),f\ast \varnothing=f$$$.

Convolution

Set Union/Intersection Convolution

The multiplication is identical to the FWT.

Take $$$X\ast Y=X\cup Y$$$ or $$$X\ast Y=X\cap Y$$$.

We use $$$\cup$$$ below.

D&C Multiplication

write $$$f=f^-+x^{{n}}f^+,g=g^-+x^{{n}}g^+$$$.

$f\ast g=(f^-+x^{{n}}f^+)\ast(g^-+x^{{n}}g^+)\ =f^-g^-+x^{{n}}((f^+f^-)\ast(g^-+g^+)-f^-g^-)$.

$$$T(n)=T(n/2)+2^n=O(n2^n)$$$.

FMT

mentioned above ,they are the same.

It's called 'Mobius Transform'.

Set Symmetric Difference Convolution

The multiplication is identical to the FWT, too.

Take $$$X\ast Y=X\oplus Y$$$.

D&C Multiplication

write $$$f=f^-+x^{{n}}f^+,g=g^-+x^{{n}}g^+$$$.

$f\ast g=(f^-+x^{{n}}f^+)\ast(g^-+x^{{n}}g^+)\ =f^-g^-+f^+g^++x^{{n}}(f^-g^++f^+g^-)$.

$$$T(n)=T(n/2)+2^n=O(n2^n)$$$.

FWT

It's called 'Walsh Transform'.

Subset Convolution

$X\ast Y=\begin{cases} X\cup Y & X\cap Y = \varnothing\ \varnothing & X\cap Y \neq \varnothing \end{cases}$

It's the same as Subset Convolution.

Composition

Source:

https://www.luogu.com.cn/problem/P12230 https://www.luogu.com.cn/problem/P12231

They are all special cases of composition.

$$$h$$$ is a polynomial, $$$f$$$ is a set power series.

We use subset operation below.

$$$h(f)=\sum_i h_i f^i$$$

If $$$f_0=0$$$,then $$$i \gt n$$$ is useless.

We need solve FMT to get $$$f^i$$$ ,and do the multiplication and addition. Finally we do IFMT to get the answer.

But it's different when it comes into 'inverse'.

Source: https://www.luogu.com.cn/problem/P12232

$$$f\ast g=x^{\varnothing}$$$, $$$f$$$ is given ,solve for $$$g$$$.

Use the classic 'subset mind': first do FMT, then for each $$$S$$$ treat it as a polynomial and get its inverse.

Three formula:

If $$$f\cdot g = 1$$$,then $$$g_n=-\frac{1}{f_0}\sum_{i=1}^{n}f_ig_{n-i}$$$.

If $$$g=exp(f)$$$,then $$$g_n=\frac{1}{n}\sum_{i=1}^{n}f_iig_{n-i}$$$.

If $$$g=ln(f)$$$,then $$$g_n=f_n-\frac{1}{n}\sum_{i=0}^{n-1}g_iif_{n-i}$$$.

Example

Problem 1

There is a machine. Every time Alice push the button, the machine give $$$S$$$ in probability $$$p_S$$$. Alice initially have no sets and she keeps pushing the button until the union is $$$U$$$.Ask the exceptation of the number of pushing the button.

$$$n\leq 20$$$

$$$ans=[x^U]\sum k(p^k-p^{k-1})$$$.

Do mobius transform and reverse it and we are done.

$$$O(n2^n)$$$.

Problem 2: Topcoder SRM 518 Nim

Alice and Bob are playing Nim. $$$m$$$ piles of stones. Ask the number of stones where each number is a prime $$$\leq l$$$.

$$$m\leq 10^9,l\leq 10^5$$$.

$$$ans=\sum_{S\neq \varnothing}(\sum_T [T \text{ is prime}])^m$$$

Do walsh transform and inverse. $$$O(l(\log m+\log l))$$$.

Problem 3: Connected subgraph counting

Count connected subgraph of a graph of $$$n$$$ vertices and $$$m$$$ edges.

$$$n\leq 20,m\leq n(n-1)/2$$$.

Let $$$g_S$$$ be the number of subgraph of $$$S$$$, $$$f_S$$$ be the number of connected subgraph of $$$S$$$.

$$$1+g_S=\sum \frac{f^k}{k!}=\exp(f)$$$

$$$f=\ln(1+g)$$$

$$$O(n^22^n)$$$.

Template

template<const ll mod>
struct SPS{
int n;
vector<ll> coef;
void resize(int n_,int v=0){
    n=n_;
    coef.resize(1<<n,v);
}
SPS(){}
SPS(int n_){resize(n_,0);}
SPS(vector<ll> a):coef(a){}
ll qpow(ll a,ll b,ll p){
    ll c=1;for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;return c;
}
ll inv(ll x){
    return qpow(x,mod-2,mod);
}
ll& operator [](size_t x){
    return coef[x];
}
template<class Op>
void rec(vector<ll> &a,int n,Op op,int p=0){
    if(n<=6){
        for(int o=1;o<1<<n;o<<=1)
            for(int i=0;i<1<<n;i+=o<<1)
                for(int j=0;j<o;++j)
                    op(coef[p+i+j],coef[p+i+j+o]);
    }else{
        rec(a,n-1,op,p);
        rec(a,n-1,op,p+(1<<n-1));
        for(int i=0;i<1<<n-1;++i)op(a[p+i],a[p+i+(1<<n-1)]);
    }
}
void OR(){
    rec(coef,n,[&](ll &x,ll &y){y+=x;if(y>=mod)y-=mod;});
}
void IOR(){
    rec(coef,n,[&](ll &x,ll &y){y+=mod-x;if(y>=mod)y-=mod;});
}
void AND(){
    rec(coef,n,[&](ll &x,ll &y){x+=y;if(x>=mod)x-=mod;});
}
void IAND(){
    rec(coef,n,[&](ll &x,ll &y){x+=mod-y;if(x>=mod)x-=mod;});
}
void XOR(){
    rec(coef,n,[&](ll &x,ll &y){
        ll tx=x,ty=y;x=tx+ty,y=tx+mod-ty;if(x>=mod)x-=mod;if(y>=mod)y-=mod;
    });
}
void IXOR(){
    rec(coef,n,[&](ll &x,ll &y){
        ll tx=x,ty=y;x=tx+ty,y=tx+mod-ty;if(x>=mod)x-=mod;if(y>=mod)y-=mod;
    });
    ll tmp=1;for(int i=0;i<n;++i)tmp=tmp*(mod+1>>1)%mod;
    for(int i=0;i<1<<n;++i)coef[i]=coef[i]*tmp%mod;
}
SPS operator * (const SPS B){
    SPS res(n);
    for(int i=0;i<1<<n;++i)res.coef[i]=coef[i]*B.coef[i]%mod;
    return res;
}
SPS operator & (SPS B){
    SPS A(n);
    for(int i=0;i<1<<n;++i)A.coef[i]=coef[i];
    A.AND(),B.AND();
    A=A*B;
    A.IAND();
    return A;
}
SPS operator | (SPS B){
    SPS A(n);
    for(int i=0;i<1<<n;++i)A.coef[i]=coef[i];
    A.OR(),B.OR();
    A=A*B;
    A.IOR();
    return A;
}
SPS operator ^ (SPS B){
    SPS A(n);
    for(int i=0;i<1<<n;++i)A.coef[i]=coef[i];
    A.XOR(),B.XOR();
    A=A*B;
    A.IXOR();
    return A;
}
//subset convolution
SPS operator || (SPS B){
    vector<SPS> f(n+1,SPS(n)),g(n+1,SPS(n)),h(n+1,SPS(n));
    for(int i=0;i<1<<n;++i){
        f[__builtin_popcount(i)].coef[i]=coef[i];
        g[__builtin_popcount(i)].coef[i]=B.coef[i];
    }
    for(int i=0;i<=n;++i)f[i].OR(),g[i].OR();
    for(int i=0;i<=n;++i)
        for(int j=0;j<=i;++j)
            for(int k=0;k<1<<n;++k)
                h[i].coef[k]=(h[i].coef[k]+f[j].coef[k]*g[i-j].coef[k])%mod;
    for(int i=0;i<=n;++i)h[i].IOR();
    SPS res(n);
    for(int i=0;i<1<<n;++i)res.coef[i]=h[__builtin_popcount(i)].coef[i];
    return res;
}
SPS exp(){
    vector<ll> inv(n+1);
    inv[1]=1;for(int i=2;i<=n;++i)inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    SPS res(n);
    vector<SPS> f(n+1,SPS(n)),g(n+1,SPS(n));
    for(int i=0;i<1<<n;++i)f[__builtin_popcount(i)][i]=coef[i];
    for(int i=0;i<=n;++i)f[i].OR();
    for(int i=0;i<1<<n;++i){
        g[0][i]=1;
        for(int j=1;j<=n;++j){
            for(int k=1;k<=j;++k){
                g[j][i]=(g[j][i]+f[k][i]*k%mod*g[j-k][i])%mod;
            }
            g[j][i]=g[j][i]*inv[j]%mod;
        }
    }
    for(int i=0;i<=n;++i)g[i].IOR();
    for(int i=0;i<1<<n;++i)res.coef[i]=g[__builtin_popcount(i)][i];
    return res;
}
SPS ln(){
    vector<ll> inv(n+1);
    inv[1]=1;for(int i=2;i<=n;++i)inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    SPS res(n);
    vector<SPS> f(n+1,SPS(n)),g(n+1,SPS(n));
    for(int i=0;i<1<<n;++i)f[__builtin_popcount(i)][i]=coef[i];
    for(int i=0;i<=n;++i)f[i].OR();
    for(int i=0;i<1<<n;++i){
        g[0][i]=0;
        for(int j=1;j<=n;++j){
            for(int k=1;k<=j-1;++k){
                g[j][i]=(g[j][i]+g[k][i]*k%mod*f[j-k][i])%mod;
            }
            g[j][i]=(f[j][i]+mod-g[j][i]*inv[j]%mod)%mod;
        }
    }
    for(int i=0;i<=n;++i)g[i].IOR();
    for(int i=0;i<1<<n;++i)res.coef[i]=g[__builtin_popcount(i)][i];
    return res;
}
SPS Inv(){
    SPS res(n);
    vector<SPS> f(n+1,SPS(n)),g(n+1,SPS(n));
    for(int i=0;i<1<<n;++i)f[__builtin_popcount(i)][i]=coef[i];
    for(int i=0;i<=n;++i)f[i].OR();
    g[0][0]=inv(coef[0]);
    for(int i=0;i<1<<n;++i){
        g[0][i]=g[0][0];
        for(int j=1;j<=n;++j){
            g[j][i]=0;
            for(int k=1;k<=j;++k){
                g[j][i]=(g[j][i]+mod-f[k][i]*g[j-k][i]%mod)%mod;
            }
            g[j][i]=g[j][i]*g[0][0]%mod;
        }
    }
    for(int i=0;i<=n;++i)g[i].IOR();
    for(int i=0;i<1<<n;++i)res.coef[i]=g[__builtin_popcount(i)][i];
    return res;
}
};
typedef SPS<998244353> SPS998;

References

https://mirror.codeforces.com/blog/entry/45223

https://mirror.codeforces.com/blog/entry/72488

https://www.luogu.com.cn/problem/P4717

https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf

https://www.luogu.com.cn/article/gs78uwd7

https://www.cnblogs.com/Mackerel-Pike/p/16395436.html

https://yhx-12243.github.io/OI-transit/records/loj6719%3Bgym102331C.html

APIO 2025 Class: 【陈昕阳】集合幂级数在子图计数问题上的应用.pdf

吕凯风(vfleaking)，集合幂级数的各种应用及其快速算法，中国国家集训队论文2015.

https://www.cnblogs.com/alex-wei/p/set_power_series.html

https://www.cnblogs.com/tzcwk/p/dxs-sqr.html

Others

My Blog

good code

I finally reached Grandmaster. And now I am to share some of my experience.

This blog is following NemanjaSo2005's blog.

Some tips related to Competitive Programming

Firstly, I will note that just because some practice method worked for me, it doesn't mean it will work for you, or in general. I will try to give some points that are either important or not that well discussed.

Competitive Programming is fun! Enjoy the problems themselves and don't always focus on ratings. CP is a matter of capability, not of reputation.

Do the proper problems. Neither too hard nor too simple. You can learn new ideas or tricks from these problem, and btw enjoy the beauty of problem solving.

Join an academic community. Ask the problems you don't understand or help others. Excellent people help each other to improve while the bad ones prevent each other from improving. Please choose to be the former.

Be focused when solving problems. You may be wrong , but it's ok to fix the wrong ideas or bugs. That's useful for improving.

Codeforces is excellent. There are many interesting problems and contests of great quality. You can use it for your training.

Conclusion

Reach GM doesn't require much talent. Instead, it requires the enthusiasm and persistent practice.

There is still a long way for me to go. And I'm not satisfied with myself, like Faust.

That's the word I send you. Thank you for reading! I hope you found my article interesting and maybe even useful. If you have any questions, thoughts, or experiences to share—or even just want to congratulate me—please feel free to drop a comment.

Case 1

$$$[1,2,3,\dots ,x][x+1,x+2,\dots ,y,1,2,3,\dots,x-1]$$$

$$$[1,2,3,\dots ,x,x+1,x+2,\dots ,y][1,2,3,\dots,x-1]$$$

take either

take the example in the officail tutorial:

$$$[1,2,3,1,2,1]$$$

$$$[1,2,3]+[1,2]+[1]$$$

$$$[1,2]+[3,1,2]+[1]$$$

It inspire me to ban the $$$[1,2,\dots x][x+1\dots]$$$ situation.

Case 2

$$$[k,k+1,\dots,x,1,2,3,\dots,k-1][k,k+1,\dots]$$$

There should be no misunderstanding.

Solution

The $$$O(n^4)$$$ brute force.

I didn't come up with it during the contest,though.

https://mirror.codeforces.com/contest/2124/submission/327909733

I wrote another $$$O(n^3)$$$ dp.

https://mirror.codeforces.com/contest/2124/submission/327819126

But I can't optimize it.

So what is tutorial say is right.

https://mirror.codeforces.com/contest/2124/submission/327928111

https://mirror.codeforces.com/contest/2124/submission/327928858

I enjoyed the problem, indeed.

Key observation

First,the $$$(i,j)$$$ must satisfy $$$a_i$$$ is the prefix minimum and the $$$a_j$$$ is the suffix maximum.Otherwise,the modification has no use or the $$$j$$$ can be adjusted to the next suffix maximum to its right.

Second,if the $$$x$$$ which the $$$a_i$$$ is changed to is bigger than the previous prefix minimum,it's all the same no matter the $$$x$$$ ranges.It's because the minimum has been taken by the last one.

$$$a_i\in [0,n]$$$,so the first property is the number of key pairs $$$(i,j)$$$ is $$$O(n)$$$.

So get the $$$O(n^2)$$$ brute force solution: https://mirror.codeforces.com/contest/2124/submission/327896282.

Solution

All we need to do is to solve a pair $$$(i,j)$$$ fast enough.

Denote $$$a_i:=x$$$,and divide the array into some parts.

$$$[1,i-1]$$$: precalculated.

Oh,the prefix minimum need another case work.

Find the minimum $$$k$$$,s.t. $$$i \lt k \lt j,x\leq a_k$$$.

$$$[i,k)$$$: prefix minimum are all x

But we need to handle whether $$$k \gt j$$$ or $$$j\leq k$$$,that's another case work.

to calculate $$$[k,j)$$$ that's not easy.So change the angle.

1.$$$[k,n]$$$: from a $$$a_k$$$ to get minimums, calculated in some way

2.$$$[j,n]$$$: from a value to get minimums,calculated in some other way.

3.combine them: subtract $$$[j,n]$$$ from $$$[k,n]$$$.

The techique details are in the code.(https://mirror.codeforces.com/contest/2124/submission/327901887)

Fail to become GM.

Hints are omitted.

$$$O(nmh^2)$$$ is too simple,just use dynamic programming. $$$dp(i,j,k)$$$ means the probability to reach the goal in the first $$$i$$$ turns,$$$\min(h_i)=j$$$,$$$\sum (h_i-j)=k$$$,and make simple transitions.

As we see,the $$$k$$$ cound be big. And if $$$k\leq n$$$,we get $$$O(nmh)$$$,which is fast enough.

And the $$$k$$$ can only be big in the beginning,and we can enumerate the time when $$$h_i$$$ are equal.

And set another dp,which is used frequently. $$$g(i,j)$$$ means the probability to have $$$j$$$ times when the Sword doesn't shine.It can be done in $$$O(nmh)$$$.

So the work are done.

https://mirror.codeforces.com/contest/2115/submission/322464169

Problem

I want to explain the brute force for F.

In the tutorial of F,it said "however, deriving them manually is quite complicated, as there are many situations."

But I consider this problem as a perfect chance to practice case work:

Do the first three letters by case work.

First, whether $$$s_1$$$ is 'a' or 'b' doesn't matter.

We can just record the longest 'ababab' prefix and the value of $$$s_{mid}$$$ ,and do case work. Do two letters $$$x,y$$$ once.

1. p=1; p is odd number ;p is even number
2. $$$s_1=s_{mid}$$$,$$$s_1\neq s_{mid}$$$
3. $$$p=mid-1$$$,$$$p\neq mid-1$$$
4. $$$x=a$$$,$$$x=b$$$
5. $$$y=a$$$,$$$y=b$$$

In the $$$p=1$$$,we don't care $$$p=mid-1$$$.

As in the code,there is $$$2\times 2 \times 2+2\times 2\times 2\times 2\times 2=40$$$ cases,handle them one by one and get c++ code in 15kb.

I highly recommend you reading code, and I'm glad you to find my mistakes.