TopCoder SRM 502 TheCowDivOne

题意

给定(n,K)，求从({0,1,cdots,n-1})选出(K)个数，和为(n)的倍数的方案数
(Kle 10^3)
(nle 10^9)

做法

显然有

[ans=sum_{i=0}^{frac{n(n-1)}{2}} [n|i][x^i][y^k]prod_{j=0}^{n-1} (1+x^jy) ]

根据([n|k]=frac{1}{n}sumlimits_{i=0}^{n-1}omega_n^{ik})，有：

[ans=[y^k]frac{1}{n}sumlimits_{i=0}^{n-1}prodlimits_{j=0}^{n-1}(1+omega_n^{ij}y) ]

结论1：(prodlimits_{i=0}^{n-1}(1+omega_n^{ki}y)=(prodlimits_{i=0}^{frac{n}{t}-1}(1+omega_{frac{n}{t}}^{i}))^{t})（其中(t=(n,k))）

证明：
显然((prodlimits_{i=0}^{frac{n}{t}-1}(1+omega_{frac{n}{t}}^{frac{k}{t}i}))^{t})
由于((frac{k}{t}frac{n}{t})=1)，且({0,1,cdots,frac{n}{t}-1})是模(frac{n}{t})的完全剩余系
故({frac{k}{t}i|iin[0,frac{n}{t})})也是模(frac{n}{t})的完全剩余系，得证。

我们枚举((n,k)=frac{n}{d})，很容易得到

[ans=[y^k]{1over n} sum_{d|n} phi(d)prod_{j=0}^{d-1} (1+omega_d^{j}y)^{nover d} ]

结论2：(prodlimits_{i=0}^{n-1}(1+omega_n^iy)=1+(-1)^{n+1}y^n)

证明：
根据定理：(x^n-1=prodlimits_{i=0}^{n-1}(x-omega_n^i))
我们知道(prodlimits_{i=0}^{n-1}(1+omega_n^iy))只有(y^0,y^n)的系数可能不为(0)
(y^0)的系数显然为(1)，(y^n)的系数为(omega_n^{frac{n(n-1)}{2}})
若(n)为奇数，(omega_n^{frac{n(n-1)}{2}}=(omega_n^n)^{frac{(n-1)}{2}}=1^{frac{(n-1)}{2}}=1)
若(n)为偶数，(omega_n^{frac{n(n-1)}{2}}=(omega_n^{frac{n}{2}})^{n-1}=(-1)^{n-1}=-1)
故(omega_n^{frac{n(n-1)}{2}}=(-1)^{n+1})，得证。

[egin{aligned} ans&=[y^k]frac{1}{n}sumlimits_{d|n}phi(d)(1+(-1)^{d+1}y^d)^{frac{n}{d}}\ &=[y^k]frac{1}{n}sumlimits_{d|n}phi(d)sumlimits_{j=0}^{frac{n}{d}}{frac{n}{d}choose j}(-1)^{(d+1)j}y^{dj}\ &=frac{1}{n}sumlimits_{d|n,d|k}phi(d){frac{n}{d}choose frac{k}{d}}(-1)^{(d+1)frac{k}{d}}\ end{aligned}]

由于(kle 1000)，可以直接暴力算