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

G - Divide a Sequence

长n数组A

2^{n-1}种方式切割成非空顺序数字

f(切割) = $\prod$每个子数组的 (max-min)

求 $\sum$ f(所有切割)

mod 998244353

范围

2s 1024mb

我的思路

dp搞一搞

考虑最后一个数组长度
dp[i] = dp[i-len] * ((max-min)([i-len+1..i]))

但这样就O(n) 状态, n^2转移了

然后,算的时候,max和min可以拆开, 但是如果 两两不等的话, 即使用了 区间sum dp * max, 也可能max需要一个一个枚举,也是n^2

问题变成说

dp[i] = sum max(a[i-len+1..i]) * dp[i-len] - min(a[i-len+1..i]) * dp[i-len]

考虑相邻转移

i-1: sum max(a[j+1..i-1]) * dp[j]

1. a[i]是[j+1..i]的最大值, 那么找最小的j, 这之家你的贡献 = a[i] * sum dp[j..i-1]
2. a[i]不是[j+1..i]的最大值, 那么这贡献 = sum max(a[j+1..i])*dp[j] = sum max(a[j+1..i-1])*dp[j]

因此相邻的dp虽然没有直接关系, 但是可以利用上次的计算

dp[i] = a[i] * sum(dp[j..i-1]) + sum f(0..j)

min同理

似乎就没了

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

G - Strongest Takahashi

n x n 格子

# 不可通行,. 可通行

选一个[1,N]中的数字D, 选择DxD的区域,花费代价D移除所有#

问移除所有#的最小代价

范围

N 50

2s

1024mb

我的思路

显然选一个最大的就是n

什么时候不是n?

(n-1)x(n-1) 覆盖不完

那有没有可能 (n-1)x(n-1) 不能覆盖完,但是可以拆成更小的

1
2
3

#..
...
..#

另一个想法是从小向大合并

1
2

#.
.#

有相邻,则合并成更大的

1
2

XX
XX

但是方向选择上?, 不一定能确定

1
2
3
4
5
6

.....#
......
###...
......
...#..
...#..

考虑dp

dp[i][j][d] 表示,覆盖掉i,j 开始d x d的范围的最小代价

但感觉不会转移

看上去,不会出现多个小块 让不能同时行分割和列分割, 但不会证明?

1
2
3
4
5
6
7
8
9

 x
 x  xxxxxxx
 x
 x      x
 x      x
        x
xxxxxx  x
        x
        x

如果是这种, 那么直接用大块覆盖更好

因此 区域覆盖= min(纵切割和,横切割和,一个正方形全覆盖的和)

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

G - Modulo Shortest Path

N 点 有向图

任意两点$i,j$, 有边$weight_{i\to j} = A_i+B_i \bmod M$

输出$i$到$N$的最短路

范围

n 2e5

m 1e9

3s

1024 mb

我的思路

说是有向, 实际上是两两联通,区别只是权重 $i \to j$ 是$A_i+B_j$, 而 $j\to i$是$A_j+ B_i$

n很大 不能可能枚举边,

但似乎, 1->a->b->c

如果忽略到mod, 边代价为= A1+Ba+Aa+Bb+Ab+Bc

也就是 A1+Bc+ (A+B)(a+b)

也就是(1->N) = 首项 + 末项 + 中间的AB

ans - (A1+Bn + (A+B)(…)) = 0 (mod M)

而注意到直接走, 就是$(A1+Bn)%M$, 所以已经存在一个[0,M)的答案, 所以最优的一定也是[0,M)内

如果 Bi 和前面的不超过M, Ai和后面的和不超过M

那么显然i只会让总代价增加(Ai+Bi), 因为可以去掉它,把前后拼起来

这里可以看出需要

(A0 + Bi)mod m + (Ai + B1) mod m < (A0 + B1) mod m < m

所以前面一定也是 [0,m)

(A0 + B1 + Ai + Bi) % m < (A0 + B1) % m < m

因此 (A0+B1+Ai+Bi) >=m, 而且这个减m 要在 上面求和的两个mod 中实现

((A0 + B1)%m + Ai + Bi) % m < (A0 + B1) % m < m

对于A0+B1 < m,

如果 Ai > A0 则Ai+B1 >= m, 如果Ai < A0, 则Bi > B1

如果 Bi > B1 则A0+Bi >= m, 如果Bi > B1, 则Ai > A0

对于2m > A0+B1 >= m

则 m - B1 <= Ai < A0, m - A0 <= Bi < B0

可以看成, 每次路径上插入一个点, 都是让总代价单调下降 (m - (ai+bi)%m)

初始$1 \to N$, 然后每次找一个去插入

但是点插入的顺序, 如何做?

按下降排序? , 前i个最大下降结果, 可是还会收到可插入的影响? 如何维护状态

另外就是这性质 有没有办法优化dij

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

G - Balls in Boxes

n个盒子, 初始第i个盒子有ai个球

k次操作

每次 等概率选一个盒子, 增加1个球

分数 = 最终每个盒子的球的个数之乘积

求分数期望 mod 998244353

范围

n 1000

k 1e9

ai [0, 1e9]

2s

1024 mb

我的思路

感觉上可以 做n和n-1的关系, 然后直接算频次, 最后除总次数 转成概率

F(n,k) = 前n个所有方案的乘积和, Ans = F(n,k) / n^k

对于最后一个盒子, 选择了j次, 对应的方案乘积和为 C(k,j) * F(n-1,k-j) * (a[n]+j)

F(n,k) = sum (a[n]+j) * F(n-1,k-j) * C(k,j), j=0..k

这里n虽然小, 但是k很大, 上面这个显然TLE, 如果能搞到n^2 左右的就好了

C(k,j) 的部分拆出来 分配给F的分母可以简化,但是依然没有去掉k的维度

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

G - GCD Permutation

给一个1~N的排列p

问有多少个有序对 (i,j), (i<=j), 满足 gcd(i,j) != 1, gcd(p[i],p[j]) != 1

范围

n 2e5

5s

1024mb

我的思路

有点想暴力 然后证明复杂度?

对于 (i,Pi), 取两个中较小的一个, 找所有包含它下标的, 用较大的去验证gcd

最多有6个不同质数因子, 最坏情况 1/2+1/3+1/5+1/7+1/11+1/13 = 1.3左右

所以最坏情况是 找n个坐标

先写个代码再说

https://atcoder.jp/contests/abc230/submissions/34500571

显然 有很多是2 的倍数的,它们如果每个都会去访问n/2, 那么已经就是n^2了, 肯定会超时

想法就是 如果 (2的倍数,3的倍数) 之类做容斥? 但是我容斥完全不会