CF451E Devu and Flowers

\(CF451E\) \(Devu\) \(and\) \(Flowers\)

链接:https://www.luogu.com.cn/problem/CF451E

题目描述:将一些球丢进一个盒子里,每一个求有一种颜色,有多少种本质不同的方法

题解:可知该题的模型是多重集的组合数，由于该题不满足\(a_{i}<=r\)，则我们需要容斥,每一次容斥有\(s\)个不符合要求的选法，则每一次的贡献为\(\sum_{i=0}^{n}(-1)^n\sum_{|S|==i}{}C(s,sum-(sum_a(S)+|S|))\)

#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
long long ans,n,k,f[22],res,mul=1;
long long fast_pow(long long a,int b)
{
  if (b==0)
    return 1;
  if (b&1)
    return fast_pow(a*a%mod,b/2)*a%mod;
  else
    return fast_pow(a*a%mod,b/2);
}
long long C(long long b)
{
  res=mul;
  for (long long i=b-(n-1)+1;i<=b;++i)
    res=(res*(i%mod))%mod;
  return res;
}
void dfs(int x,int r,long long sum)
{
  if (sum<n-1)
    return;
  if (x==n+1)
    {
      if (r%2==1)
	ans=(ans+C(sum))%mod;
      else
	ans=(ans-C(sum))%mod;
      return;
    }
  for (int i=x+1;i<=n+1;++i)
      dfs(i,r+1,sum-f[i]-1);
  return;
}
int main()
{
  scanf("%lld%lld",&n,&k);
  for (int i=1;i<=n;++i)
    scanf("%lld",&f[i]);
  for (long long i=1;i<=n-1;++i)
    mul=(mul*fast_pow(i%mod,mod-2))%mod;
  dfs(0,0,n+k);
  printf("%lld\n",(ans+mod)%mod);
  return 0;
}