8305: BZOJ4305:数列的GCD

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给出一个长度为N的数列{a[n]},1<=a[i]<=M(1<=i<=N)。  现在问题是,对于1到M的每个整数d,有多少个不同的数列b[1], b[2], ..., b[N],满足:  (1)1<=b[i]<=M(1<=i<=N);  (2)gcd(b[1], b[2], ..., b[N])=d;  (3)恰好有K个位置i使得a[i]<>b[i](1<=i<=N)  注:gcd(x1,x2,...,xn)为x1, x2, ..., xn的最大公约数。  输出答案对1,000,000,007取模的值。 


输入格式

第一行包含3个整数,N,M,K。  第二行包含N个整数:a[1], a[2], ..., a[N]。 


输出格式

输出M个整数到一行,第i个整数为当d=i时满足条件的不同数列{b[n]}的数目mod 1,000,000,007的值。 


样例输入

3 3 3
3 3 3

样例输出

7 1 0

提示

当d=1,{b[n]}可以为:(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1)。  当d=2,{b[n]}可以为:(2, 2, 2)。  当d=3,因为{b[n]}必须要有k个数与{a[n]}不同,所以{b[n]}不能为(3, 3, 3),满足条件的一个都没有。  对于100%的数据,1<=N,M<=300000, 1<=K<=N, 1<=a[i]<=M。 


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: