@atcoder - Japanese Student Championship 2019 Qualification

@description@
@solution@
@accepted code@
@details@

@description@

请找到满足以下条件的长度为 N 的非负整数序列 A1, A2, ..., AN 的数量。

（1）L≤A1+A2+...+AN≤R。

（2）将 N 个元素排成非增序列后，第 M 个元素要等于第 M + 1 个元素。

请将答案 mod 10^9 + 7。

Constraints

所有数都是整数。

1≤M<N≤3×10^5, 1≤L≤R≤3×10^5。

Input

输入形式如下：

N M L R

Output

输出序列数量 mod 10^9 + 7。

Sample Input 1

4 2 3 7

Sample Output 1

105

Sample Input 2

2 1 4 8

Sample Output 2

3

@solution@

即使放在最后一题，但其实这道题也是比较水的组合计数（所以为什么当时我做不起啊喂）。

令 f(N, M, S) 表示序列满足 0 <= A1 + A2 + ... + AN <= S 且满足题目所说的第二个条件时的答案，则最终答案 = f(N, M, R) - f(N, M, L - 1)。

先只考虑 A1 + A2 + ... + AN <= S 的条件，令 B = S - A1 - A2 - ... - AN，则 B >= 0 且 A1 + A2 + ... + AN + B = S。这样转化以后就可以把不等式化为等式，用隔板法可以快速统计出方案数（其实很像线性规划的标准型转松弛型）。

满足第二个条件，一种想法是用 \(C_N^M\) 算前 M 大的数所在的位置，将前 M 大与后 N-M 分开讨论。但是因为数可以相同，这样算出来会重复（即前 M 大可能跟后 N-M 有数字相同，会互相影响）。

但如果反过来，我们令排序后的 A'[M] ≠ A'[M+1]。因为排好序了，所以 A'[M] > A'[M+1] ，这样前 M 大与后 N-M 就分开来了。

通过计算强制不等于的方案数，用不带限制的方案数 - 强制不等于的方案数就可以得到答案。

枚举 A[M] = x，现在的限制转变为要求序列中有 M 个数 >= x，剩余 N - M 个数 < x，且至少要有一个数 = x。可以最后乘上系数 \(C_N^M\) 表示选择哪几个数 >= x。

注意到最后一个条件很碍眼，但是如果去掉可能会算重复。

我们这样来处理：用 “M 个数 >= x, N - M 个数 < x 的方案数” 减去 “M 个数 > x, N - M 个数 < x 的方案数”，即再次使用容斥。

现在问题转为：A1 + A2 + ... + AN + B = S；A[1], A[2], ... A[M] >= p；0 <= A[M+1], A[M+2], ... A[N] < q 的方案数。

限制 A[1], A[2], ... A[M] >= p 可以通过预先将 S 减去 M*p 来处理，这样就可以把 A[1...M] 的下界变成 0。

限制 A[M+1], A[M+2], ... A[N] < q 可以使用容斥，枚举强制选 k 个数 >= q，然后一样将 S 减去 k*q 将下界变成 0。乘上系数 \(C_{N-M}^{k}\) 表示选择哪 k 个数。

最后关于时间复杂度，因为 S - k*q >= 0 才有意义，所以最后的容斥是 O(S/q) 的复杂度，而其他地方的计算是常数级别。

而 q 是从 1...K 中枚举出来的数，所以时间复杂度为 O(S/1 + S/2 + ... + S/K)。因为 S 与 K 同阶，可以近似地看作 O(K log K)。

@accepted code@

#include<cstdio>

const int MAXN = 1000000;

const int MOD = int(1E9) + 7;

int pow_mod(int b, int p) {

	int ret = 1;

	while( p ) {

		if( p & 1 ) ret = 1LL*ret*b%MOD;

		b = 1LL*b*b%MOD;

		p >>= 1;

	}

	return ret;

}

int fct[MAXN + 5], ifct[MAXN + 5];

void init() {

	fct[0] = 1;

	for(int i=1;i<=MAXN;i++)

		fct[i] = 1LL*fct[i-1]*i%MOD;

	ifct[MAXN] = pow_mod(fct[MAXN], MOD-2);

	for(int i=MAXN-1;i>=0;i--)

		ifct[i] = 1LL*ifct[i+1]*(i+1)%MOD;

}

int comb(int n, int m) {return 1LL*fct[n]*ifct[m]%MOD*ifct[n-m]%MOD;}

int solve2(int N, int M, int S, int l, int r) {

	int ret = 0;

	if( S - 1LL*M*r < 0 ) return ret;

	else S -= M*r;

	for(int i=0,f=1;i<=N-M&&S>=0;i++,f=1LL*f*(MOD-1)%MOD,S-=l)

		ret = (ret + 1LL*f*comb(S + N, N)%MOD*comb(N - M, i)%MOD)%MOD;

	return 1LL*ret*comb(N, M)%MOD;

}

//A1 + A2 + ... + AN + B = S, A[1...M] >= r, 0 <= A[M+1...N] < l

//A1 + A2 + ... + AN + B = S - M*r, A[1...M] >= 0, 0 <= A[M+1...N] < l

int solve(int N, int M, int S) {

	int ret = comb(S + N, N);

	for(int i=S;i>=1;i--) {

		int del = (solve2(N, M, S, i, i) + MOD - solve2(N, M, S, i, i + 1))%MOD;

		ret = (ret + MOD - del)%MOD;

	}

	return ret;

}

//A1 + A2 + ... + AN + B = S

int main() {

	init(); int N, M, L, R;

	scanf("%d%d%d%d", &N, &M, &L, &R);

	printf("%d\n", (solve(N, M, R) + MOD - solve(N, M, L - 1))%MOD);

}

@details@

比赛时看着 standings 感觉是一道不可做的题，然后考场上一直在想什么 fft 啊之类的。。。

赛后想了想，发现不对啊，这个不应该用组合数来做吗。

然后就想了一个解法，最后跟 editorial 对比发现基本一致。。。

这个题的每一步推导，都透露出满满的套路气息。。。

巴特西

@atcoder - Japanese Student Championship 2019 Qualification - F@ Candy Retribution

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章