给定 $n$ , $p$ , $r$ , $k$ ( $1\le n\le 10^9$ , $0\le r,2\le p\le 2^{30}-1$ )，求

$$\sum_{i\bmod k=r}{nk\choose i}\bmod p $$

题解

$$\begin{aligned}&\sum_{i\bmod k=r}{nk\choose i}\\=&\sum_{i\bmod k=r}[x^i](1+x)^{nk}\\=& [x^r]\left((1+x)^{nk}\bmod(x^k-1)\right)\end{aligned} $$

循环卷积快速幂。

也可以组合意义+矩阵乘法优化dp。

代码

const int N = 60;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, p, k, r;
	int add(int a, int b) { return a + b > p? a + b - p: a + b; }
	int dec(int a, int b) { return a - b < 0? a - b + p: a - b; }
	int mul(int a, int b) { return 1ll * a * b % p; }
	void times(int *f, int *g) {
		static int h[N];
		for (int i = 0; i < k; ++i)
			for (int j = 0; j < k; ++j)
				h[(i + j) % k] = add(h[(i + j) % k], mul(f[i], g[j]));
		memcpy (f, h, sizeof (int) * k); memset (h, 0, sizeof (int) * k);
	}
	int a[N], ans[N];
	int main () {
		n = read(), p = read(), k = read(), r = read();
		if (k == 1) a[0] = 2 % p; else a[0] = a[1] = 1;
		ans[0] = 1;
		for (ll b = 1ll * n * k; b; b >>= 1, times(a, a))
			if (b & 1) times(ans, a);
		printf ("%d\n", ans[r]);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}