本题是2022CCPC F题的强化版.
给出一个 n,m 求出所有长度小于等于n的数列\(a_k(k\le n)\)且\(a_k\le m\)且\(a_i|a_{i+1}\)
固定n 显然可以发现对于m的标准分解 \(m=p_1^{k_1}p_2^{k_2}...\)对于每个p相互独立 所以此时 \(f_w\)即\(a_k=w\)的方案数这是一个积性函数。
正常情况下可以通过线性筛来求出答案。不过本题n的长度不定。
固定m \(m=p_1^{k_1}p_2^{k_2}...\) 对于某个n来说方案数是 \(C(n+k1-1,k1)\cdot C(n+k2-1,k2)...\)。推导不难。
本质上是一个关于n的w次多项式.前缀和是一个w+1次的多项式 拉格朗日插值一下仅能求出来对于一个m所有n的和.
继续思考对于某个m 需要知道1~w+1的n的值对于全体m呢 取一个较大的次数c 求出1~c的n各个对所有m的答案和。进行插值即可。
对于某个n来求m m很大线性筛解决不了可以考虑 杜教筛或min25筛.
至于CCPC的F题 只需要一次min25筛即可。不需要插值。
标签：...,Good,对于,Arrays,min25,插值,杭电杯,Counting,k2 From： https://www.cnblogs.com/chdy/p/16870087.html