序列统计 解题过程
lvvd
·
·
个人记录
link
发现确定每种元素数量过后序列就唯一了，接下来是统计方案数。
枚举长度 $len$，发现方案数是简单的组合数学，插板法即可，答案为：
$$
\dbinom{len + R - L + 1 - 1}{R - L + 1 - 1} = \dbinom{len + R - L}{R - L}
$$
但是 $N$ 太大了，枚举不了欸。
$$
\dbinom{len + R - L}{R - L} = \dfrac{(len + R - L)!}{(R - L)! \times len!}
$$
$$
\begin{aligned}
&\sum\limits_{len = 1}^{n}\dfrac{(len + R - L)!}{(R - L)! \times len!}\\
=&\dfrac{\sum\limits_{len = 1}^{n}\dfrac{(len + R - L)!}{len!}}{(R - L)!}\\
=&\dfrac{\sum\limits_{len = 1}^{n}\left(\prod\limits_{j = len + 1}^{len + R - L}j\right)}{(R - L)!}\\
\end{aligned}
$$
在模 $10^{6} + 3$ 的意义下最后乘上 $(R - L)!$ 的逆元即可。
。。。
啊不对不对。
不是这样，重推。令 $X = R - L$。
$$
\begin{aligned}
&\sum\limits_{len = 1}^{n}\dbinom{n + X}{X}\\
=&\dbinom{X + 1}{X} + \dbinom{X + 2}{X} + \dbinom{X + 3}{X} + \cdots + \dbinom{X + n}{X}\\
=&\dbinom{X + 1}{X + 1} + \dbinom{X + 1}{X} + \dbinom{X + 2}{X} + \dbinom{X + 3}{X} + \cdots + \dbinom{X + n}{X} - \dbinom{X + 1}{X + 1}\\
=&\dbinom{X + 2}{X + 1} + \dbinom{X + 2}{X} + \dbinom{X + 3}{X} + \cdots + \dbinom{X + n}{X} - \dbinom{X + 1}{X + 1}\\
=&\dbinom{X + 3}{X + 1} + \dbinom{X + 3}{X} + \cdots + \dbinom{X + n}{X} - \dbinom{X + 1}{X + 1}\\
\cdots\\
=&\dbinom{X + n}{X + 1} + \dbinom{X + n}{X} - \dbinom{X + 1}{X + 1}\\
=&\dbinom{X + n + 1}{X + 1} - \dbinom{X + 1}{X + 1}\\
=&\dbinom{X + n + 1}{X + 1} - 1\\
\end{aligned}
$$
好了，用Lucas定理就好了。
理论存在，实践开始。
Code：
```cpp
#include <bits/stdc++.h>
namespace VividCycle {
#include <bits/stdc++.h>
#define getchar gc
#define putchar pc
#define fu(i, l, r) for(int i = l; i <= r; ++i)
#define fd(i, l, r) for(int i = l; i >= r; --i)
#define fo(i, v) for(const auto& i : v)
using namespace std;
typedef __int128 ll;
typedef unsigned long long ull;
static char buffer[1 << 20 | 1]; static int outp = -1;
void flush() {fwrite(buffer, 1, outp + 1, stdout), outp = -1;}
void pc(const char& ch) {if(outp == (1 << 20)) flush(); buffer[++outp] = ch;}
char gc() {static char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf; return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1000010, stdin), p1 == p2) ? -1 : *p1++;}
template<typename T> void read(T& x) {x = 0; int f = 1; char ch = getchar(); while(ch < '0' || ch > '9') f *= ((ch == '-') ? -1 : 1), ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f;}
template<typename T, typename ...Args> void read(T& x, Args& ...args) {read(x), read(args...);}
void write(const char& ch) {putchar(ch);} void write(const char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);} void write(char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);}
template<typename T> void write(T x) {static char obuf[1 << 8]; static int p; p = 0; if(x < 0) x *= (putchar('-'), -1); if(!x) {putchar('0'); return;} while(x) obuf[++p] = x % 10 ^ 48, x /= 10; while(p) putchar(obuf[p--]);}
template<typename T, typename ...Args> void write(T x, Args ...args) {write(x), write(args...);}
}
using namespace VividCycle;
const int mod = 1000003;
ll t, n, l, r, fact[mod], inv[mod];
ll ksm(ll x, ll y) {
ll ret = 1;
while(y) {
if(y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll c(ll n, ll m) {
if(n < m) return 0;
if(!m) return 1;
return fact[n] * inv[m] % mod * inv[n - m] % mod;
}
ll lucas(ll n, ll m) {
if(!m) return 1;
return lucas(n / mod, m / mod) * c(n % mod, m % mod) % mod;
}
int main() {
fact[0] = 1;
fu(i, 1, mod - 1) fact[i] = fact[i - 1] * i % mod;
inv[mod - 1] = ksm(fact[mod - 1], mod - 2);
fd(i, mod - 1, 1) inv[i - 1] = inv[i] * i % mod;
read(t);
while(t--) {
read(n, l, r);
write((lucas(r - l + n + 1, r - l + 1) + mod - 1) % mod, '\n');
}
flush();
return 0;
}
```