1 条题解
-
0
前置知识
解法
记 ,枚举长度 ,等价于求 的非负整数解的数量。接着推式子就行。
$\begin{aligned} \sum\limits_{i=1}^{n}\dbinom{m+i-1}{i} \end{aligned}$
$\begin{aligned} &=\dbinom{m}{0}-1+\sum\limits_{i=1}^{n}\dbinom{m+i-1}{i} \end{aligned}$
$\begin{aligned} &=\dbinom{m}{1}+\dbinom{m}{0}-1+\sum\limits_{i=2}^{n}\dbinom{m+i-1}{i} \end{aligned}$
$\begin{aligned} &=\dbinom{m+1}{1}-1+\sum\limits_{i=2}^{n}\dbinom{m+i-1}{i} \end{aligned}$
$\begin{aligned} &=\dbinom{m+k}{k}-1+\sum\limits_{i=k+1}^{n}\dbinom{m+i-1}{i} \end{aligned}$
$\begin{aligned} &=\dbinom{m+n-1}{n-1}+\dbinom{m+n-1}{n}-1 \end{aligned}$
因为 较大,所以需要跑卢卡斯定理。
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define sort stable_sort #define endl '\n' ll inv[1000010],jc[1000010],jc_inv[1000010]; ll C(ll n,ll m,ll p) { if(n>=m&&n>=0&&m>=0) { return (jc[n]*jc_inv[m]%p)*jc_inv[n-m]%p; } else { return 0; } } ll lucas(ll n,ll m,ll p) { return m?C(n%p,m%p,p)*lucas(n/p,m/p,p)%p:1; } int main() { ll t,n,m,l,r,i,p=1000003; cin>>t; inv[1]=1; jc[0]=jc_inv[0]=jc[1]=jc_inv[1]=1; for(i=2;i<=p-1;i++) { inv[i]=(p-p/i)*inv[p%i]%p; jc[i]=jc[i-1]*i%p; jc_inv[i]=jc_inv[i-1]*inv[i]%p; } for(i=1;i<=t;i++) { cin>>n>>l>>r; m=r-l+1; cout<<(lucas(n+m,n,p)+p-1)%p<<endl; } return 0; }
- 1
信息
- ID
- 4403
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 42
- 已通过
- 18
- 上传者