Educational Codeforces Round 123
https://codeforces.com/contest/1644
F. Basis
F(a数组,k数字) = 把a每个数组重复k次, 然后取 和a等长的前缀 [a_0_1,a_0_2...,a_0_k, a_1_1...a_1,k, a_2_1,...,a_2_k,...]
`x!=y, G(a数组,x数字,y数字) = 把a中所有x变成y, 所有y变成x
如果满足以下条件,则称a数组是b数组的父数组:
- 存在 k使得F(a,k) = b
- 或者 存在x!=y, G(a,x,y) = b
如果 有父数组链关系, 则称作祖先
问题, 给定n,k
构造系列 数组s={ s1,s2,..,sm}
每个si包含n个元素, si中的的值\in [1,k]
对于 任意的长n 值在 [1,k]的数组a, 至少在你给的s中存在一个si是a的祖先
问s的最小长度 mod 998244353
范围
n,k 2e5
6s
512mb
我的思路
si 通过 F,G的操作能变成任意数组
一个纯数字的数组, 那么通过F操作一定是自己的祖先,
两个不同的纯数字数组, 通过一次G操作 互为祖先
纯数字数组, 通过两次操作G一定是自己的祖先,
每个数组通过巨大k 操作, 都能变成纯数字数组
G的性质, 让数组的内容和具体值无关, 变成的一段一段的同样的值,(可以看成交换)
所以 比如 xxxyyyxxzz 是否能达到, 就是看 111221133 是否能达到
F的性质, 则是说不要考虑任何 x * w y * w z * w 的形状, 也就是能找到一个连续段的分割, 因为它总对应一个更小的
如果 k >= n, 那么就好了 [1,2,3,…,n], 啥都能变
–
考虑 k < n
两个没有 前缀 循环节的如何判断是否可以相互转化呢
1 | n=5,k=4 |
一个猜想, 没有用完k的一定可以由 用完k的转化来, 因为至少有同色的个数 >= 2, 而且它不能转化回去(所以它的父一旦能被表示它则一定被表示, 所以它自身不需要存在)
两个序列之间如果可以转化 则 一定没有F操作, 否则形状会变有周期的,
而两个序列如果之间有G操作, 则不满足 从小到达命名1,2,3,4 的性质
综上, 需要统计
长度n, 用完k个,没有循环段, 且满足顺序赋值的个数(每个位置的值 <= 之前用的最大值+1)
有循环段很好算,枚举循环长度就行, 所以就找出满足 顺序赋值 的个数 再来减法
f[i][t] = 前i个最大命名为t的方案数
f[i][t] = f[i-1][t] * t + f[i-1][t-1] * 1, 分别是用前面一样的和用更大的
那么ans = f[n][k] - 有循环段的
直接搞是 O(n^2)
看成生成方程
$f_i(x) = f_{i-1}’(x) x + x f_{i-1}(x)$
$f_i(x)e^x = x (f_{i-1}e^x)’$
$令a_i = f_i(x)e^x$
再看 系数 $a[i][t] = a[i-1][t] * t$
所以 $a[n][t] = a[0][t] * t^n$
然后乘上$f[n] = a[n] * e^{-x}$ 就能得到 f[n][k]完了?
$a[0] = f[0] * e^x$
似乎有点问题