[bzoj 4870] [Shoi2017]组合数问题

求

定义下指标大于上指标时, 二项式系数等于0. (1≤n≤10^9, 0≤r<k≤50, 2≤p≤2^30-1) 小葱发现, 是否是的倍数, 取决于是否等于.

说得太好了! 我考试的时候就忘掉了这一点......TAT

本题也是thu校赛练习赛的题目之一, yp同学教了我一下做法. QAQ

n很大, r,k很小, 看起来像矩阵快速幂. 强行构造递推, 用范德蒙德卷积公式:

(原来只知道这个特例)

记答案为, 则

发现转移矩阵是循环的, 所以可以只保留第一行 (虽然在本题中不是必须的).

也可以考虑待求和式的组合意义 (见WrongAnswer的博客). 记为n个物品中取出模k等于r个物品的方案数, 考虑第一个物品选还是不选, 则有

同时, .

此时, 我们也能看到递推式的组合意义: 每k个物品分一组, 一共n组, 第一组取j个.

typedef long long ll;

const int K = 50;

ll C[K+1][K+1];
int p;

struct Matrix {
	ll a[K][K];
	Matrix(ll t=0)
	{
		fill_n(*a, sizeof(a)/sizeof(ll), 0);
		rep (i, 0, K) a[i][i] = t;
	}
	Matrix operator*(const Matrix& o) const
	{
		Matrix r;
		rep (i, 0, K) rep (j, 0, K) rep (k, 0, K)
			(r.a[i][j] += a[i][k] * o.a[k][j]) %= p;
		return r;
	}
	friend Matrix pow(Matrix x, int n)
	{
		Matrix y(1);
		for (; n; n >>= 1, x = x*x)
			if (n & 1)
				y = y * x;
		return y;
	}
} M;

int main()
{
	int n, k, r;
	scanf("%d%d%d%d", &n, &p, &k, &r);

	rep (i, 0, k+1) {
		C[i][0] = 1;
		rep (j, 1, i+1)
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % p;
	}

	M.a[0][0] = 2 % p;
	rep (i, 1, k) M.a[0][i] = C[k][i];
	rep (i, 1, k) {
		M.a[i][0] = M.a[i-1][k-1];
		rep (j, 1, k) M.a[i][j] = M.a[i-1][j-1];
	}

	M = pow(M, n-1);

	ll ans = 2 * M.a[0][r] % p;
	rep (i, 1, k) (ans += C[k][i] * M.a[i][r]) %= p;

	printf("%lld\n", ans);

	return 0;
}