bzoj 2839 集合计数 —— 二项式反演

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

设 \( f(i) \) 为至少 \( i \) 个选择，则 \( f(i) = C_{n}^{i} * (2^{2^{n-i}} - 1) \)，因为其他可选可不选；

设 \( g(i) \) 为恰好 \( i \) 个选择，则 \( f(i) = \sum\limits_{j=i}^{n} g(j) * C_{j}^{i} \)

感觉形式不是一般那种，所以想换一下，设 \( f(i) \) 为至多 \( i \) 个不选，则 \( f(i) = C_{n}^{i} * (2^{2^{i}} - 1) \)

\( g(i) \) 为恰好 \( i \) 个不选，则 \( f(i) = \sum\limits_{j=0}^{i} g(j) * C_{i}^{j} \)

则 \( g(i) = \sum\limits_{j=0}^{i} (-1)^{i-j} * C_{i}^{j} * f(j) \)

然而这样求 \( g(n-k) = \sum\limits_{i=0}^{n-k} (-1)^{n-k-i} * C_{n-k}^{i} * f(i) \) 却不对...改成

\( g(n-k) = \sum\limits_{i=0}^{n-k} (-1)^{n-k-i} * C_{n-i}^{k} * f(i) \) 却对了...不明白啊...

后来知道上面那个形式也可以直接反演 \( g(i) = \sum\limits_{j=i}^{n} (-1)^{j-i} * C_{j}^{i} * f(j) \)

还是不明白那种做法，组合数为什么...

注意放在指数的数是对 mod-1 取模！

upt：如果 \( f(i) \) 是至多 \( i \) 个不选，那么 \( f(i) = \sum\limits_{j=0}^{i} C_{n-j}^{n-i} * g(j) \)，而不是 \( C_{i}^{j} \)

因为“至多 \( i \) 个”，所以 \( i \) 是不确定的，而 \( n-i \) 确定必选，算方案的时候也是 \( f(i) = C_{n}^{i} * (2^{2^{i}}-1) \)

所以应该是在能确定的部分中进行选择，也就是 \( C_{n-j}^{n-i} \) ！

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

int const xn=1e6+,mod=1e9+;

int n,k,jc[xn],jcn[xn],f[xn];

ll pw(ll a,int b,int md){ll ret=; for(;b;b>>=,a=a*a%md)if(b&)ret=ret*a%md; return ret;}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void init()

{

  jc[]=;

  for(int i=;i<=n;i++)jc[i]=(ll)jc[i-]*i%mod;

  jcn[n]=pw(jc[n],mod-,mod);

  for(int i=n-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

}

int C(int n,int m){return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;}

int main()

{

  n=rd(); k=rd(); init();

  for(int i=;i<=n;i++)f[i]=(ll)C(n,i)*(pw(,pw(,i,mod-),mod)-)%mod;//

  int ans=;

  for(int i=;i<=n-k;i++)ans=upt(ans+(ll)C(n-i,k)*f[i]*(((n-k-i)&)?-:)%mod);//C(n-k,i)?

  /* //也可

  for(int i=0;i<=n;i++)f[i]=(ll)C(n,i)*(pw(2,pw(2,n-i,mod-1),mod)-1)%mod;//

  int ans=0;

  for(int i=k,t=1;i<=n;i++,t=-t)ans=upt(ans+(ll)C(i,k)*f[i]*t%mod);

  */

  printf("%d\n",ans);

  return ;

}

巴特西

bzoj 2839 集合计数 —— 二项式反演

最新文章

热门文章