[BZOJ 4403]序列统计
转载请注明出处：http://danihao123.is-programmer.com/
老早做的题……
一看单调不降就想去用差分……但差分不好推（比下面的颓法要多一步……）。其实我们发现，只要给[L,R]里每种整数分配出现次数，原序列就可以唯一确定了。
因此我们把[L,R]中每个整数的出现次数当做一个变量，他们加起来应该等于一个[1,n]中的整数。用隔板法很容易退出来式子是（令l=R−L+1）：
\sum_{i = 1}^n \binom{i + l - 1}{l - 1}
看起来玩不动了……但是我们给式子加上一个\binom{l}{l}（其实就是1），然后我们会发现式子可以用杨辉三角的递推式合并成一个组合数，即\binom{n + l}{l}。然后求这个组合数还需要Lucas定理……
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | /************************************************************** Problem: 4403 User: danihao123 Language: C++ Result: Accepted Time:908 ms Memory:16448 kb****************************************************************/ #include <cstdio>#include <cstring>#include <cstdlib>#include <cctype>#include <algorithm>#include <utility>typedef long long ll;const ll ha = 1000003LL;const int maxn = 1000003;ll pow_mod(ll a, ll b) { ll ans = 1LL, res = a % ha; while(b) { if(1LL & b) ans = (ans * res) % ha; res = (res * res) % ha; b >>= 1; } return ans;}ll f[maxn], g[maxn];void process() { f[0] = 1LL; for(int i = 1; i < maxn; i ++) { f[i] = (f[i - 1] * (ll(i))) % ha; } g[maxn - 1] = pow_mod(f[maxn - 1], ha - 2LL); for(int i = maxn - 2; i >= 0; i --) { g[i] = (g[i + 1] * (ll(i + 1))) % ha; }} ll C(int a, int b) { if(a < b) return 0LL; return (((f[a] * g[b]) % ha) * g[a - b]) % ha;}ll calc(int a, int b) { if(a < b) return 0LL; if(b == 0) return 1LL; if(a < ha && b < ha) { return C(a, b); } else { int as = a % ha, bs = b % ha; return (C(as, bs) * calc(a / ha, b / ha)) % ha; }} int main() { process(); int T; scanf("%d", &T); while(T --) { int n, l, r; scanf("%d%d%d", &n, &l, &r); int len = r - l + 1; printf("%lld\n", (calc(n + len, len) - 1LL + ha) % ha); } return 0;} |
评论 (0)
