C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 400K, 提交时间: 2023-07-05 12:38:57

#include<bits/stdc++.h>
#define endl "\n"
#define lowbit(x) (x&(-x))
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const ll mod = 2004;
ll yz=1;
ll C(ll n,ll m){
	if(n<m)return 0;
	ll res=1,p=mod*yz;
	for(ll i=n-m+1;i<=n;i++){
		res=res*i%p;
	}
	return ((res/yz)%mod+mod)%mod;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n,a,b;
	cin>>n>>a>>b;
	vector<ll>f(n);
	for(int i=0;i<n;i++){
		cin>>f[i];
		yz*=(i+1);
	}
	ll ans=0;
	for(int i=0;i<(1ll<<n);i++){
		ll num=0,x=0;
		for(int j=0;j<n;j++){
			if(i&(1ll<<j)){
				num++;
				x+=f[j]+1ll;
			}
		}
		if(x>b)continue;
		if(num&1){
			ans=((ans-C(b-x+n,n)+C(a-x+n-1,n))%mod+mod)%mod;
		}else {
			ans=((ans+C(b-x+n,n)-C(a-x+n-1,n))%mod+mod)%mod;
		}
	}
	cout<<(ans%mod+mod)%mod<<endl;
	return 0;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 556K, 提交时间: 2021-11-25 22:23:03

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 2004

int n,l,r;
int a[25],fac = 1,sum;

int C(int x,int y){
	int M = mod*fac, ans = 1;
	for(int i = y-x+1; i <= y; ++i) ans = ans*i%M;
	return (ans/fac)%mod;
}

void dfs(int k,int val,int q,int lim){
	if(q>lim) return;
	if(k==n+1){
		sum = (sum+val*C(n,n+lim-q)%mod)%mod;
		return ;
	}
	dfs(k+1,val,q,lim); dfs(k+1,-val,q+a[k]+1,lim);
}

inline int sol(int x){
	sum = 0;
	dfs(1,1,0,x);
	return (sum%mod+mod)%mod;
}

signed main(){
	cin>>n>>l>>r;for(int i = 1; i <= n; ++i) cin>>a[i],fac = fac*i;
	cout<<(sol(r)-sol(l-1)+mod)%mod;
	return 0;
}