https://atcoder.jp/contests/abc323

G - Inversion of Tree

给定一个 1~n的排列p

1
2

for k = 0..n-1:
	求 对于n点树，满足((边端点 点的idx大小 和 p[点idx]大小 是相反的) 的边的个数 == k) 的树的个数 mod 998244353

n 500

4s

1024mb

我的思路

因为这里要的相反不是 父子和p相反，而是index和p[index]相反， 所以如果要选根，选1就行

然后问题是 如果在树上做dp,不光要记录满足树和子树的点树，还需要记录哪些点已经用了，感觉这状态有点多

注意到$n\le 500$是有点小的，可能有$n^2,n^3$的考虑的方向，但实际上这里还有一个k,所以可能是$nk,n^2k,nk^2$一类的

但直接的思路还是没有

然后就是插入新点的想法

如果有一个n-1点的方案，那么对于 p[1]...p[n-1]需要把所有大于$p[n]$的p进行减1,这样就是规模减1的子问题，

但是问题是，这样的话，并没有看出n-1到n的转移

首先钦定了根是1，所以(n,p(n))不是根，如果它是叶子，那么 一个n-1树上原来叶子p[叶] >= p[n] 都会贡献到对应的k+1, 而原来p[叶] < p[n] 会贡献到k

那还不用说非叶子的，光是这里，就需要记录叶子的p和更大的p之间的关系的个数，那么更小的层数时要记的关联太多了

似乎连一个暴力的计数法都没有

然后 如果 == k难求，可以考虑求 $\le k$ 然后做相邻相减

https://atcoder.jp/contests/abc321

G - Electric Circuit

3种点

n个 part点

m个红点

m个蓝点

给定每个 颜色点连到一个part点

然后红点和蓝点的直接连线 需要单射且满射，那么有m!种

对于所有连法 求 Exp(连接后的连通块个数)

n 17

m 1e5

3s

1024mb

我的思路

n 很小想用bitmask

首先根据 n来整理，变成 有n个点，每个点有ri个红色，bi个蓝色

然后要把所有红蓝相连，求连通块的个数期望

1
2
3
4
5
6
7
8
9

f[mask] = mask内连成一个连通块 且无剩余蓝红的方案数
g[mask] = mask内无剩余蓝红的方案数
ans[s] = sum s的所有方案的连通块个数
ans[s] = for mask, mask 包含最小点
		f[mask] * ans[s-mask] 两边互不影响计算右边贡献
		+ f[mask] * g[mask] 计算左边贡献

g[mask] = sum红! , 满足sum红==sum蓝
f[mask] = g[mask] - sum f[submask]*g[mask-submask], submask包含mask中最小的

似乎就AC了

https://atcoder.jp/contests/abc320

G - Slot Strategy 2 (Hard)

n个只包含’0’-‘9’的长度m的字符串在旋转

对于一个时刻 最多停止一个字符串旋转，字符串展示字符s[i][t%m]

问 最少多少时刻 让所有字符串停止，且展示的字符一样， 或无方案

n 100

m 1e5

2s

1024mb

我的思路

注意到 只包含数字，而数字只有10个，所以可以指定数字比较方案优劣

那么对于给定数字以后，每个字符串将变成一个0/1 bool串，其中 true表示 对应位置是要指定的结果数字

有一点想搞可反悔的dp

首先如果每个字符串都有指定数字才有可能，这样就是依次来都是一个方案，只是可能不是最短时间

但实际上可以变成二分图

首先 左侧是 字符串id, 右侧是可以逐步增加点的的时刻, 只要有对应位置就建立一条边

这样如果有 ans = |n| 就是答案， 这样最坏的情况是 n*m个右侧点，也就是所有字符串都集中在一个循环时刻上了

这里可以优化一下 右侧增点的过程，把与左侧无连接的点直接预处理掉，变成 [offset,vector<int>left]

那么每次增加 至少增加一次连边，

想用hall定理，也就是什么时刻 左侧的任意点的右向连接数一定大于左侧点数， 这个量级的上限

因为每循环一轮，所有左侧点连的点个数 至少增1,所以 总边数不会超过n^2

似乎就没了， 然而TLE了2个点

https://atcoder.jp/contests/abc319

F - Fighter Takahashi

根1,n点 树

非根节点, 2种类型， (si,gi) 或 ((gi) 最多10个)

1
2
3
4
5
6
7
8

初始 s=1 在根
   如果 首次 到点 (ei,si):
       if s < si:
           终止
       else:
          s += gi
   如果 首次 到点 (ei,gi):
          s *= gi

问 能不能经过所有 (si,gi)

n 500

si [1,1e9]

gi [1,1e9]

第二种类型最多10个

2s

1024mb

这不是手机广告里看到的游戏吗 哈哈哈哈哈哈哈

我的思路

这10个，和 n <= 500

我的感觉就是 bitmask乱搞一下？

dp[bitmask] = 恰好把bitmask的 (gi)类型点走完 的最大s

因为所有操作都是增长s的

所以一旦s > max(si)以后，就都可达了

那么对于 (s+w)*v和(s*v+w) 肯定先加会更好

所以步骤是

1. 当前bitmask,尽量+
2. 完成加以后走一次 (gi)

尽量+因为和当前s有关系，而办法就是所有可达点找最小的si,因为任何其它顺序的方案，对其 (可达性,si)排序，肯定有等价的 先最小可达si的方案，贪心就完了

那么问题来了，bitmask以后的方案似乎对应的点并不一致

因为在 尽量+的时候走过非bitmask的点

那么还剩下树的性质没有用，如何使用呢？

另一个想法就是 别bitmask了，直接 贪心+10! 吧，反正上面总结的是 每次尽量+，之后才走乘法

所以是

1. state => 贪心所有可用的+点全部用完
2. 那么现在剩余有若干个乘法点，这里直接分叉 暴力： $500\cdot 10!=1814400000$个方案

再一个就是两者结合，当达到bitmask且完成尽量+以后，记录s和对应的树状态

因为bitmask完成 和 + 以后，那么树上的不考虑s的 连通点是一样的，在一样的开放连通点情况下

“感觉上是” s越大越优，因为完成了 尽量+

所以 当前两个方案 如果不同 它们s如果相同，那么可达区域 <= s都可达 也就相同

如果它们 s不同，s更大的 可达区域也越大

所以就是 bfs + 贪心 + 优先队列 + bitmask?

直接过了

https://atcoder.jp/contests/abc318

G - Typical Path Problem

n点,m边无向图

给定3点a,b,c，问是否存在从a到c经过b的简单路径

n 2e5

m 2e5

2s

1024mb

我的思路

找可以切割图的关键路径

按照关键路径切割图，合并

新图是树且树上所有边是原图的关键路径，在新树上找a到c简单路径

那么 就变成a-端点[关键路径]端点-...-端点[关键路径]端点-c

那么就是判断b 是否为其中的端点

或者相邻端点不同时，b属于对应连通块

然而ACx77,WAx16