2022 杭电杯(7) I Counting Good Arrays

本题是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筛即可。不需要插值。

原文地址：http://www.cnblogs.com/chdy/p/16870087.html