余式系数

令$F_n(x)=x^n, G_m(x)=(x-1)^m$，并记$R_{n,m}(x)$为$F_n(x)$除以$G_m(x)$时所得的余式。例如$R_{6,3}(x)=15x^2-24x+10$。

令$C(n, m, d)$是$R_{n,m}(x)$中$d$次项的系数的绝对值，例如$C(6, 3, 1)=24, C(100, 10, 4)=227197811615775$。

求$C(10^{13}, 10^{12}, 10^4) \bmod 999999937$。

本题难度:

解答

显然 $$F_n(x)=(x-1+1)^n=\sum_{k=0}^{n}\binom{n}{k}(x-1)^k=\sum_{k=0}^{m-1}\binom{n}{k}(x-1)^k \pmod G_m.$$ 因此 $$C(n, m, d)=|\sum_{k=d}^{m-1}\binom{n}{k}\binom{k}{d}(-1)^{k-d}|=\binom{n}{d}\binom{n-d-1}{m-d-1}.$$ 接下来只需实现$f(x,p)=x! \bmod p$函数及其乘法逆，用一个不超过$p$次循环即可实现，最终结果是$472294837$。

注：为了便于用内建函数作快速幂，以下代码为Python 3。

n=10**13
m=10**12
d=10**4
r=10**7+1
mod=10**9-63

f=[0]*r
f[0]=1

for i in range(1,r):
    f[i]=(f[i-1]*i)%mod

def solve(n,m):
    p=1
    while n>0 and m>0:
        a,b=m%mod,n%mod
        if a<=b:
            p*=f[b]*pow(f[a]*f[b-a],mod-2,mod)
            p%=mod
        n//=mod
        m//=mod
    return p%mod
print((solve(n,d)*solve(n-d-1,n-m))%mod)