bzoj 3027 [Ceoi2004]Sweet—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3027

化式子到 ( \mul_{i=1}^{n}(1-x^(m[i]+1)) ) / (1-x)^n 之后就不会了。

其实把分子拿出来后的部分可以展开成一个式子，用组合意义可知 k 次项系数是 C( n-1+k,n-1 ) 。

分子的那部分可以暴搜 2^n 种可能的项！一个项 k * x^y 对答案的贡献就是 k*( \sum_{i=L-y}^{R-y}C(n-1+i,n-1) )；考虑完这 2^n 种情况对答案的贡献后答案就算好了。

组合数一列的求和可以是那个右下角位置的值。

模数可能让组合数不能除，但可以把要除的 n! 乘进模数里，即 % (mod*n!) ，最后就可以把答案除以 n! 再输出了。

注意负数。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=,M=;

int n,m,w[N],L,R;

ll mod,ans;

void upd(ll &x){x>=mod?x-=mod:;}

ll calc(int k)

{

  ll ret=;

  for(int i=k+;i<=k+n;i++)

    ret=ret*i%mod;

  return ret;

}

void dfs(int cr,int xs,int cs)

{

  if(cs>R)return;

  if(cr>n)

    {

      ll d=calc(R-cs)+mod-(L-cs-<?:calc(L-cs-));

      upd(d);

      ans=(ans+xs*d)%mod;//xs may <0 so ans may <0!!!

      return;

    }

  dfs(cr+,xs,cs);

  dfs(cr+,-xs,cs+w[cr]+);

}

int main()

{

  scanf("%d%d%d",&n,&L,&R);

  for(int i=;i<=n;i++)scanf("%d",&w[i]);

  m=;for(int i=;i<=n;i++)m*=i; mod=(ll)*m;

  dfs(,,); if(ans<)ans+=mod;///

  printf("%lld\n",ans/m);

  return ;

}

巴特西

bzoj 3027 [Ceoi2004]Sweet——生成函数

最新文章

热门文章