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

https://codeforces.com/contest/1762

D. GCD Queries

交互题

有 [0…n-1] 的排列 固定但是隐藏

你最多 2n 次询问, 找到2个下标, 其中一个要是0的下标

每次可以询问 gcd(a[i],a[j]), i!=j

范围

n 2e4

3s

256mb

我的思路

筛出 2的倍数

筛出 4的倍数

这样下去就可以了

但 次数无法保证

要找2的倍数 首先得找到一个是2的倍数的, 这最坏需要 n/2 + 3 次, 再找 就需要 n - 4 次

https://codeforces.com/contest/1766

F. MCF

n 点 m边 网络求一个最大流,最小费用 方案

且满足每条边上 实际流 与 其容量 奇偶性一致

输出方案, 或不存在

范围

n 100

m 200

容量 [1,100]

单位代价 wi [-100,100]

我的思路

想着把奇数处理掉, 剩下就是容量处以2, 费用乘以2的问题了

但不会处理奇数, 想到可以每个点出度入度, 但具体也不会

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

G - Farthest CIty

问 n个点, 的简单连通图, 1到n的距离 严格大于所有1到其它点的距离的 图有多少个

个数 mod m

范围

n 500

m [1e8,1e9]

4s

1024mb

我的思路

数数嘛, 对于一个具体的图, 考虑计算所有点到1的距离,看一下相邻点的性质,

显然 相邻点的距离值 差不大于1

所以有一个O(n^4) 的dp

dp[最大距离为i][距离为i的有j个][距离<=i的有k个] = 的方案数

有转移 dp[i][j0][k0] = dp[i-1][j1][k1] * binom(n-k1,j0)/j0个在剩下的中选/ * (2^(j1)-1)^j0(每个分别和前面j1的连接方式) * 2^(j0(j0-1)/2) (j0个内部的任意连接) , 其中 k0=k1+j0

这样答案就是 sum dp[1..n][1][n]

要是能优化成O(n^3)就能过了, 比赛时想了半天, 发现i无关, 想说矩阵乘法快速幂次, binom拆一拆 搞了半天

---

赛后又想了想, 可以完全不要 i 直接 dp[用了k个点][最大距离的有j个点]的方案数 就完了………………..

dp[i0][j0] = dp[i1][j1] * binom(n-i1,j0) * (2^{j1}-1)^j0 * 2^(j0(j0-1)/2), 其中 i0=i1+j0

ans=dp[n][1]

其实这里有点问题, 因为中间选的时候不能选择 最后一个

所以不妨 先把 n拿出来 最后考虑它

这样转移方程不变

ans= sum dp[n-1][j=1..n-1] * (2^j-1)

---

然后加个预处理 去掉 中间的log复杂度