大于 $\max(c_i c_j)$ 的 $ v = \gcd(c_i) \ (i \in [1, n])$ 的倍数都可以被取到。
先做关于 $v$ 的循环卷积,然后背包一下把中间相差的部分补上即可。
由于要求对 $10^9+7$ 取模,所以需要 MTT。

与上一题类似,我们可以考虑生成函数。但是由于本题是 $\mod m$ 意义下的乘法,所以我们可以把原来的乘法转换为与 $m$ 的原根的对数的加法。再用上题目类似的思路即可。

定义生成函数 $f$ :

$$
f(x) = \sum\limits_{i=0}^{\varphi(m)} tag(i) \times x^i
$$

其中 $tag(i) = 1$ 当且仅当存在 $x \in S$ 使得 $\log_g x = i$ 。

最后答案为:

$$
[x^k]f^n(x)
$$

CF1096G - Lucky Tickets

一道生成函数板题,定义生成函数 $f$:
$$
f(x) = \sum\limits_{i=0}^{\infty} tag(i) \times x^i
$$

若集合中有 $i$ 则,$tag(i) = 1$ ;否则 $tag(i) = 0$ 。

则 $[x^i]f^n(x)$ 表示选 $n$ 项时和为 $i$ 的方案数。

容易发现答案即:

$$
\sum\limits_{i=0}^{\infty} ([x^i] f^n(x))^2
$$

多项式快速幂即可。

BZOJ4178 - A

今天模拟赛的第一题, NTT 作多项式乘法,把后面的转移快速幂一下就过了。需要注意的是 950009857 的原根是 7 而不是 3 。

洛谷5106 - dkw的lcm

积性函数的定义: 如果 $(a,b) = 1$ ,那么 $f(ab) = f(a) \times f(b)$ 。 显然欧拉函数是积性函数。

设 $lcm(i_1, i_2, …, i_k) = x$ ,我们把 $x$ 表示成 $x = \prod {p_i ^ {a_i}}$ 的形式。对每个 $p_i ^ { a_i }$ 分开考虑,枚举每个质数与幂次,用简单容斥统计出每个 $\varphi({p_i ^ {a_i}})$ 在答案中出现的次数,通过欧拉定理 + 快速幂计算答案。

假设我们当前枚举的质数为 $p^k$ ,我们把 $[1..n]$ 的数分成三个集合 $A, B, C$

  • 对于每个 $x \in A$ ,当且仅当 $p^k \not\mid x$;
  • 对于每个 $x \in B$ ,当且仅当 $p^k \mid x$ 且 $p^{k + 1} \not\mid x$ ;
  • 对于每个 $x \in C$ ,当且仅当 $p^{k+1} \mid x$。

则答案中 $\varphi({p^k})$ 的幂次相当于给 $k$ 个空位,只能放集合 $A$ 和 $B$ 中的元素且集合 $B$ 中的元素至少放一次的方案数,即 $(|A| + |B|)^k - |A|^k$,此处的值可能会超过 int 的存储范围,因而根据欧拉定理,对 $\varphi(10^9+7) $ (即 $ 10^9+6$ )取模。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×