好题：序列统计

好题：序列统计 - 题解

题面

序列统计

分析：
读完题目，发现数据规模很大，且是多测，那么考虑 O ( 1 ) O(1) O(1) 或 O ( l o g n ) O(log_n) O(logn) 的复杂度进行求解。

因为对于每组数据而言，我们都要求出序列长度分别从 1 1 1 到 N N N 的方案和，所以不妨设 g ( i ) g(i) g(i) 表示对于当前数据而言，构造出长度为 i i i 且符合题意单调不降的序列方案数。则有：

r e s = ∑ i = 1 N g ( i ) res = sum_{i = 1}^{N}g(i) res=∑i=1Ng(i)

接下来我们考虑 g ( m ) g(m) g(m) 应该怎么求。

因为题面要求单调不降，而在 [ L , R ] [L, R] [L,R] 中任意选 m m m 个数我们都可以通过一定的摆放方式满足题意。但是两种方案不同只能是至少一种数字的数量不同。在 [ L , R ] [L, R] [L,R] 中一共有 k = R − L + 1 k = R - L + 1 k=R−L+1 种数字。我们设 x 1 , x 2 , x 3 , . . . , x k x_1, x_2, x_3, ..., x_k x1,x2,x3,...,xk 分别表示第 1 , 2 , 3 , . . . , k 1, 2, 3, ..., k 1,2,3,...,k 种数字选的个数。那么问题可转化为：

已知数 m m m 且

x 1 + x 2 + x 3 + . . . + x k = m ( x i ≥ 0 ) x1 + x2 + x3 + ... + x_k = m (x_i geq 0) x1+x2+x3+...+xk=m(xi≥0) 。求满足条件的解的个数。

也就是 g ( m ) g(m) g(m) 的大小就等于这个不定方程解的数量。

根据隔板法我们可知 g ( m ) = C m + k − 1 k − 1 g(m) = C_{m + k - 1}^{k - 1} g(m)=Cm+k−1k−1

因此，我们就可以将 r e s res res 表示出来：

r e s = ∑ i = 1 N C i + k − 1 k − 1 res = sum_{i = 1}^{N}C_{i + k - 1}^{k - 1} res=∑i=1NCi+k−1k−1

由于 C n m = C n n − m C_{n}^{m} = C_{n}^{n - m} Cnm=Cnn−m ，因此可将等式进一步变形：
r e s = ∑ i = 1 N C i + k − 1 k − 1 = ∑ i = 1 N C i + k − 1 i res = sum_{i = 1}^{N}C_{i + k - 1}^{k - 1} = sum_{i = 1}^{N}C_{i + k - 1}^{i} res=∑i=1NCi+k−1k−1=∑i=1NCi+k−1i

写下来就是：

r e s = C k 1 + C k + 1 2 + C k + 2 3 + . . . + C k + N − 1 N res = C_{k}^{1} + C_{k + 1}^{2} + C_{k + 2}^{3} + ... + C_{k + N - 1}^{N} res=Ck1+Ck+12+Ck+23+...+Ck+N−1N

再根据 C n m = C n − 1 m + C n − 1 m − 1 C_{n}^{m} = C_{n - 1}^{m} + C_{n - 1}^{m - 1} Cnm=Cn−1m+Cn−1m−1，我们可以在等式右边的开头加上 C k 0 C_{k}^{0} Ck0 ，结尾减去 C k 0 C_{k}^{0} Ck0，那么等式化为：

r e s = C k 0 + C k 1 + C k + 1 2 + C k + 2 3 + . . . + C k + N − 1 N − C k 0 res = C_{k}^{0} +C_{k}^{1} + C_{k + 1}^{2} + C_{k + 2}^{3} + ... + C_{k + N - 1}^{N} - C_{k}^{0} res=Ck0+Ck1+Ck+12+Ck+23+...+Ck+N−1N−Ck0

= C k + 1 1 + C k + 1 2 + C k + 2 3 + . . . + C k + N − 1 N − C k 0 = C_{k + 1}^{1} +C_{k + 1}^{2} + C_{k + 2}^{3} + ... + C_{k + N - 1}^{N} - C_{k}^{0} =Ck+11+Ck+12+Ck+23+...+Ck+N−1N−Ck0

= C k + 2 2 + C k + 2 3 + . . . + C k + N − 1 N − C k 0 = C_{k + 2}^{2} +C_{k + 2}^{3} + ... + C_{k + N - 1}^{N} - C_{k}^{0} =Ck+22+Ck+23+...+Ck+N−1N−Ck0

= . . . = ... =...

= C k + N N − C k 0 = C k + N N − 1 = C_{k + N}^{N} - C_{k}^{0} = C_{k + N}^{N} - 1 =Ck+NN−Ck0=Ck+NN−1

k k k 和 N N N 很大，但是有取余运算，我们可以使用 L u c a s Lucas Lucas 定理。至此，问题得到了解决。

CODE：

#include
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL T, n, L, R, mod = 1e6 + 3, fac[N], inv[N];
LL q_pow(LL x, LL y){
	LL res = 1;
	while(y){
		if(y & 1) res = (res * x) % mod;
		x = (x * x) % mod;
		y >>= 1;
	}
	return res % mod;
}
void pre_work(){
	fac[0] = 1;
	for(int i = 1; i < mod; i++)
	    fac[i] = (fac[i - 1] * i) % mod;
	inv[mod - 1] = q_pow(fac[mod - 1], mod - 2);;
	for(int i = mod - 2; i >= 0; i--){
		inv[i] = (inv[i + 1] * (i + 1)) % mod;
	}
}
LL C(LL n, LL m){
	if(n < m) return 0;
	else return (((fac[n] * inv[m]) % mod) * inv[n - m]) % mod;
}
LL lucas(LL n, LL m){
	if(n < mod && m < mod) return C(n, m);
	else return ((C(n % mod, m % mod) % mod) * (lucas(n / mod, m / mod) % mod)) % mod;
}
int main(){
	freopen("squeence.in", "r", stdin);
	freopen("squeence.out", "w", stdout);
	pre_work();
	scanf("%d", &T);
	while(T--){
		scanf("%lld%lld%lld", &n, &L, &R);
		LL k = R - L + 1;
		LL res = lucas(n + k, n);
        if(res == 0) res = mod;
		printf("%lldn", res - 1);
	}
	return 0;
}

好题：序列统计 - 题解

Java相关栏目本月热门文章