bzoj4314题解

定义$f(x,y)=\prod _{i=0}^{n-1}(1+x^iy)$，这里做乘法的时候$x$是模$n$的循环卷积，而y是普通卷积. 那么答案就是$[x^0y^k]f(x,y)$.

这个循环卷积不好处理，注意到DFT本质上就是一个循环卷积，我们可以考虑使用IDFT，答案就是

$$\frac{1}{n}[y^k]\sum f(\omega _n^i,y)\omega _n^{-i\cdot 0}$$

想办法化简这个式子

$$\begin{aligned}&\sum f(\omega _n^i,y)\\\\=&\sum _{i=0}^{n-1}\prod _{j=0}^{n-1}(1+\omega _n^{ij}y)\\\\=&\sum _{d|n}\sum _{(i,n)=d}\prod _{j=0}^{n-1}(1+(\omega _{n/d}^{i/d})^jy)\\\\=&\sum _{d|n}\sum _{(i,n)=d}\prod _{j=0}^{n-1}(1+\omega _{n/d}^jy)\\\\=&\sum _{d|n}\sum _{(i,n)=d}(\prod _{j=0}^{n/d-1}(1+\omega _{n/d}^jy))^d\end{aligned}$$

这个时候要用到一个结论

$$\prod _{i=0}^{n-1}(x-\omega _n^iy)=x^n-y^n$$

证明的话，把$x=\omega _n^iy(i=0,1,\ldots,n-1)$带入，发现两边都是0，而两边都是$n$次的，说明这是个恒等式.

把$x=-1$带入上式，两边再乘上$(-1)^n$，就可以得到

$$\prod _{i=0}^{n-1}(1+\omega _n^iy)=1-(-y)^n$$

回到我们原来要推的那个式子，可以变形为

$$\begin{aligned}&\sum _{d|n}\sum _{(i,n)=d}(\prod _{j=0}^{n/d-1}(1+\omega _{n/d}^jy))^d\\\\=&\sum _{d|n}\sum _{(i,n)=d}(1-(-y)^{n/d})^d\\\\=&\sum _{d|n}(1-(-y)^{n/d})^d\varphi(n/d)\end{aligned}$$

要求这个式子中$y^k$的系数，直接用二项式定理展开就可以了. 组合数可以把阶乘分段打表来算.

可以注意到，$k$的范围扩大到$10^9$也是可以做的，要求的余数不是0而是一个由输入给定的值也是可以做的（当然式子需要再推一推）.

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ele int
#define ll long long
using namespace std;
#define maxk 1010
#define MOD 1000000007
#define K 400000
const ele tf[]={};//这里省略阶乘的表
ele n,k,phi[maxk];
inline ele get_phi(ele n){
	ele ans=n,tmp=n;
	for (int i=2; i*i<=n; ++i)
		if (tmp%i==0){
			ans/=i; ans*=i-1;
			while (tmp%i==0) tmp/=i;
		}
	if (tmp>1) ans/=tmp,ans*=tmp-1;
	return ans;
}
inline ele pw(ele a,ele x){
	ele ans=1,tmp=a%MOD;
	for (; x; x>>=1,tmp=(ll)tmp*tmp%MOD)
		if (x&1) ans=(ll)ans*tmp%MOD;
	return ans;
}
inline ele fac(ele n){
	ele ans=tf[n/K];
	for (int i=n/K*K+1; i<=n; ++i) ans=(ll)ans*i%MOD;
	return ans;
}
inline ele ifac(ele n){
	return pw(fac(n),MOD-2);
}
inline ele C(ele n,ele m){
	return (ll)fac(n)*ifac(m)%MOD*ifac(n-m)%MOD;
}
inline ele calc(ele d){
	if (k%(n/d)) return 0;
	ele c=k/(n/d);
	ele ans=(ll)C(d,c)*phi[n/d]%MOD;
	if (n/d%2==0 && c%2) ans=ans?MOD-ans:0;
	return ans;
}
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1; i<=k; ++i) phi[i]=get_phi(i);
	ele ans=0;
	for (int d=1; d*d<=n; ++d)
		if (n%d==0){
			(ans+=calc(d))%=MOD;
			if (d*d!=n) (ans+=calc(n/d))%=MOD;
		}
	ans=(ll)ans*pw(n,MOD-2)%MOD;
	printf("%d\n",ans);
	return 0;
}