题解：洛谷P6078 [CEOI2004] Sweets

这是一道紫题！

我们需要接触一个叫做生成函数的登西。

洛谷

---

思路

对于至少 $a$ 个，不超过 $b$ 个的限制，可以先求出限制不超过 $b$ 个的方案数，然后减去限制不超过 $a-1$ 个的方案数，即为答案。

对第 $i$ 个糖果罐列出其的生成函数，得：

$$F_i(x)=\sum_{j=0}^{m_i}{x^j}=\frac{1-x^{m_i+1}}{1-x}$$

因此，设答案为G(x):

$$G(x)=$$

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod=2004;

ll n,a,b;
ll c[15];

ll C(ll x,ll y)
{
	if(y>x)
	{
		return 0;
	}
	
	ll ans=1,ans1=1;
	
	for(ll i=1;i<=y;i++)
	{
		ans1*=i;
	}
	for(ll i=x;i>x-y;i--)
	{
		ans=(ans*i)%(mod*ans1);
	}
	
	return ans/ans1;
}

ll dfs(ll x,ll y,ll sum)
{
	if(x>n)
	{
		return y*C(sum+n,n)%mod;
	}    
	                     
	return (dfs(x+1,y,sum)+dfs(x+1,-y,sum-c[x]-1))%mod;
}
                                                
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	                         
 	cin>>n>>a>>b;                 
	                                 
	for(ll i=1;i<=n;i++)
	{
		cin>>c[i];                
	}                                           
	
	cout<<((dfs(1,1,b)-dfs(1,1,a-1))%mod+mod)%mod<<"\n";
	
	return 0;                                            
}                                                                                 

---

咕了，学不懂数学