Description
给出\(n(n\leq10),a,b(a,b\leq10^7)\)与\(\{c_n\}(c_i\leq10^6)\)，求使得\(\sum_{i=1}^n x_i \in[a,b]\)且\(x_i\in[0,c_i]\)的方案数，对\(2004\)取模。
Solution
定义\(f(m)\)表示“将不超过\(m\)个物品放入\(n\)个盒子，且第\(i\)个盒子中的物品数在\([0,c_i]\)范围内”的方案数。原问题就是求\(f(b)-f(a-1)\)。我们进行容斥：
因为\(n\leq10\)，所以我们可以枚举哪些盒子超出范围，共有\(2^n\)种。接下来我们只需求：将不超过\(m\)个物品放入\(n\)个盒子中，对于其中的\(k\)个盒子\(p_1..p_k\)，其中的物品数超过范围的方案数。
我们先向这\(k\)个盒子里分别放入\(c+1\)个物品，然后再将剩下的物品放进\(n\)个盒子。将不超过\(m_0\)个物品放进\(n\)个盒子的方案数为\(\binom{m_0+n}{n}\)，也就是将\(m_0\)分成\(n+1\)个非负整数的方案数。如果无法让\(k\)个盒子都超出范围，方案数就为\(0\)。
不过一个组合数对\(2004\)取模很烦。一般来说，如果要模一个不能表示成\(p^q\)的数，需要用中国剩余定理进行展开再用扩展Lucas定理。\(2004=2^2\times 3\times 167\)，分别对\(2^2,3,167\)取模再组合起来。不过因为这道题\(n\)很小，所以有一种简单做法：
对于本题来说，\(\dbinom{m_0+n}{n} \bmod2004=\dfrac{\prod_{i=0}^{n-1}(m_0+n-i) \bmod (2004\cdot n!)}{n!}\)，\(O(n)\)暴力计算即可。
Code
//[CEOI2004]Sweet
#include <cstdio>
typedef long long lint;
lint const H=2004;
int n,a[20];
lint facN;
int C(int a,int b)
{
lint r=1;
for(int i=1;i<=b;i++) r=(r*(a-i+1))%(facN*H);
return r/facN;
}
int dfs(int x,int m,int cnt)
{
if(m<0) return 0;
if(x>n) return ((cnt&1?-1:1)*C(m+n,n)+H)%H;
int r=0;
r+=dfs(x+1,m-a[x]-1,cnt+1);
r+=dfs(x+1,m,cnt);
return r%H;
}
int main()
{
int x,y; scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
facN=1; for(int i=1;i<=n;i++) facN=facN*i;
int ans=dfs(1,y,0)-dfs(1,x-1,0);
printf("%lld\n",(ans+H+H)%H);
return 0;
}
P.S.
%%%Icefox，%%%Pickupwin