F - Score of Permutations

排列P,

初始,i号人有球i

每次 所有 i != pi 的人, 把球给pi号人

在 > 0 次后,如果所有人又是i号人有球i, 那么就停止

分数 = 最小的次数

求所有排列方案 的分数的k次方的和

mod 998244353

限制

N 50

k 1e4

2 s

1024 mb

我的思路

很明显, 交换的圈构成环, 次数 = lcm(每个环长)

N 很小, 是不是可以枚举因数

dp[i][j] = 使用i个,最大是j,的{lcm,方案数}

dp[i][j] 贡献来自 dp[i- tm][m],m > j, t > 0, 即n-i+tm个中选tm个, 然后分成t组每组m个

因为组合tm中分成t组,每组m个

这样想,tm中最小的作为开头,依次剩下的选m-1个, 然后剩余就是(t-1)m 同样的

这样每次考虑最小的所在环, 就不重不漏

$\binom{n-i+tm}{tm} A(tm-1,m-1) \cdot A((t-1)m-1,m-1) \cdots$

$ = \binom{n-i+tm}{tm} \frac{(tm)!}{m\cdot 2m \cdots tm}$

$ = \binom{n-i+tm}{tm} \frac{(tm)!}{m^t * t!}$

似乎就对了

生成方程

感谢google翻译和maspy大佬的几篇博客, 见下方链接

用很多例子来实例如何使用 多项式乘积

状態ごとに何らかの値が計算されているときに、その計算結果を多項式の形で持ちます。この際、 「多項式の次数」が「考えている状態」、「係数」が状態ごとの「計算した値」（多くの場合、数え上げ）を表すように多項式を持つのが原則です。

括号内是或关系, 括号间幂次是加和关系,系数是代价倍数一般是1

翻译了一下, 统一了一下格式,增加了一些步骤

以下未强调的都是非负整数

注意的是有不少都可以写成无限次方的上限,因为超过n不会影响n,看具体情况哪个更好用用哪个

maspy 1 如何把问题转化

问题1, $A=\{2,3\},B=\{2,4\},C=\{3,5,7\} , a+b+c=n$ 有多少种方法可以

$\lbrack x^n \rbrack (x^2+x^3)(x^2+x^4)(x^3+x^5+x^7)$, 就是乘开后$n$次项的系数

F - String Cards

给N个字符串, 恰好选其中K个, 拼接出的最小字典序的字符串是什么

范围

N 50

|Si| [1,50], 每个长度

只含小写英文字母

2s

1024 mb

我的思路

例如

b和ba

b <= ba

但是

bab <= bba

非前缀的 s1 < s2, 一定s1

s1 是 s2的前缀的 s1 < s2

如果只剩下一个,则s1

否则,形如

1
2
3
4
5
6
7
8
9

[A]
[A][B]
[A][B][C]
[A][B][C][D]

[A][A] ?
[A][B] [A] ?
[A][B][C] [A] ?
[A][B][C][D] [A] ?

如果本身A和B有直接大小, 那么就能知道第一个还是后面3个,A和C再比,A和D再比

但如果A和B依然是前后缀关系, 这会考虑长度,也会考虑要选的个数

少考虑一点, 对于两个

1
2

A
AB

两种排列

1
2

AAB
ABA

长度一致, 考虑是否交换

但感觉两个到三个之间局部性不知道是否成立:

(A,AB)组合A 放在前, (AB,ABC) 组合 AB 放在前, 能否推出 (A,ABC) 中 A要放在前

1
2
3

A
AB
ABC

其实我在想,是不是n^4 可以暴力dp?, 好像会是n^6?

dp[i][j][length], 前i选j,长度=length的最小前缀

G - Roll or Increment

https://atcoder.jp/contests/abc224/tasks/abc224_g

1~N 骰子

初始S, 得分f(X) = X

A元, 让得分+1

B元, 重新转

求最小期望代价, 让得分为T

范围

N 1e9

A,B [1,1e9]

2s

1024 mb

我的思路

日常不会概率论

猜一个

S < T

直接通过A, (T-S)A

转一次的期望 E

(N-T)/N * (B+E), 大于T 部分的贡献

1/N ( min(0,B+E) + min(A,B+E) + min(2A,B+E) + … + min((T-1)A,B+E)), $\le T$ 部分的贡献

$E = \frac{N-T}{N} \cdot (B+E) + \frac{1}{N} ( min(0,B+E) + min(A,B+E) + min(2A,B+E) + \cdots + min((T-1)A,B+E))$

若能求出E, 就做出来了

转化一下

$NB + \sum_{i=0}^{T-1} \text{min}(iA-(B+E),0) = 0$

只有E是变化的, 随着E 增大, 表示式变小, 单调, 可二分

好像还真就过了

G - Vertex Deletion

https://atcoder.jp/contests/abc223/tasks/abc223_g

N 点, 标号1到N, 的树

找有几个点满足, 删了它和它直接相连的边以后, 最大匹配个数 = 原图最大匹配个数

限制

N 2e5

2 s

1024 mb

我的思路

显然如果删了u以后最大匹配个数不变, 那么在原图中u所直接连的点,在删除以后的图中都被选了

否则的话, 其中一个和u可以让匹配数+1

并且这些和u直接相连的点在最大匹配中是必选, 也就是不存在方案让它不被选

又因为结构是树

假设断开u-v的连接

以v为根的连通块为根做树

v必选(和子节点匹配)的条件是,任何一个子树的根未被选

v不被选(不和子节点匹配,可能和父节点匹配)的条件是,所有子树的根被选

感觉像是换根dp

也就是求u作为根 f(u) 为不和子节点匹配的 u的个数

f(u) = !(f(v1) & f(v2) & f(v3))

为了减少枚举,可以变成 子点0的个数统计

f(u) = count(f(v) == 0) > 0

u 交换 v

u 的子节点里没有了v, 更新u

v 的子节点里没有了u, 更新v

顺序就dfs顺序就完了

好像就AC了