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

Ex - Diff Adjacent

正整数序列，和为N, 没有相邻元素相等

求所有满足的序列的长度 的和 mod 998244353

n 2e5

我的思路

~~2e5 打表啊 ~~

f(m,n) = 长度为m,和=n,满足没有相邻的方案数

ans(n) = sum m f(m,n)

g(m,n,v) = 长度为m, 和=n, 最后一个数为v, 满足没有相邻相同的方案数

f(m,n) = sum g(m,n,1…)

g(1,n,n) = 1

g(1,n,!=n)=0

g(m,n,v) = sum g(m-1,n-v, != v)

注意到转移和m无关, 所以相当于初始矩阵经过 m 次矩阵乘法以后得到的

1
2
3
4
5
6
7
8

初始(1行n^2列)
		转换^m 
                     m (对应第n行的是m,非n行的是0)
                     0
                     0
                     m
                     0
                     0

然而直接的话，矩阵大小是((n^2)^2) 因为转移每次 都并不是行列对齐

n^2都不行，更别说n^4还要乘法了

而注意到最左和最右的两个行/列矩阵，非零元不超过n

能否靠这个简化

另一些思路，有容斥相邻位置，但是2^{位置}次方吗?

不要等于，换成 f(=n) = f(<=n) - f(<= n-1)

中间想拆成生成函数表示，但是没有拆成功

长度之和 就是每个位置贡献1, 能不能拆

虽然11不能相邻，但是12间隔还是长度能达到 2n/3

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

Ex - Unite

N行,M列, 黑/白, 至少一个黑

最小数量 把白色染成黑色, 让所有黑色是一个连通块(4临)

N 100

M 7

2s

1024mb

我的思路

这M这么小，一股插头dp/横断截面dp的味道

dp[i][横截面状态][已有不连接连通块个数:0/1] = 最小操作数

然后横截面状态, 需要保证横截面以上的内容合法， 然后状态就是最小表示法

但是这样转移太大了, 所以还是插头,

不压缩的情况 也只有$8^7=2097152$ 个状态, 而压缩后应该会很小，因为首先有从小到大性就已经$2\cdot 3\cdot 4 \cdot 5\cdot 6 \cdot 7\cdot 8=40320$, 而且相邻会属于同样的块，所以就更小的了,

O(nm state) 应该就没有了

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

E - Kth Number

给长n数组a, $a[i]\in[0,M]$

对于每个$a[i]=0$,等概率修改$a[i]\in[1,M]$

所有修改完后, sort a

问 exp(A[k]) mod 998244353

N 2000

M 2000

4s

1024mb

我的思路

$ans = \sum_{v=1\to m} v\cdot p(v)$

其中$p(v)$表示 $v$是排序后第$k$小的概率

有$z$个0,其中$z_1$个改为$< v$,$z_2$个改为$=v$,剩下$z-z_1-z_2$个改为$> v$

$p(v) \cdot z^m = \sum_{z_1,z_2} \binom{z}{z_1}\binom{z-z_1}{z_2} (v-1)^{z_1}1^{z_2}(m-v)^{z-z_1-z_2}$, 其中 $z_1 + count(<v) < k$且$z_1+z_2+count(\le v) \ge k$

看上去是$O(m n^2)$的

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

Ex - K-Coloring

n点无向图

m 边

点赋值 [1,k] 相邻点值不同的方案数 mod 998244353

n 30

m [0,30]

k 1e9

8s

1024mb

我的思路

m 30, n 30, 想到的30相关的就是2^{30/2} 的meet-in-the-middle, 但没什么具体的想法

方案统计

对于一个具体方案，考虑按照 点的index顺序从小到大交换

例如 1染色x , u染色1, 那么把所有x和1染色的交换成1和x, 那么得到的依然合法

这样 index顺序虫小到大 染色c个的方案数 f(c)

ans = sum f(c) A(Permutation)(k,c)

1
2
3
4

dfs(u, cntcolor){
  color[u] = [1..cntcolor+1] and !=color[v in connect[u]]
  dfs(u+1, max(cntcolor,color[u]);
}

感觉复杂度会爆炸?吧?

不同难搞，要不然就是反过来容斥 相同

属性i = 边i连的两点颜色相同

ans = sum (-1)^count(属性…) g(属性…)

这个问题就是 $2^{30}$太大, 需要拆分

右侧的g()=k^{未连通块个数}

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

Ex - Optimal Path Decomposition

n 点树

找最小整数k，使得有方案满足染色

• 每个相同具体颜色，连通且简单路径
• 树里所有简单路径 最多K种颜色

n 2e5

2s

1024mb

我的思路

这第一眼上去像是重轻儿子

第二眼上去像是树上DP

虽然具体的染色的情况 不和 K直接相关

但是 当两个不同颜色链的端点相邻，那么把它们染成同样的颜色，得到的K不会比之前的更差

dp[u][u是否可以向上连] = {u的子树中最多颜色的路径，从u向下最多颜色的路径}

显然 子树cnt >= u向下

看起来是一个 O(n^2) 的状态

而从u 向下最多颜色的路径 <= u到最深叶子的

如果有办法 把这个缩减这个向下颜色的路径的维度

然而根据轻重儿子的链式方法，根到任何叶子最多经过O(log(n)) 条不同的重链

所以如果直接 轻重链方案，那么方案 <= 2log n

所以 dp[u][u是否可以向上连][u向下最多的颜色的路径 <= 2log n] = u子树中最多颜色的路径

似乎就能做了?