老早做的题……

一看单调不降就想去用差分……但差分不好推（比下面的颓法要多一步……）。其实我们发现，只要给\([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定理……

代码：

/**************************************************************
    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;
}

• 相关文章
• 全局相关文章