https://atcoder.jp/contests/abc296/tasks
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
给长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
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 | dfs(u, cntcolor){ |
感觉复杂度会爆炸?吧?
不同难搞，要不然就是反过来容斥 相同
属性i = 边i连的两点颜色相同
ans = sum (-1)^count(属性…) g(属性…)
这个问题就是 $2^{30}$太大, 需要拆分
右侧的g()=k^{未连通块个数}
https://atcoder.jp/contests/abc293/tasks
n 点树
找最小整数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子树中最多颜色的路径
似乎就能做了?
https://codeforces.com/contest/1830
长度n数组 a,b
计算多少对 i < j 满足 ai * aj = bi + bj
t 1e4
sum n 2e5
ai,bi [1,n]
4s
512mb
加的范围保证了 <= 2n
所以 对于同样的a 直接整合
然后 2n (1+1/2+1/3+…), 所以真的枚举的 乘法对是满足范围的
然后对于具体的 v0=ai,v1=aj
那么对应 bi/bj 是两个集合, 或者map[b]=count
每次选小的 去大的里面搜, 这复杂度不知道多少, 过了pretest,被hack tle了