#P4305. 数列的GCD

    ID: 3521 传统题 1000ms 256MiB 尝试: 516 已通过: 159 难度: 6 上传者: 标签>CF1900提高莫比乌斯反演倍数枚举乘法原理阶乘逆元预处理快速幂

数列的GCD

题目描述

给定一个长度为 nn,值域为 [1,m][1,m] 的序列 aa,求对于 d∈[1,m]d\in[1,m] 的每一个 dd,有多少个不同的序列 b1⋯nb_{1\cdots n} 满足:

  • ∀i∈[1,n],bi∈[1,m]\forall i\in[1,n],b_i\in[1,m];
  • gcd⁡i=1n{bi}=d\gcd_{i=1}^n\{b_i\}=d;
  • 恰好 有 kk 个位置满足 ai≠bia_i\not =b_i。

答案对 109+710^9+7 取模。

输入格式

第一行三个整数 n,m,kn,m,k。

第二行 nn 个整数 a1⋯na_{1\cdots n}。

输出格式

一行共 mm 个整数,第 ii 个整数表示 d=id=i 时的答案对 109+710^9+7 取模后的值。

3 3 3
3 3 3
7 1 0

样例解释

当 d=1d=1,$b=\{1,1,1\},\{1,1,2\},\{1,2,1\},\{1,2,2\},\{2,1,1\},\{2,1,2\},\{2,2,1\}$,共 77 个。

当 d=2d=2,b={2,2,2}b=\{2,2,2\},共 11 个。

当 d=3d=3,没有满足条件的序列 bb,共 00 个。

数据规模与约定

对于 100%100\% 的数据,1≤n,m≤3×1051\leq n,m\leq 3\times 10^5,1≤k≤n1\leq k\leq n,1≤ai≤m1\leq a_i\leq m。