https://atcoder.jp/contests/abc284/tasks

Ex - Count Unlabeled Graphs

按照下面步骤生成图

选 简单,无向,n个无标签点 的图

给每个点 写 <= k的数, (1~k每个都至少出现一次

找方案数 mod p(质数 1e8~1e9)

范围

k <= n <= 30

我的思路

无标签的图 和 有标签的图之间 如何进行 重复统计的转化 ???

考虑按照连通块来划分

连通块大小 和 同联通块大小的选择个数

f[s] = 每个连通块大小为s 的 染色方案数 的生成方程 = a[s] x^s + a[2s] x^2s + a[3s] x^3s …

为了统计 g[s] = 加上外部贡献的选择倍数 = a[s]/s! x^s + a[2s]/(2s)! x^2s + a[3s]/(3s)! x^3s …

这样 ans = [x^n] n! g[1] * g[2] * g[3] * ... * g[n]

那么问题来了, 如何计算f[i]

h[i] = 1个大小为i的联通块的染色方案数

a[i] = h[i], 直接染色

a[2i] = binom(2i,i-1) h[i] * h[i], 确定1在地一个块

a[3i] = binom(3i,i-1) * binom(2i,i-1) h[i]^3, 确定1在地一个块, 不在第一个块中最小的在第二个块

那么如何计算h[i]

count[形状] = 一个形状的染色方案数

h[i] = sum count[形状i]

形状不同, 染色后一定不同, 但是相同形状 染色后可能相同,

如何判断两个形状不同, 如何枚举形状, 每个形状如何计算染色方案??????????????????????????

并不会

能想到一些必要条件, 但没啥充分条件, 比如 点i连的点和相同,且度相同

第一类stirling数

$s(n,k) = \begin{bmatrix} n \\ m \\ \end{bmatrix}$ 表示n个不同元素, 划分成m个非空段(每个非空段 满足循环平移等价) 的方案数

(n个两两不同元素,划分为k个互不区分的非空轮换的方案数, 也就是 如果划分出 [1,2,3] 那么 和[2,3,1]等价和[3,1,2]等价, 但是和[3,2,1]等价

$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$ 一样的也是考虑 最后一个单独放还是插入到前面某个序列里

边界$\begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]$

生成函数

构造生成函数 $F_n(x)=\sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i$

根据递推公式$F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x)$

有 $F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=\dfrac{(x+n-1)!}{(x-1)!}$

https://atcoder.jp/contests/abc283/tasks

Ex - Popcount Sum

$0 \le R,M+R,2M+R,3M+R,\cdots < N$

$R \in [0,M]$

问上述[0,N]中的这些数, 的二进制下的1的个数的总数

范围

t 组数据 1e5

n 1e9

4s

1024mb

我的思路

分类一下, 感觉就需要一点数学, 然后t 1e5, 基本也就是说, 要么O 1,要么O sqrt 左右

如果m==1, 那么就是1…n 的所有数的二进制1的个数和, [1…2^t,2^t+1…n] 这样划分就是 sqrt

如果m==2^k, 那么这些数的 低k位都一样, k位以上, 和上面是一样的

如果m 不是上面的情况,进位的时刻, 似乎并不好拿捏

2, 3+2,6+2,9+2

1
2
3
4
5

  10
 101
1000
1011
1110

能说的是 低两位4次的循环节, 比3还大, 高位也没啥规律

对称相加

R, M+R, 2M+R, … , kM+R

kM+R, (k-1)M+R,…, R

对称的和始终是 (k+1)M+R, 有办法 只算 一半 与 (k+1)M+R 的bit的联系, 这样一半

https://atcoder.jp/contests/abc282/tasks

G - Similar Permutation

两个长n排列A,B

相似度为 相邻同增次数 + 相邻同减次数, (A[i+1]-A[i])(B[i+1]-B[i]) > 0

问 相似度为k的有序对 (A,B) 有多少个, mod p

范围

n 100

p [1e8~1e9]

4s

1024mb

我的思路

看这 n, 感觉有可能就要到4次方, 想一维度的排列,每次 从N-1到n, 就是考虑n的插入位置

但是两个序列的话

a0 a1 a2…..

b0 a1 b2…..

插入一个值, 会让后面的值平移, 增减关系会错位

变一变, f(k) = 至少k个位置增减关系一致, 那么ans = f(k) - f(k+1)

但这样也不知道怎么统计

因为

1 2 3, 假设定了第一个位置是增

那么

1-2 3

2-3 1

1-3 2

第二个位置并不是增 减 数量相等的

如果a和b在从n-1变到n时, 插入位置相同, 那么这个位置的左右增减都是相等的, 但是插入前可能相等可能不等,增量是1, 但不同怎么处理

再就是不要插入n, 而是末尾插入一个

f(len a, last a, len b, last b), 似乎可以搞?, 注意到两个len是相等的

插入 x, 等于 原来 [1…x-1] 不变, [x..n-1] 平移1变成[x+1,n]

f(len, last a, last b,同增减k)

f[n][a1][b1][k1] += f[n-1][a0][b0][k0] , k1 = k0+ bool( (a1 <= a0)^(b1 <= b0) )

这样状态是 O(n^4) 转移是 O(n^2) 一共O(n^6) 过不了

可能需要二维前缀和搞一搞?, 实际就是一条纵线 a1 = a0 和 b1 = b0 划分的

https://codeforces.com/contest/1767

E. Algebra Flash

长n的 染色格子

每次只能走 i+1 或 i+2

颜色要激活才能走(一次激活所有同色), 求最小代价, 让1到n是通的

范围

n 3e5

颜色种类 m [1,40]

激活代价 [1,1e7]

2s

256mb

我的思路

只感受到 i如果不激活, 那么i-1 和i+1必定要激活, 这样有一定的 约束性, 不知道能不能2-sat, 但感觉2-sat 出来的强联通块的意义 也不明

m 40 的话, 就没法直接bitmask