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

亦凉 2023-06-01 13:59 125阅读 0赞

*  @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 对比发现基本一致。。。

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

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11406974.html