首先答案能用生成函数的角度求出：令 \(C(x)=\sum\limits_{i=0}^{n-1} (1+x)^{id}\)，则 \(f(j)=[x^j]C(x)\) 。 就是求 \(C(x)\) 的前 \(m\) 项系数。
考虑这是等比数列求和，令 \(A(x)=\frac{(1+x)^{nd}-1}{x},B(x)=\frac{(1+x)^{d}-1}{x}\) ，则 \(C(x)=\frac{A(x)}{B(x)}\) 。
\(A\) 和 \(B\) 都是容易求出的，把模数拆成 \(M=\prod p_i^{c_i}\) 的形式，求出模 \(p_i^{c_i}\) 时的一行组合数是不难的（记录一下 \(p_i\) 的次数，其他的正常乘），然后再 CRT 合并。
令 \(f_i=[x^i]A(x),g_i=[x^i]B(x),h_i=[x^i]C(x)\) 。
先考虑 \(gcd(d,M)=1\) 这档分， \(g_0h_i=f_i-\sum\limits_{j=1}^{d-1}g_jh_{i-j}\) 。
因为 \(g_0=d\) ，所以可以求逆元，我们就能 \(O(md)\) 算出来。
\(gcd(d,M)\ne 1\) 怎么办？到这里我就不会了/kk
还是把 \(M\) 拆成 \(\prod p_i^{c_i}\) 的形式，把模 \(p_i^{c_i}\) 的答案算出来，再 CRT 合并。注意 \(d\) 不是 \(p_i\) 倍数的部分，可以乘在一起，用上面的方法处理。
对于 \(d\) 是 \(p_i\) 的倍数，……（未写完）
标签：frac,gcd,CRT,求和,sum,Day,2019,LOJ3075 From： https://www.cnblogs.com/cwhfy/p/17113756.html